Generalized Subtraction and Division

KenKen puzzles, as popularized in the U.S., have a major simplifying restriction: Subtraction and division cages must have exactly two cells. This restriction is lifted in some puzzle variants. Today, in response to a reader question, I briefly look at the problem of generalizing my solver to handle such puzzles.

An Example

See this puzzle for an example of 3+ cell subtraction and division. In particular, note that cells D1, E1, and E2 must form a quotient of 1, while cells D3, E3, and F3 must form a difference of 0.

What Does This Mean?

With 3+ cell subtraction or division, the cells are arranged in some order (in which the largest value comes first) and operators are placed between them. In the preceding example, this means that:

• (D1 / E1) / E2 = 1, or
• (E1 / D1) / E2 = 1, or
• (E2 / E1) / D1 = 1

and

• (D3 - E3) - F3 = 0, or
• (E3 - D3) - F3 = 0, or
• (F3 - E3) - D3 = 0

Note that alternative formulations, such as (D1 / E2) / E1 = 1, amount to reshufflings of terms, and may be ignored.

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 subtraction and division Constraints, 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.

We use the following rules to determine whether or not a given value might appear in a given cell of a subtraction cage:

• The candidate value may appear if a sum can be constructed from the values of the other cells equal to the candidate value less the cage’s value
• The candidate value may appear if a difference can be constructed from the values of the other cells equal to the sum of the candidate value and the cage’s value
• If neither of the first two cases applies, the candidate value may not appear in the cell

We use the following rules to determine whether or not a given value might appear in a given cell of a division cage:

• The candidate value may appear if a product can be constructed from the values of the other cells equal to the candidate value divided by the cage’s value
• The candidate value may appear if a quotient can be constructed from the values of the other cells equal to the product of the candidate value and the cage’s value
• If neither of the first two cases applies, the candidate value may not appear in the cell

The new Diff and Div constraints look like this:

class Diff(Constraint):
	def __init__(self, value, *cells):
		Constraint.__init__(self, value, *cells)
		if (len(self.cells) < 2): raise Exception('Diff constraints must be applied to 2 or more cells')
	def _test_component(self, component, context):
		return ((component>self.value) and can_make_sum_p(component-self.value, context)) or \
			   can_make_difference_p(self.value+component, context)

class Div(Constraint):
	def __init__(self, value, *cells):
		Constraint.__init__(self, value, *cells)
		if (len(self.cells) < 2): raise Exception('Div constraints must be applied to 2 or more cells')
	def _test_component(self, component, context):
		return ((not component%self.value) and can_make_product_p(component/self.value, context)) or \
			   can_make_quotient_p(self.value*component, context)

Helpers

We need two new helper functions, which test whether or not a difference or a quotient (respectively) can be made from a group of cells with certain possible values:

# Can we select exactly one member from each set s.t. the difference of all selected members is t?
d_diff_queries = {}
def can_make_difference_p(t, sets):
	if (len(sets) == 1): return (t in sets[0])
	r = d_diff_queries.get((t, sets))
	if (r == None):
		head = sets[0]; tail = sets[1:]
		r = any(can_make_sum_p(e-t, tail) for e in head if e > t) or \
			any(can_make_difference_p(t+e, tail) for e in head)
		d_diff_queries[(t, sets)] = r
	return r

# Can we select exactly one member from each set s.t. the quotient of all selected members is t?
d_quot_queries = {}
def can_make_quotient_p(t, sets):
	if (len(sets) == 1): return (t in sets[0])
	r = d_quot_queries.get((t, sets))
	if (r == None):
		head = sets[0]; tail = sets[1:]
		r =	any(can_make_product_p(e/t, tail) for e in head if not e%t) or \
			any(can_make_quotient_p(t*e, tail) for e in head)
		d_quot_queries[(t, sets)] = r
	return r

Code

A complete implementation can be downloaded here. It's based on the last version we discussed, which added support for puzzles with multiple solutions.

Efficiency

This is a somewhat naive implementation; for one thing, it ignores the fact that it's impossible to make a difference or a quotient larger than the puzzle size. Nevertheless, it does work, and illustrates how to generalize the solver to handle such problems.

Future Work

I'm continuing on with my recent work, then looking into widgets:

• Possibly deploy support for 3+ cell difference and quotient cages to the web-based KenKen solver
• Add more sites to the whitepaper
• Begin researching widgets

Weekend Stats

It's far too early to really say, but I think the new advertising approach is working a little better. These stats are pretty noisy, but when I dig into my Adwords stats, I'm seeing decent (6 or 7) Quality Scores, full budget utilization, and ~$0.25 CPC. The latter number is unsustainably high, of course, but let's worry about that later. More generally (and generalizing wildly), a whitepaper marketing approach seems to fit well with Adwords.

Follow Along

You can subscribe to my RSS feed, if you’d like to follow along with this month’s project, in which I attempt to create and popularize a puzzle site.