Following up on yesterday’s post, I’d like to get started on the construction of a solver for KenKen puzzles, using the same basic constraint-propogation-and-search approach that Norvig used in his Sudoku solver. I’m going to begin with a discussion of the role of constraints in the KenKen solver.
Usage
Since our approach will involve the production and refinement of partial solutions, constraints will be used to eliminate possible values from partial solutions. For instance, if a constraint specifies that the sum of three cells must equal 5, then we can eliminate from consideration any solution which places a value greater than 3 in any of those cells.
We will represent (partial) solutions as dictionaries mapping cell IDs to collections of possible cell values. Constraints will be represented as objects with an “apply” method, which will take a partial solution dictionary, and return a “bad” dictionary indicating which possible values should be removed from the partial solution. This “bad” dictionary will map cell IDs to collections of known impossible cell values.
Example
Perhaps a code snippet showing how constraints will be used might make the concept clearer:
def constrain(solution, *constraints):
queue = set(constraints)
while (queue):
constraint = queue.pop()
for cell, bad_choices in constraint.apply(solution).items():
values = solution[cell]
for choice in bad_choices:
values = values.replace(choice, '')
if (not values):
return False
if (solution[cell] == values):
continue
solution[cell] = values
queue.update(d_constraints[cell])
return solutionThis code takes a partial solution and a list of (potentially) violated constraints. Each constraint is applied to the solution, and any known bad values are removed. Any constraints associated with changed cells are, in turn, applied to the new solution, since the changed cells might give rise to additional constraint violations.
Coming Attractions
Tomorrow we will implement all the constraint classes.
Legal Notes
“KenKen” is a registered trademark. The people behind the game clearly intend to create a Sudoku-like frenzy for these puzzles, thereby enhancing the value of their trademark, from which they aim to profit. I wish them all the luck in the world with that plan. For my part, I wish to make clear that I am, and my (emerging) solver is, in no way associated with official KenKen-brand products. To the extent that I use the term “KenKen” as an adjective, it should be understood to mean “compatible with products or puzzles produced by the holder of the trademark name ‘KenKen'”.
