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)
# 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)
# 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))``````

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.

This entry was posted in Projects, Python. Bookmark the permalink.