Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Creating Kakuro Puzzles

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Random thoughts
View previous topic :: View next topic  
Author Message
MusiX

Joined: 17 Nov 2005
Posts: 2
:

Items
PostPosted: Thu Nov 17, 2005 12:08 pm    Post subject: Creating Kakuro Puzzles Reply with quote

Hi,

Even though I think they are not as interesting as Sudoku, I'd like to create some Kakuro Puzzles. Does anybody have some goot hints, tips or resources about generating Kakuro puzzles? I'd like to write a program but don't really know where to begin...

Thanks
Back to top
View user's profile Send private message
Bo

Joined: 02 Sep 2005
Posts: 27
:

Items
PostPosted: Thu Dec 01, 2005 12:07 pm    Post subject: Re: Creating Kakuro Puzzles Reply with quote

There is a thread about Killer Sudoku that can be used as starting point:
http://www.setbb.com/phpbb/viewtopic.php?t=213&mforum=sudoku
In Killer Sudoku there is the additional constraint that each cell belongs to a group of cells whose values must add up to a specified sum.
In the thread, code for a solver is given based on the exact cover concept.
In Kakuro, however, a cell will belong to 2 sum groups.
This must be handled in some way. Maybe by allocating an exact cover column for each cell and sum group?
Once you have a solver, you can try to generate puzzles using ideas for how Sudoku puzzles are generated.
If you find any other resources how to generate Kakuro puzzles I am interested to know.

Bo
Back to top
View user's profile Send private message
jbum

Joined: 14 Aug 2005
Posts: 14
:
Location: Los Angeles

Items
PostPosted: Thu Dec 01, 2005 6:23 pm    Post subject: Reply with quote

Hi,

I've implemented a Perl program for generating Kakuro puzzles, but it uses techniques that are quite different from the techniques I use for generating sudoku. I basically use brute force techniques with
a few heuristics for optimization.

It is much closer to a crossword generator I made some years ago.
Many academic articles on crossword puzzle generation are relevent
here.

Unfortunately, I am finding it much slower to generate Kakuros than sudoku - especially puzzles 7x7 or larger. The vast majority of puzzles I generate lead to multiple solutions, and it takes a long time to filter out valid puzzles that have only one solution.

The basic algorithm I use is as follows:

1) Generate a grille for the puzzle (the pattern of empty / non-empty
cells). I do this by randomly choosing a number of empty cells, and
then empting them, creating a symmetrical puzzle. The grille is rejected
if it leads to an invalid puzzle (containing solo squares, disconnected islands, a word with more than 9 digits, etc.). I can generate grilles
pretty quickly.

2) Fill the grille with unique numbers, insuring that no word contains a duplicate number. I am guessing that the work in Step 4 can be reduced if some heuristics are used here, such as forcing a few words to contain sums which have more limited possibilities.

3) Generate the sums for each 'word' in the puzzle (the clues). At this
point, you have the answers and clues, but you don't know if the puzzle
leads to multiple solutions.

4) Generate possible solutions to the puzzle using a depth-first search, based on the sums (the clues) only. This essentially requires a fast
puzzle solver. Terminate the search if 2 or more solutions are found. This is the slowest part of the process, and there
are numerous optimizations to be made here, such as the order in
which the cells are solved, and optimization of backtracking.

5) If 2 solutions are found, reject the puzzle and go back to step 2.

6) Save the puzzle and go back to step 1.
_________________
http://www.krazydad.com/
Back to top
View user's profile Send private message Visit poster's website
MusiX

Joined: 17 Nov 2005
Posts: 2
:

Items
PostPosted: Tue Dec 13, 2005 9:29 am    Post subject: Reply with quote

Thanks jbum your algorithm is quite useful, although i'm a bit stuck on the grille creation. I don't think your script is open source?
Back to top
View user's profile Send private message
jbum

Joined: 14 Aug 2005
Posts: 14
:
Location: Los Angeles

Items
PostPosted: Tue Dec 13, 2005 3:22 pm    Post subject: Grille creation Reply with quote

A few tips on grille creation:

I use a standard-issue flood-fill algorithm to determine if a grille is
all interconnected.

The most common problem when generating grilles is accidentally
generating 1-word squares. In my first grille generator, I was
getting a lot of these, especially at the larger sizes. I later found a way
to avoid it.

Basically I start with all black squares and then paint the grille with
a set of all the possible 2x2 patterns. When I paint, I check to see
which of the 2x2 patterns are legal in the location I want to paint in,
and then paint using one of the legal patterns. I keep adding new 2x2
patterns in random locations, until the grille is interconnected. This
naturally produces grilles with no 1-word squares.

You can see some of the grilles this produces here:

http://www.krazydad.com/kakuro/
_________________
http://www.krazydad.com/
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Random thoughts All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron