A KenKen puzzle/solver in Python

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:

• Cell is used to model a (row, col, value) tuple

-
Cage (abstract) is used to model a grouping of Cell objects that must collectively satisfy a constraint. From this class, we have the following derived classes:

• AddCage for cells involved in addition constraints

• MulCage for cells involved in multiplication constraints

• SubCage for cells involved in subtraction constraints

• DivCage for cells involved in division constraints

• ConCage for constant constraints

• RowCage for unique row/column constraints

-
Puzzle combines 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 ''.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 i

I am unfamiliar with both the design pattern and the backtracking algorithm, so almost all of my comments will be nitpicks.

utils.py

• kk_sub: I prefer values[0] - values[1] in {value, -value}, which will work if value is negative. Maybe we know that it will always be nonnegative, though.

• kk_div: I prefer values[0] == values[1] value or values[1] == values[0] value, which avoids float division and casts.

• kk_{add,mul,sub,div}: It would be clearer to me if you used more descriptive argument names than 'values' and 'value'. You could do 'summands' and 'sum' (though that clashes with the built-in) for kk_add, 'factors' and 'product' for kk_mul, etc.

• product: I prefer reduce(operator.mul, values). You're already using functools, so I don't feel that this is a big jump in complexity.

-
parse_string:

• It would be clearer to me if you used a set comprehension to define cage_cells: {Cell(row, col, None) for (row, col) in cells}. Also, since value is a keyword argument in Cell.__init__ you could use set(itertools.starmap(Cell, cells)) (not that that's any clearer than what you have now).

• If you moved that definition up to right after the definition of cells, you could replace the test for already-accounted-for cells with if puzzle_cells.intersection(cage_cells), which is easier for me to parse.

• I think you should swap the test for already-accounted-for cells with the test for value or cells not being provided. It seems strange to use cells and only afterwards check that it's valid.

-
You could avoid the searches in the collection of the cells in each row and column using something like below.

rows = [[] for _ in range(size)]
cols = [[] for _ in range(size)]
# Later, inside look over cages:
for cell in cage_cells:
    rows[cell.row].append(cell)
    cols[cell.col].append(cell)
# Then, outside that loop:
puzzle_cages.extend(map(RowCage, itertools.chain(rows, cols)))

class definitions

• Cage.solved: I think the test that values and self.cells have the same length should either be removed or throw an exception if it fails. values is freshly created from self.cells immediately before the test; something catastrophic has happened if it fails.

• {Add,Mul,Sub,Div}Cage.__init__: if you switched the order of the arguments in kk_{add,mul,sub,div}, the super().__init__ call could use functools.partial(kk_{add,mul,sub,div}, value). I personally prefer that to the lambda, though I'd believe others would disagree with me. Also (this is out of my depth), doesn't this approach result in every instance of Cage having a dedicated func function object? It seems that all the instances of AddCage could share kk_add and just pass it both value and values (and likewise for the others). I think the subclasses of Cage should override evaluate, or func should be made a method.

• Puzzle.__init__: the puzzle comprises the cells, not the other way around.

• Puzzle.{domain,unassigned}: the docstring incorrectly says that a Boolean is returned.

• Puzzle.consistent: you repeat this expression for cages containing a given cell in reduce. Maybe it would be good to make a method for this?

solver code

• CageVisitor.visit_add:

• I'd prefer if value is not None in place of if value. Seeing if value along with sum makes me think of zero.

• If you found the difference between cell.value and s before the loop, you could avoid the additions inside the loop.

• You could prune more aggressively by factoring in how many other cells in the cage are undetermined. For example, if cage.value is 9, cage.values is [3, None, None], and self.candidates is [1, 4, 6], we can eliminate 6 because that would force the remaining undetermined cell to have value 0. That does couple the candidates for different cells, which it looks like you haven't done so far.

• CageVisitor.visit_mul: I prefer if cage.value % value. And why not use the quotient of cage.value and the product of the values of the cells whose values have been determined?

-
CageVisitor.visit_sub:

• In the docstring, 'MulCage' should be 'SubCage'.

-
I don't like how kk_sub([x, x], cage.value) will get called, and you aren't using the fact that the order of values doesn't affect kk_sub. Maybe you could do something like below. You could do something similar in visit_div.

self.candidates = list(itertools.chain.from_iterable(filter(
    lambda pair: kk_sub(pair, cage.value),
    itertools.combinations(candidates, 2)
)))

-
But that said, why are you finding differences between elements of candidates? It's the difference between x and the candidates of the other cells that matters, unless I misunderstand something. It seems to me that CageVisitor is initialized with a list of candidate values for the particular cell being visited, not a list of candidate values across all cells in the cage. I may well be confused on

StackExchange Code Review Q#162933, answer score: 7