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()
		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.)

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:
			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_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’”.