40,000 KenKen Puzzles with Unique Solutions

KenKen

I wrote a solver and generator of KenKen puzzles called CanCan. It started as a Scala learning exercise but became a full-blown tool that may be of general interest. I’ve used it to generate and publish over 40,000 KenKen puzzles with unique solutions of sizes ranging from 4×4 to 9×9.

KenKen is a cousin of Sudoku and the strategy employed here is an extension of the constraint-propagation algorithm Peter Norvig uses in his Sudoku solver. There is a mathematical literature on Sudoku. CanCan utilizes some of the constraint satisfaction strategies described in “A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles” by J.F. Crook. In “Sudoku Squares and Chromatic Polynomials” Agnes Herzberg and M. Ram Murty derive various theoretical results by treating Sudoku as a graph coloring problem. It is not immediately obvious how to extend their results to KenKen since it’s not clear how to make a topological representation of arithmetic constraints, but this may be a fruitful area for investigation. It turns out the hard part is neither solving nor generating KenKen puzzles, but rather generating ones with unique solutions. CanCan currently does this in a brute force fashion, by solving the puzzles that it generates and throwing out the ones that have more than one solution. Improving performance by being smarter about this is an area of future work.

KenKen and Scala

I’ll let CanCan’s documentation speak for itself to anyone who’s interested and here just point out some of the Scala language idioms I utilized. The solver algorithm is a depth-first search of a solution graph in which branches of the recursion may be abandoned if they lead to a state that is inconsistent with the puzzle constraints. The individual search states are called markups, and the following for comprehension comprises the whole of the core search algorithm.

def nextMarkups(markup: Markup): TraversableView[Markup, Traversable[_]] =
    for {cell <- selectCell(markup, puzzle).toTraversable.view
         value <- guessValue(markup, cell).par
         next <- constraints(markup + (cell -> Set(value)), constraints.cellMap(cell))}
    yield next

As long as there are cells with ambiguous values in their markup we select one of them, guess one of its values, then apply the puzzle constraints to get the following markup state. The code is short and readable, but then there’s some Scala magic behind the scenes making it that way.

  1. The first two clauses of the comprehension are loops over cells and values, respectively, while the constraints application in the last one returns an Option depending on whether or not the particular branch of the search tree is consistent with the puzzle constraints, which allows the search to ignore invalid branches. This is an instance of Scala’s Option monad for-comprehension idiom, the easiest way I’ve ever seen to do an early exit from recursion.
  2. The return type TraversableView[Markup, Traversable[_]] is a lazy sequence of markups. The loop evaluates individual search steps are only as needed, which makes many optimizations possible. (For example, when trying to determine if a puzzle has a unique solution I simply ask for the first two solved elements from this sequence then see how many come back.) I don’t have to do any extra work to implement lazy evaluation. I code as if the entire sequence were in memory, and Scala’s lazy collections framework ensures that everything happens just in time.
  3. Searches of sub-trees arising for different guesses in the same cell can be conducted in parallel. This can be a timesaver if your hardware supports it, but multithreaded coding is a pain. In most languages you break the flow of your source code by sequestering the parallelized instructions off in their own function, have to implement tricky things like thread pools, and generally suffer through at least one synchronization bug. Scala’s parallel collections framework handles all that for you. The .par at the end of the value clause of the loop is all you need. I implemented the whole of my parallelization in four keystrokes.

Scala

My interest in functional programming was piqued by a fellow developer describing his experiences with Haskell. “Usually I can pick up a new programming language over a weekend,” he said, “but I’ve been at Haskell for a year and I still don’t understand it.” He meant this as praise, though it sounded more like a serious flaw in Haskell to me. Still, I was intrigued enough to split the difference and go with Scala, since at worst I figured it would just be Java with much-needed type inference. It took me a week or two to get into the groove, but now after completing a substantive project I am impressed with the functional paradigm in general and Scala in particular. Being able to think of your code’s methods as functions in the strict mathematical sense allows you to bring a host of intuitions from outside the programming domain to bear. The emphasis on immutable data structures doesn’t strike me as profound in and of itself, but I see how it enables very clean implementations of things like parallelism and lazy evaluation. I’m not as sold on using recursion for everything because it’s too hard to step through in a debugger, but the complexity has to end up somewhere. I’m not in love the way I was with Ruby a few years back, but I at least have a serious crush on Scala and can cheerfully recommend anyone else who is considering it to take the leap.

Advertisements
This entry was posted in Those that have just broken the flower vase. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s