# Solver for KenKen puzzles (Search)

Today we complete the first version of our solver for KenKen puzzles. Previously we’ve defined constraint classes, input/output functions, and data structures; all that remains is to write the search and propagation code. Once again, this is all based on Norvig’s Sudoku solver.

### Constraint Propagation

The first thing we’ll define is a constraint propagation function. This will take a (partial) solution – a dictionary mapping strings representing cell IDs to strings representing possible values for those cells – and a list of constraints. The function will eliminate from the solution any possible cell values which are prohibited by any of the list of constraints. The function will also consider any constraints associated with any cells changed during this process, even if those constraints are not in the original list. Here’s the code:

``````def constrain(solution, *constraints):
queue = set(constraints)
while (queue):
constraint = queue.pop()
values = solution[cell]
values = values.replace(choice, '')
if (not values):
return False
if (solution[cell] == values):
continue
solution[cell] = values
queue.update(d_constraints[cell])
return solution``````

Note that this code makes reference to a d_`constraints` dictionary, which is assumed to be in lexical scope. This dictionary maps cell IDs to sets of the constraints associated with those cells. We’ll deal with its definition a bit later.

This function returns a constrained solution, or `False` if during the process of constraint a cell is discovered which has no possible legal values. (I.e. the puzzle cannot be solved given its constraints and previously chosen values.)

### Assignment

Next, we’ll define a helper function for search. This will simply assign a value to a cell of a partial solution, and then invoke constraint propagation to determine the ramifications of that assignment:

``````def assign(solution, cell, value):
solution[cell] = value
return constrain(solution, *d_constraints[cell])``````

This code also makes reference to a d_`constraints` dictionary, as above.

### Search

At last we come to the heart of the solver: The search function. It is quite modest:

``````def search(solution):
# Check for trivial cases
if ((not solution) or all(len(v)==1 for v in solution.values())):
return solution
# Find a most-constrained unsolved cell
cell = min((len(v),k) for k,v in solution.items() if len(v)>1)[1]
# Try solutions based upon exhaustive guesses of the cell's value
return first(search(assign(solution.copy(), cell, h)) for h in solution[cell])``````

This code takes a (partial) solution as a starting point for the search, and has three steps:

1. If the initial solution is `False`, no further action is necessary. If the initial solution has only one possible value for each cell, then it’s complete, and no further action is necessary.
2. If the solution is incomplete (i.e. processing didn’t terminate in the first step) find an unsolved cell (i.e. one with 2 or more possible values) with the minimum number of possible values.
3. Try assigning each possible value to the cell found in step 2, and then using the resulting partial solutions as the starting points for new searches. Return the first successful solution, if any.

This code uses a small helper function, `first()`:

``````# Return first non-false value, or False
def first(iterable):
for i in iterable:
if (i): return i
return False``````

### Putting It Together

We can now assemble the `constrain()`, `assign()`, and `search()` functions into a solver, which takes as its argument an instance of the `Puzzle()` class we defined last week:

``````def solve(puzzle):
# Derived from the problem size
rows	= string.ascii_uppercase[:puzzle.size]
cols	= string.digits[1:1+puzzle.size]
sets	= [Set(0, *(r+c for c in cols)) for r in rows] + \
[Set(0, *(r+c for r in rows)) for c in cols]
# Cell -> constraint mapping
d_constraints = dict((r+c, set()) for r in rows for c in cols)
for constraint in sets+puzzle.cages:
for cell in constraint.cells:

# Helper: Given a partial solution, apply (potentially) unsatisfied constraints
def constrain(solution, *constraints):
# ... snip ...
# Helper: Given a partial solution, force one of its cells to a given value
def assign(solution, cell, value):
# ... snip ...
# Helper: Recursively refine a solution with search and propogation
def search(solution):
# ... snip ...

# Solve
symbols = string.digits[1:1+puzzle.size]
return search(constrain(dict((c,symbols) for c in d_constraints.keys()), *puzzle.cages))``````

This function does some setup:

• Defines possible row and column names (e.g. A-I, 1-9) for a puzzle of the given size
• Defines all row- and column-uniqueness (`Set`) constraints for a puzzle of the given size
• Defines a `d_constraints` dictionary, which maps cell IDs to sets of constraints
• Defines the helper functions discussed above

This function then creates a completely unconstrained solution (in which any cell may have any value), constrains it with the puzzle’s cages, and invokes `search()` on the resulting partial solution.

### Invocation

Here is complete code for a KenKen solver. Assuming that you have this code stored in a file “neknek_0” on your import path, and that you have a puzzle stored in a file “6×6.txt” in your current working directory, you can invoke the solver with this code:

``````>>> import neknek_0
>>> neknek_0.print_solution(neknek_0.solve(neknek_0.Puzzle('6x6.txt')))``````

If 6×6.txt contains this puzzle definition:

``````#	6
+	13	A1 A2 B1 B2
*	180	A3 A4 A5 B4
+	9	A6 B6 C6
!	2	B3
*	20	B5 C5
+	15	C1 D1 E1
*	6	C2 C3
+	11	C4 D3 D4
!	3	D2
+	9	D5 D6 E4 E5
/	2	E2 E3
+	18	E6 F4 F5 F6
+	8	F1 F2 F3``````

the preceding invocation will print out this result:

``````1 | 4 | 3 | 5 | 2 | 6
--+---+---+---+---+--
3 | 5 | 2 | 6 | 4 | 1
--+---+---+---+---+--
4 | 6 | 1 | 3 | 5 | 2
--+---+---+---+---+--
5 | 3 | 6 | 2 | 1 | 4
--+---+---+---+---+--
6 | 2 | 4 | 1 | 3 | 5
--+---+---+---+---+--
2 | 1 | 5 | 4 | 6 | 3``````

### Coming Attractions

Tomorrow we’ll begin to look at some performance issues. On my machine, the preceding code will solve a 9×9 puzzle in about 0.7 seconds, but I think we can do better. Here’s the timing code, BTW:

``````>>> timeit.Timer('neknek_0.solve(neknek_0.Puzzle("9x9.txt"))', 'import neknek_0').timeit(number=10)/10
0.66255693738775678``````

### Hat Tip

Dave Shields has also posted a Python solver for these puzzles. It takes a somewhat different approach, and (I think) relies more heavily on exhaustive search. You might find it interesting.

### 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’”.

Share and Enjoy:
This entry was posted in Projects, Python. Bookmark the permalink.