KenKen Solver – Multiple Solutions

A reader asks if the KenKen solver we recently developed can handle puzzles with multiple solutions. It turns out to be pretty simple to modify the search-and-propagation algorithm to return all the solutions to a puzzle, instead of just one.

Starting Point

Let’s pick up where we left off after the last round of optimization, with this version of the solver. Our task will be to make the solve() function return every solution to a KenKen puzzle, not simply one of them.

Here’s the critial part of the code:

def solve(puzzle):
	... snip ...
	# Helper: Recursively refine a solution with search and propagation
	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])
	# Solve
	d_sum_queries = {}
	d_prod_queries = {}
	symbols = string.digits[1:1+puzzle.size]
	return search(constrain(dict((c,symbols) for c in d_constraints.keys()), *puzzle.cages))

Exhaustive Search

The key part of the code is found at the bottom of the search() function:

return first(search(assign(solution.copy(), cell, h)) for h in solution[cell])

This code returns the first solution which results from plugging each candidate value into the specified cell, and testing whether or not a complete solution can be found given that starting point.

We want to write a search function that returns all solutions found from all such starting points. Here’s an example of one:

# Helper: Recursively refine a solution with search and propagation
def search_ex(solution):
	# Check for trivial cases
	if (not solution):
		return []
	if 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
	rv = []
	for h in solution[cell]: rv.extend(search_ex(assign(solution.copy(), cell, h)))
	return rv

Here’s a modified solve() function that can support exhaustive search:

def solve(puzzle, exhaustive=False):
	... snip ...
	# Helper: Recursively refine a solution with search and propagation
	def search(solution):
		... snip ...
	def search_ex(solution):
		... snip ...
	# Solve
	d_sum_queries = {}
	d_prod_queries = {}
	symbols = string.digits[1:1+puzzle.size]
	if (exhaustive):
		fxn = search_ex
	else:
		fxn = search
	return fxn(constrain(dict((c,symbols) for c in d_constraints.keys()), *puzzle.cages))

A complete solver incorporating these changes can be downloaded here.

Example

The following puzzle has three solutions:

#	5
+	14	A1 A2 B1 B2
-	3	A3 B3
/	4	A4 A5
-	2	B4 B5
-	2	C1 C2
*	40	C3 D3 D4 E4
+	9	C4 C5 D5
/	2	D1 E1
*	12	D2 E2 E3
!	5	E5

Assuming that it’s stored in a file named “5x5m.txt” in the working directory, and that the Python solver provided above is stored in a file named “neknek_3.py” on the import path, we can solve this puzzle with the following commands from within the PythonWin interpreter:

>>> import neknek_3
>>> for s in neknek_3.solve(neknek_3.Puzzle('5x5m.txt'), True): neknek_3.print_solution(s); print

The output:

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

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

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

A Caveat

It can take quite a bit longer to run the exhaustive solver than the first-match solver, especially on some larger puzzles with 10+ solutions. This is simply due to the much larger portion of the search space that must be covered. It’s probably best to avoid the exhaustive mode if you don’t really need it.