Solver for KenKen puzzles (Representation)

One of the biggest differences between KenKen puzzles and Sudoku puzzles is that the former are harder to represent compactly. Sudoku puzzles can be represented as a simple string of numbers, but the 2-dimensional cages of KenKen puzzles seem to require a more vebose representation. Fortunately, such a representation needn’t be complicated.

Requirements and Format

We want to develop a format for KenKen puzzles that is:

• Human-readable
• Easily parsed by software
• Concise

To this end, we will store puzzles as text files, each line of which will state a “fact” about the puzzle. Lines will be comprised of whitespace-delimited symbols. A complete set of facts will unambiguously describe a puzzle.

Size

The first piece of information used to describe a KenKen puzzle is its size. This will be stored as a line of the form:

• # ::size::

where “::size::” will be replaced by a number (e.g. 3, 6, or 9) representing the number of cells along one edge of the puzzle.

Cages

We don’t need to explicitly represent row- and column-uniqueness constraints, as they are implicit in the size of the puzzle. However, we do need to represent the puzzle’s cages, and the Addition, Subtraction, Multiplication, Division, and Assertion constraints. Each constraint will be stored on its own line, in one of the following forms:

• + ::cell_list::
• – ::cell_list::
• * ::cell_list::
• / ::cell_list::
• ! ::cell::

where “::cell_list::” will be replaced by a space-delimited list of cell names (e.g. “A1 B1 B2 B3”), and “::cell::” will be replaced by a single cell name. Cells will be named with letter-number combinations, in which the letters identify rows, with “A” at the top, and the numbers represent columns, with “1” at the left. (In a 9×9 grid, the upper-left cell is “A1”, and the lower-right is “I9”.)

Example

Here is a sample description of a 3×3 puzzle:

#	3
+	3	A1 B1
+	5	A2 B2
!	1	A3
+	5	B3 C3
+	4	C1 C2

which represents this:

Internals

In the code, we will represent puzzles as objects with two members:

• A size
• A list of cage constraints

Here is the class, which includes code to parse files of the format discussed above. (Note that it makes reference to the Constraint sub-classes defined yesterday.)

class Puzzle(object):
	lut = {'!':Assert, '+':Sum, '-':Diff, '*':Prod, '/':Div}
	def __init__(self, fn):
		# Parse file
		lines = [l.split() for l in file(fn, 'rb').read().strip().split('\n')]
		if (lines[0][0] != '#'):
			raise Exception('Puzzle definitions must begin with a size ("#") line')
		self.size	= int(lines[0][1])
		self.cages	= [self.lut[l[0]](*l[1:]) for l in lines[1:]]

Solutions

We’re not just about problems, we offer solutions too. Fortunately, solutions are much easier to deal with, and, in fact, we can largely crib Norvig’s Sudoku code to display them. (The following code assumes that the string module has been imported.)

def print_solution(s):
	if (not s):
		print s
		return
	rows	= list(set(k[0] for k in s.keys())); rows.sort()
	cols	= list(set(k[1] for k in s.keys())); cols.sort()
	max_len = max(map(len, s.values()))
	row_div = '\n' + '-+-'.join('-'*max_len for c in cols) + '\n'
	print row_div.join(' | '.join(string.center(s[r+c], max_len) for c in cols) for r in rows)

This code will properly display complete or partial solutions stored as string->string dictionaries, in which the keys are cell IDs (of the same form used in puzzle definitions) and the values are made up of numbers from 1 to 9, representing the possible values of the cell.

Here is an example of a partial solution:

 12 |  23 | 123
----+-----+----
 12 |  23 | 123
----+-----+----
123 | 123 | 123

and a complete solution:

2 | 3 | 1
--+---+--
1 | 2 | 3
--+---+--
3 | 1 | 2

Coming Attractions

Next week (this weekend will likely cover other matters) we’ll combine the constraint classes we defined yesterday, the code presented today, and some simple propagation and search code to produce a complete solver for KenKen puzzles.

Legal Notes

“KenKen” is a registered trademark. The people behind the game clearly intend to create a Sudoku-like frenzy for these puzzles, thereby enhancing the value of their trademark, from which they aim to profit. I wish them all the luck in the world with that plan. For my part, I wish to make clear that I am, and my (emerging) solver is, in no way associated with official KenKen-brand products. To the extent that I use the term “KenKen” as an adjective, it should be understood to mean “compatible with products or puzzles produced by the holder of the trademark name ‘KenKen’”.