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
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’”.
Pingback: Things that were not immediately obvious to me » Blog Archive » No-op KenKen Solver