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.
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() for cell, bad_choices in constraint.apply(solution).items(): values = solution[cell] for choice in bad_choices: 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.)
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.
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) # 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:
- 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.
- 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.
- 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,
# 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
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: d_constraints[cell].add(constraint) # 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_constraintsdictionary, 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.
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
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
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.
“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’”.