Solver for KenKen puzzles (Constraints)

Today I’m going to show the Constraint implementation for a KenKen solver I’m building. This code will cover all the rules of the KenKen game, and will shortly be used in a constraint propogation and search algorithm. It contains several inefficiencies, which will be dealt with later.

Commonalities

KenKen has 6 different types of constraints:

• The arithmetic constraints: Addition, Subtraction, Multiplication, and Division
• The uniqueness constraints on rows and columns
• Assertion constraints, which set particular cells to particular values

Since four of these constraints will probably require similar logic, let’s define a common base class which offers support for them:

class Constraint(object):
	def __init__(self, value, *cells):
		self.cells	= set(cells)
		self.value	= int(value)
	def _test_component(self, component, context):
		return True
	def apply(self, solution):
		d_sets = dict((c, map(int, solution[c])) for c in self.cells); d_bad = {}
		for k,v in d_sets.items():
			others = [ov for ok,ov in d_sets.items() if ok != k]
			d_bad[k] = ''.join(str(e) for e in v if not self._test_component(e, others))
		return d_bad

This class stores a constraint value (an integer) and a set of IDs (strings) of the cells to which the constraint will be applied.

The apply() method of this class will take a partial solution, represented as a dictionary, and return a dictionary of all values which are incompatible with the constraint. (Both dictionaries have strings representing cell IDs as keys, and strings representing sets of numbers as values.) The _test_component() method will be overridden by subclasses, and tests whether or not a given integer may be used to satisfy the constraint, given all possible values of all other cells governed by the constraint. (Those “all possible values of all other cells” are represented by context: a list of lists of integers.)

Addition and Multiplication

The Addition and Multiplication constraints can be implemented with simple overrides of Constraint._test_component():

class Sum(Constraint):
	def _test_component(self, component, context):
		return (self.value>=component) and can_make_sum_p(self.value-component, context)

class Prod(Constraint):
	def _test_component(self, component, context):
		return (not self.value%component) and can_make_product_p(self.value/component, context)

Sum._test_component() requires that the component being tested be less that the constraint’s value, and that it be possible to total up some combination of the possible values of the constraint’s other cells to the difference between the constraint’s value and that component.

Similarly, Prod._test_component() requires that the component being tested be a factor of the constraint’s value, and that it be possible to multiply up some combination of the possible values of the constraint’s other cells to the quotient of the constraint’s value and that component.

Each of these methods requires a helper function:

# Can we select exactly one member from each set s.t. the sum of all selected members is t?
def can_make_sum_p(t, sets):
    if (not sets): return (t == 0)
    head = sets[0]; tail = sets[1:]
    return any(can_make_sum_p(t-e, tail) for e in head if e <= t)

# Can we select exactly one member from each set s.t. the product of all selected members is t?
def can_make_product_p(t, sets):
    if (not sets): return (t == 1)
    head = sets[0]; tail = sets[1:]
    return any(can_make_product_p(t/e, tail) for e in head if not t%e)

These functions answer questions which, I'm pretty sure, are variations of the Multiple-Choice Knapsack Problem, which I recall as being in NP. So, they're not particularly efficient; more on that in the days ahead.

Subtraction and Division

The Subtraction and Division constraints are in some sense simpler than Addition and Multiplication, since they are always applied to exactly two cells. On the other hand, these operations are not commutative:

class Diff(Constraint):
	def __init__(self, value, *cells):
		Constraint.__init__(self, value, *cells)
		if (len(cells) != 2): raise Exception('Diff constraints must be applied to pairs of cells')
	def _test_component(self, component, context):
		return (self.value+component in context[0]) or (component-self.value in context[0])

class Div(Constraint):
	def __init__(self, value, *cells):
		Constraint.__init__(self, value, *cells)
		if (len(cells) != 2): raise Exception('Div constraints must be applied to pairs of cells')
	def _test_component(self, component, context):
		return (self.value*component in context[0]) or (float(component)/self.value in context[0])

Both classes have special constructors, which ensure that the constraints are being applied to the proper number of cells. Both classes have _test_component() methods which check the component's cell's counterpart for either of the two values which, taken together with the component's value, will satisfy the constraint.

Assertion

The Assertion constraint just sets a cell to a value.

class Assert(Constraint):
	def apply(self, solution):
		return dict((c, solution[c].replace(str(self.value), '')) for c in self.cells)

The Assertion constraint overrides Constraint.apply(), and flags every value other than the constraint's value as bad.

Uniqueness

This constraint requires that any value appear at most once in a set of cells.

class Set(Constraint):
	def apply(self, solution):
		# For each cell:
		d_bad = {}
		for c in self.cells:
			# If a cell has only one possible value, remove that value from all other cells
			if (len(solution[c]) != 1): continue
			for c2 in self.cells:
				if (c2 != c): d_bad[c2] = d_bad.get(c2,'') + solution[c]
		return d_bad

The Uniqueness constraint overrides Constraint.apply(), and flags as bad any re-occurance of a value which appears alone in a cell's list of possible values.

Coming Attractions

Tomorrow we will address input and output: The representation of KenKen puzzles in human-and-machine readable format, and the display of solutions.

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’”.