I've written a simple KenKen puzzle/solver in Python. I'd love some feedback on the design of the puzzle, as well as the architecture for the solver.
To model the puzzle, I have the following classes:
Cellis used to model a (row, col, value) tupleCage(abstract) is used to model a grouping ofCellobjects that must collectively satisfy a constraint. From this class, we have the following derived classes:AddCagefor cells involved in addition constraintsMulCagefor cells involved in multiplication constraintsSubCagefor cells involved in subtraction constraintsDivCagefor cells involved in division constraintsConCagefor constant constraintsRowCagefor unique row/column constraints
Puzzlecombines cages, cells, and exposes methods for the unassigned cells, whether or not the puzzle is solved, etc.
Now for the code:
from abc import ABC, abstractmethod
from utils import kk_add, kk_mul, kk_sub, kk_div
class Cell:
def __init__(self, row, col, value=None):
"""
Models a cell in a kenken puzzle
Args:
row: row
col: column
value: cell value
"""
self.row = row
self.col = col
self.value = value
def __str__(self):
return '<Cell ({0}, {1}): {2}>'.format(self.row, self.col, self.value)
def __hash__(self):
return hash((self.row, self.col))
def accept(self, visitor):
"""
Visitor implementation; accept a visitor object
and call the object's visit method for this object
Args:
visitor: `CellVisitor` implementation
Returns: None
"""
visitor.visit_cell(self)
class Cage(ABC):
def __init__(self, cells, func):
"""
Base class to model a cage in a kenken puzzle
A cage is a grouping of cells with a constraint
that the values of the cells must collectively satisfy
Args:
cells: the `Cell` objects in this cage
func: a predicate used to indicate when the cage is satisfied
"""
self.cells = set(cells)
self.func = func
def __str__(self):
return '<{0} cells={1}>'.format(self.__class__.__name__, self.cells)
@property
def values(self):
"""
Returns: list the cell values list for this cage
"""
return [cell.value for cell in self.cells]
@property
def consistent(self):
"""
Returns: bool whether or not this cage is consistent
with respect to its current cell values
"""
return None in self.values or self.solved
@property
def solved(self):
"""
Returns: bool whether or not this cage is solved
with respect to its current cell values
"""
values = self.values
return (
None not in values
and len(values) == len(self.cells)
and self.evaluate(*values)
)
def evaluate(self, *values):
"""
Evaluate this cage for the given input arguments,
returning whether or not it's conditions have been satisfied
Args:
*values: variate list of test values
Returns: bool
"""
return self.func(values)
@abstractmethod
def accept(self, visitor):
"""
Visit this cage. Accept a visitor object and call the
object's visit method for this object
Args:
visitor: `CageVisitor` implementation
Returns: None
"""
pass
class AddCage(Cage):
def __init__(self, cells, value):
"""
Models an addition cage in a kenken puzzle
Args:
cells: list of `Cell` objects contained in this cage
value: target value the cell values in this cage must sum to
"""
self.value = value
super().__init__(cells, lambda values: kk_add(values, value))
def accept(self, visitor):
"""
Visit this cage
Args:
visitor: `CageVisitor` object
Returns: None
"""
visitor.visit_add(self)
class MulCage(Cage):
def __init__(self, cells, value):
"""
Models a multiplication cage in a kenken puzzle
Args:
cells: list of `Cell` objects contained in this cage
value: target value the cell values in this cage must multiply to
"""
self.value = value
super().__init__(cells, lambda values: kk_mul(values, value))
def accept(self, visitor):
"""
Visit this cage
Args:
visitor: `CageVisitor` object
Returns: None
"""
visitor.visit_mul(self)
class SubCage(Cage):
def __init__(self, cells, value):
"""
Models a subtraction cage in a kenken puzzle
Args:
cells: list of `Cell` objects contained in this cage
value: target value the cell values in this cage must subtract to
"""
self.value = value
super().__init__(cells, lambda values: kk_sub(values, value))
def accept(self, visitor):
"""
Visit this cage
Args:
visitor: `CageVisitor` object
Returns: None
"""
visitor.visit_sub(self)
class DivCage(Cage):
def __init__(self, cells, value):
"""
Models a division cage in a kenken puzzle
Args:
cells: list of `Cell` objects contained in this cage
value: target value the cell values in this cage must divide to
"""
self.value = value
super().__init__(cells, lambda values: kk_div(values, value))
def accept(self, visitor):
"""
Visit this cage
Args:
visitor: `CageVisitor` object
Returns: None
"""
visitor.visit_div(self)
class ConCage(Cage):
def __init__(self, cell, value):
"""
Models a constant cage in a kenken puzzle
Args:
cell: `Cell` object for this cage
value: target value
"""
def func(values):
return len(values) == 1 and values[0] == value
self.value = value
super().__init__([cell], func)
def accept(self, visitor):
"""
Visit this cage
Args:
visitor: `CageVisitor` object
Returns: None
"""
visitor.visit_con(self)
class RowCage(Cage): # RowConstraint
def __init__(self, cells):
"""
Models a row constraint in a kenken puzzle
Here the cell values in this cage must be all unique
for the cage to be solved
Args:
cells: `Cell` objects
"""
def func(values):
return len(values) == len(set(values))
super().__init__(cells, func)
def accept(self, visitor):
"""
Visit this cage
Args:
visitor: `CageVisitor` object
Returns: None
"""
visitor.visit_row(self)
class Puzzle:
def __init__(self, width, cells, cages):
"""
Models a kenken puzzle
See https://en.wikipedia.org/wiki/KenKen
for more information
Args:
width: puzzle size
cells: `Cell` objects comprising this puzzle
cages: `Cage` objects a solution for this puzzle must satisfy
"""
self.width = width
self.cells = cells
self.cages = cages
def __str__(self):
return '<Puzzle width={0}, cages={1}>'.format(
self.width, len(self.cages)
)
@property
def domain(self):
"""
Returns: bool this puzzle's possible cells values
"""
return range(1, self.width + 1)
@property
def unassigned(self):
"""
Returns: bool this puzzle's unassigned cells
"""
return (cell for cell in self.cells if cell.value is None)
@property
def solved(self):
"""
Returns: bool whether or not this puzzle has been solved
"""
return all(cage.solved for cage in self.cages)
def consistent(self, cell):
"""
Returns whether or not the value for the given cell is consistent
with all of its cage constraints
Args:
cell: `Cell` object
Returns: bool
"""
return all(cage.consistent for cage in self.cages if cell in cage.cells)
For both the Cell and the Cage classes, we have an accept method. This is used to make the objects amenable to the visitor design pattern, for use during solving. The idea is that each cell has a set of "candidate values" that needs to be reduced after we decide to place a value for the cell. I decided to expose things this way to make edits to the core puzzle logic less frequent. Moreover, to try different solution strategies, we need only change the implementation of the visitor we pass to the cells/cages; the core puzzle components need not be changed.
Let's look at the solver classes:
CellVisitoris used to visit cellsCageVisitoris used to visit cages; its lifetime is managed by aCellVisitor
And the code:
from utils import with_timing, kk_div, kk_sub
class CellVisitor:
def __init__(self, candidates, cages):
"""
Visitor for puzzle cells
Pass an instance of this object to a puzzle cell
to "visit" the cell and all the cages that involve
this cell
Here we use this object to model the process of eliminating
a set of candidate values for the given cell
See https://en.wikipedia.org/wiki/Visitor_pattern
for more information on this design pattern
Args:
candidates: list of cell candidates
cages: list of cages this visitor should also visit
"""
self.candidates = candidates
self.cages = cages
def __str__(self):
return '<CellVisitor candidates={0}>'.format(self.candidates)
def visit_cell(self, cell):
"""
Visits a `Cell`
Visit each cage that contains this cell; the resulting
candidates will be the possible values for this cell
Args:
cell: `Cell` object to visit
Returns: None
"""
visitor = CageVisitor(self.candidates)
for cage in self.cages:
cage.accept(visitor)
class CageVisitor:
def __init__(self, candidates):
"""
Visitor for puzzle cages
The methods in this object are used to prune the cell
candidate values
Args:
candidates: cell candidate values to prune
"""
self.candidates = candidates
def __str__(self):
return '<CageVisitor candidates={0}>'.format(self.candidates)
def visit_add(self, cage):
"""
Visits an `AddCage`
We start with the current cage sum. Any
value that exceeds the cage target value is pruned
Args:
cage: `AddCage` object to visit
Returns: None
"""
s = sum(value for value in cage.values if value)
for value in self.candidates[:]:
if value + s > cage.value:
self.prune(value)
def visit_mul(self, cage):
"""
Visits a `MulCage`
Any candidate value that is not a divisor of
the cage target value is pruned
Args:
cage: `MulCage` object to visit
Returns: None
"""
for value in self.candidates[:]:
if cage.value % value != 0:
self.prune(value)
def visit_sub(self, cage):
"""
Visits a `SubCage`
This implementation removes pairs from the
candidates if the difference of a given pair
is not equal to the cage value
Args:
cage: `MulCage` object to visit
Returns: None
"""
candidates = self.candidates[:]
for x in candidates:
if not any(kk_sub([x, y], cage.value) for y in candidates):
self.prune(x)
def visit_div(self, cage):
"""
Visits a `DivCage`
This implementation removes pairs from the
candidates if the quotient of a given pair
is not equal to the cage value
Args:
cage: `DivCage` object to visit
Returns: None
"""
candidates = self.candidates[:]
for x in candidates:
if not any(kk_div([x, y], cage.value) for y in candidates):
self.prune(x)
def visit_con(self, cage):
"""
Visits a `ConCage`
This implementation removes all candidates
that are not equal to the cage target value
Args:
cage: `ConCage` object to visit
Returns: None
"""
for x in self.candidates[:]:
if x != cage.value:
self.prune(x)
def visit_row(self, cage):
"""
Visits a `RowCage`
This implementation removes all values
that are already assigned to a cell in the row
Args:
cage: `ConCage` object to visit
Returns: None
"""
for value in cage.values:
self.prune(value)
def prune(self, value):
"""
Helper method to safely remove values
from the candidates
Args:
value: to remove
Returns: None
"""
if value in self.candidates:
self.candidates.remove(value)
@with_timing
def backtrack_solve(puzzle):
"""
Solves a kenken puzzle recursively
During each iteration of the algorithm, a filtering
strategy is applied to the puzzle's remaining unassigned cells
See https://en.wikipedia.org/wiki/Backtracking
for more information on this algorithm
Args:
puzzle: `Puzzle` object to solve
Returns: bool True if all values in `puzzle` have been assigned a value
"""
def reduce(cell):
"""
Reduce the candidate values for this cell
Args:
cell: `Cell` object to reduce
Returns: list of reduced candidates
"""
candidates = list(puzzle.domain)
cages = (cage for cage in puzzle.cages if cell in cage.cells)
cell.accept(CellVisitor(candidates, cages))
return candidates
def solve():
"""
Solve this puzzle recursively
The algorithm first reduces the candidates for the puzzle's
unassigned cells
We then sort the reduced cells by candidate length and
recursively try values for the current cell until the search
successfully solves the puzzle
Returns: bool
"""
reduced = {cell: reduce(cell) for cell in puzzle.unassigned}
for cell in sorted(reduced, key=lambda c: len(reduced[c])):
for value in reduced[cell]:
cell.value = value
if puzzle.consistent(cell):
if solve():
return True
cell.value = None
return False
return puzzle.solved
return solve()
You can read more about the algorithm in the documentation for the solver. The basic idea is that when we visit a cell, we start off with the puzzle's full domain. Each of the cages reduces the candidates further, by means of a filtering strategy that is invoked on the candidates when we visit that cage. We do this "reduce" operation for each of the unassigned cells.
Finally, I have a "utils.py" that contains definitions that are in use by the solver and puzzle files. Included is a parse_string method that can be used to create a Puzzle object from a dictionary string:
import time
from ast import literal_eval
from functools import wraps, reduce
def kk_add(values, value):
"""
Returns whether or not the given values
sum to the target value
Args:
values: list of test values
value: target value
Returns: bool
"""
return sum(values) == value
def kk_mul(values, value):
"""
Returns whether or not the given values
multiply to the target value
Args:
values: list of test values
value: target value
Returns: bool
"""
return product(values) == value
def kk_sub(values, value):
"""
Returns whether or not the given values subtract
to the target value
Args:
values: list of test values
value: target value
Returns: bool
"""
return abs(values[0] - values[1]) == value
def kk_div(values, value):
"""
Returns whether or not the given values divide
to the target value
Args:
values: list of test values
value: target value
Returns: bool
"""
return (int(values[0] / values[1]) == value or
int(values[1] / values[0]) == value)
def product(nums):
"""
Helper method to compute the product of a list
of numbers
Args:
nums: list of numbers
Returns: number
"""
return reduce(lambda x, y: x * y, nums, 1)
def with_timing(f, output=print):
"""
Helper method to run a function and output
the function run time
Args:
f: function to decorate
output: function to output the time message
Returns: callable decorated function
"""
@wraps(f)
def timed(*args, **kwargs):
ts = time.time()
result = f(*args, **kwargs)
te = time.time()
message = 'func:{!r} args:[{!r}, {!r}] took: {:2.4f} sec'.format(
f.__name__, args, kwargs, te - ts
)
output(message)
return result
return timed
def parse_string(s):
"""
Parse a string to a `Puzzle` object
The string should be a dictionary that python
can interpret literally. For example:
{
'size': 2,
'cages': [
{'value': 2, 'op': '/', 'cells': [(0,0), (0,1)]},
{'value': 3, 'op': '+', 'cells': [(1,0), (1,1)]}
]
}
The 'op' should be one of :
'+' -> AddCage,
'-' -> SubCage,
'*' -> MulCage,
'/' -> DivCage,
'$' -> ConCage
The exclusive row/column cages will be created automatically
Args:
s: input string to read
Returns: `Puzzle` object
"""
from puzzle import (
Cell,
AddCage,
SubCage,
MulCage,
DivCage,
ConCage,
RowCage,
Puzzle
)
d = literal_eval(s.strip())
cage_factory = {
'+': AddCage,
'-': SubCage,
'*': MulCage,
'/': DivCage,
'$': ConCage
}
size = d.get('size')
cages = d.get('cages')
if size is None or cages is None:
raise SyntaxError(
"Expected 'size' and 'cages'. Got `{0}`".format(d)
)
puzzle_cages = []
puzzle_cells = set()
for cage in cages:
value = cage.get('value')
cells = cage.get('cells')
if any(cell in puzzle_cells for cell in cells):
raise ValueError('Some cells exist in another cage {0}'.format(cells))
if not value or not cells:
raise SyntaxError(
"Expected 'value' and 'cells'. Got {0}".format(cage)
)
op = cage.get('op')
if op not in cage_factory:
raise SyntaxError(
"Expected '+', '-', '*', '/', '$'. Got {0}".format(op)
)
if op == '$' and len(cells) > 1:
raise ValueError("Expected one cell for `ConstantConstraint`")
cage_cells = []
for (row, col) in cells:
cell = Cell(row, col, None)
cage_cells.append(cell)
puzzle_cells = puzzle_cells.union(cage_cells)
# the constructor for `ConCage` expects a single cell as oppose to a list
cage = cage_factory[op](cage_cells[0] if op == '$' else cage_cells, value)
puzzle_cages.append(cage)
if len(puzzle_cells) != size * size:
raise Exception(
'Expected {0} cells; parsed {1}'.format(
size*size, puzzle_cells)
)
for row in range(size):
cells = [cell for cell in puzzle_cells if cell.row == row]
puzzle_cages.append(RowCage(cells))
for col in range(size):
cells = [cell for cell in puzzle_cells if cell.col == col]
puzzle_cages.append(RowCage(cells))
return Puzzle(size, puzzle_cells, puzzle_cages)
Any feedback is welcome. I have some additional puzzle files that I used while debugging/testing the solving algorithm, as well as a "run.py" file which provides a CLI for this application. If you think this is needed, feel free to leave a comment and I can provide a link.
