
View previous topic :: View next topic 
Author 
Message 
 MusiX
 Joined: 17 Nov 2005  Posts: 2  :   Items 

Posted: Thu Nov 17, 2005 12:08 pm Post subject: Creating Kakuro Puzzles 


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 


 Bo
 Joined: 02 Sep 2005  Posts: 27  :   Items 

Posted: Thu Dec 01, 2005 12:07 pm Post subject: Re: Creating Kakuro Puzzles 


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 


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

Posted: Thu Dec 01, 2005 6:23 pm Post subject: 


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 / nonempty
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 depthfirst 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 


 MusiX
 Joined: 17 Nov 2005  Posts: 2  :   Items 

Posted: Tue Dec 13, 2005 9:29 am Post subject: 


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 


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

Posted: Tue Dec 13, 2005 3:22 pm Post subject: Grille creation 


A few tips on grille creation:
I use a standardissue floodfill algorithm to determine if a grille is
all interconnected.
The most common problem when generating grilles is accidentally
generating 1word 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 1word squares.
You can see some of the grilles this produces here:
http://www.krazydad.com/kakuro/ _________________ http://www.krazydad.com/ 

Back to top 




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

Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
