No-op KenKen Solver

A popular KenKen variant is the “no-op” puzzle, in which only the result of a cage is given. (In “standard” KenKen, both the result and an operator are given.) A reader wrote in with a question about a no-op puzzle, so I took a look at extending my Python solver to handle this variant. It turned out to be pretty easy.

An Example

Here’s an example of a 4×4 no-op puzzle. I’m using the notation I developed earlier, with the minor extension that “?” represents an unknown operator.

# 4
? 3 A1 A2
? 5 A3 A4
! 3 B1
? 8 B2 B3 B4
? 2 C2 C3
? 7 C4 D4
? 6 D1 D2 D3

This looks something like:

+----+----+----+----+
|3        |5        |
|         |         |
+----+----+----+----+
|3   |8             |
|    |              |
+----+----+----+----+
|    |2        |7   |
|    |         |    |
+----+----+----+    +
|6             |    |
|              |    |
+----+----+----+----+

Constraints

Our solver uses constraints to answer the following question:

Given what we know (or assume) about the puzzle, is it possible, under any set of circumstances, for a given value to appear in a given cell?

We answer this question, for the mathematical Constraints we’ve seen so far, with a _test_component() member function, which takes as its arguments the component to be tested, and a tuple of tuples of all other possible values in the cage, grouped by cell. Each type of Constraint has its own version of this function, customized for the Constraint‘s mathematical operation.

We can handle no-op cages in much the same way, by asking a more liberal question; instead of asking whether the _test_component() function associated with a particular operation would permit a given value in a given cell, we ask whether the _test_component() function associated with any operation would permit the value to appear.

Code

I began with the last version of the solver that I published (in this article), moved a little code around, and added a new constraint. The new no-op constraint looks like this:

class Noop(Constraint):
	def __init__(self, value, *cells):
		Constraint.__init__(self, value, *cells)
		if (len(self.cells) < 2): raise Exception('Noop constraints must be applied to 2 or more cells')
	def _test_component(self, component, context):
		return self._test_component_sum(component, context)	or \
	               self._test_component_diff(component, context)	or \
		       self._test_component_prod(component, context)	or \
		       self._test_component_div(component, context)

You can also download the complete latest version of the solver here.