16
\$\begingroup\$

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 '<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:

  • CellVisitor is used to visit cells
  • CageVisitor is used to visit cages; its lifetime is managed by a CellVisitor

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.

\$\endgroup\$
  • \$\begingroup\$ Outstanding first question. Welcome to codereview! Nice piece of code too ! \$\endgroup\$ – Grajdeanu Alex. Jun 1 '17 at 18:04
  • \$\begingroup\$ Would it be possible for you provide the additional files? I'm writing a KenKen solver as well, and I find that there's a difficulty gradient of puzzles that can and can't be solved (until I add more strategies to the solver). I'm curious to see where on the gradient this solver lies. \$\endgroup\$ – Jeremy Weirich Jun 11 '17 at 17:04
6
+200
\$\begingroup\$

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 this point.

    • Shouldn't we make use of the cells whose values have already been determined, as is done in CageVisitor.visit_add?
  • CageVisitor.visit_con: I may be missing something, but why not just do self.candidates = [cage.value]?
  • CageVisitor.prune: why not make self.candidates a set or something else with faster removals than a list? I may be missing something tricky about iterating over the structure while modifying it.
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! Very nice answer, I don't agree with some points, but on the all the points raised seem very solid. \$\endgroup\$ – Peilonrayz Jun 7 '17 at 9:04
  • \$\begingroup\$ @Peilonrayz Thank you! And thank you for the Markdown help. \$\endgroup\$ – Ben Whitney Jun 7 '17 at 15:46
  • \$\begingroup\$ These are all awesome finds. Thanks for taking the time to review. \$\endgroup\$ – user138440 Jun 8 '17 at 2:18
2
\$\begingroup\$

The design is overly complex. You gave some reasoning on your design decisions, nevertheless I want to raise some questions.

Design

The visitor pattern is intended to allow extension by implementing Visitors later on. This is very common for serializers, formatters and stuff like that. You could simply have an abstract reduce in your Cage. Another indicator for a design problem is the class of functions like kk_sub. They represent the actual constraint but are used by Cage and CageVisitor. Either you have a generic Cage without any specialisation that takes a constraint on construction or you have specialized Cages with internally hidden constraints. Cages should not only be responsible for evaluate but also for reduce which is in the visitors right now. On some of this predicates you even have different implementations in Cage and Visitor like kk_mul.

Naming

  • I would rename your CageVisitor to CageReducer because that is what it does. Same for the CellVisitor.
  • I had chosen Constraint or something similar instead of Cage.
  • the member holding the constraint shall not be named func but constraint or so.

Unit testing

  • kk_div would not pass any reasonable test
\$\endgroup\$
  • \$\begingroup\$ I disagree with the point about the design being overly complex. The reason I didn't add an abstract reduce function in the Cage code is so that I never have to couple the solver code with the representation code. I'd much rather pass this as a dependency. That way I can develop it independent of development work on the representation piece. How would you recommend handling the problem of evaluating multiple solver algorithms? Can you say more about why kk_div would fail "any reasonable test"? The naming change makes a lot of sense here. I agree with moving "visitor" to "reducer". \$\endgroup\$ – user138440 Jun 8 '17 at 2:15
  • \$\begingroup\$ kk_div([5,2],2) returns True \$\endgroup\$ – stefan Jun 8 '17 at 9:37
  • \$\begingroup\$ Ah that's a good catch. I like the definition for kk_div Ben has provided -- it should solve this problem. \$\endgroup\$ – user138440 Jun 8 '17 at 12:24
  • \$\begingroup\$ about reduce and solver. your solver is the backtracking algorithm. reduce has nothing to do with solving. there cannot be two opinions on reduce. every solver you try will use the very same reduce functions. \$\endgroup\$ – stefan Jun 8 '17 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.