Creating Kakuro Puzzles

MusiX · 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

Bo · 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

jbum · 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 / 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/

MusiX · 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?

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

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/