Kenken-friendly numbers

I messed up a kenken the other day, carelessly forgetting that 2, 3, 4 and 6 are not the only divisors of 12. Later, mulling over my mistake, I realized that it’s the presence of the multiplicative identity that gives a kenken puzzle much of its combinatorial variety. If we played kenken without 1′s, the three-cell “cage” below would have only the single solution shown.

Three-cell cage labeled 12x, with unique solution 2 x 3 x 2

But because 1 is included in the set of candidate numbers, the cage could also be filled in with various permutations of 1 × 3 × 4 and 1 × 2 × 6, thereby increasing the entropy of the puzzle.

[For those of you who don't fritter away enough of your time on the puzzles page at the back of the newspaper, here's a kenken résumé. You are given a k × k grid to be filled in with the integers from 1 through k, observing certain constraints. Each integer must appear exactly once in each column and each row (thus making the grid a Latin square). And the numbers within each thickly outlined cage must combine to produce the target number in the upper left corner of the cage, using the operation shown there (+, –, × or ÷). For the noncommutative and nonassociative operations, the requirement is merely that some ordering of the operands yields the target value.]

If having the multiplicative identity among the candidate numbers makes the puzzle more interesting, an obvious idea is to include the additive identity as well. This would be easy to arrange: Just shift from the set {1, 2, …, k} to the set {0, 1, …, k–1}. Then a target value of 3+ would no longer have the unique solution 1 + 2; it could also be 0 + 3. Moreover, a target value of 0× would be a kind of wild card, with very high entropy indeed!

Other sets of candidate numbers might produce even harder (and weirder) puzzles. How about a 5 × 5 kenken with the set {–2, –1, 0, 1, 2}? Or, venturing a little farther afield, we might try a 4 × 4 puzzle with the candidates {1, –1, i, –i}.

a complex kenken, with candidate set {1, -1, i, -i}

(Roll your mouse over the grid above to see a valid solution—but I’m not at all sure the solution is unique or that it can be found by a purely deductive process. At best this is a jokenken.)

Looking in the opposite direction, certain candidate sets should lower the entropy of the system and thus can be expected to make the puzzle easier. In particular, a grid to be filled in only with prime numbers would have unambiguous solutions (except for order) in all multiplicative cages. (If we stick with the convention that target values are always integers, there could be no division cages in such a puzzle.)

Following up on this line of thought, I began to wonder about candidate sets for which all operations would yield unambiguous results. If we choose any two distinct numbers from such a set, and combine them with any of the kenken operations +, –, ×, ÷, we would get a result different from what we would see with any other pair of numbers or any other operation. Do such sets exist? Yes, an example is {2, 8, 10, 11}, for which the four arithmetic operations yield these results:

operation tables for kenken candidate set {2, 8, 10, 11}

Following kenken convention, we take only numbers from the lower triangle of each table, and in the case of division we ignore any noninteger quotient. Thus the full set of results are the numbers circled in red. It’s easy to see there are no duplicated values. Sorted by magnitude, the set is: {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 16, 18, 19, 20, 21, 22, 80, 88, 110}.

A cute property of such sets is that they allow the construction (and solution!) of kenken puzzles like this one:

six-by-six kenken to be solved with numbers from the set {2,8,22,27,29,30}; mouseover for solution

Note that the target values in the cages do not indicate which operation is to be performed. There’s no need to specify an operator, because each of the target values can be generated in only one way from the set of numbers given. If a set allows such an operatorless puzzle grid, I’m going to call it a kenken-friendly set, or a kkf set.

[According to Wikipedia, operatorless kenkens are nothing new:

More complex KenKen problems are formed ... omitting the symbols +, −, × and ÷, thus leaving them as yet another unknown to be determined.

I've never seen such a kenken in the wild. Are they based on kenken-friendly sets of the kind defined here? I rather doubt it if the puzzles are meant to be harder than normal. (The example above is quite easy.)]

A few things I know about kenken-friendly sets:

  1. No kkf set can include either 0 or 1 among its members.
  2. No three elements of a kkf set can form an arithmetic progression. It follows that if {m, …, n} is a kkf set of k elements, then nm is at least k(k–1)/2. (Let’s call this the minimum span of the set.)
  3. Every kkf set defines a Golomb ruler, a set of integers in which all differences are unique. But of course only some Golomb rulers also satisfy the constraints that sums, products and quotients be unique.
  4. Among sets made up entirely of small numbers, kkf sets are rare, but when you select sets of k integers from the range [1, n], and n is much larger than k, nearly every set has the kkf property.

proportion of random sets that have the kkf property for k = 4 to 8

A few things I don’t know about kenken-friendly sets:

  1. For each value of k, what are the smallest kkf sets?
  2. Before we can address question 1, we have to answer this: What is the best measure of size in a kkf set? In sets of the form {m, …, n}, should we work to minimize m, minimize n, or perhaps minimize the span from m to n? Or maybe the right measure is the sum or product of all the elements of the set? (This question doesn’t come up for Golomb rulers, where it’s customary to set m=0, then look for the set with the smallest n, which is designated the optimal ruler for a given k.)
  3. One way to search for small kkf sets is to take a known Golomb ruler {0, … n}, then slide it along the number line, adding a constant c to each element. This preserves Golomb-ruler-ness, and at each c you can test for kkf-ness. The question is: Does every Golomb ruler become a kkf set for some finite value of c? The answer is yes for the 35 known optimal Golomb rulers, and I have not found a counterexample among various larger rulers. (I’ve tried a sampling of those listed by James B. Shearer.) But I have no clue to a proof, one way or the other.
  4. The special treatment of division in these sets may make sense for a puzzle printed in the newspaper, but mathematically it’s a bit of a wart. There’s no good rationale for accepting quotients when they happen to be integers and ignoring them otherwise. So what’s the proper formulation of the problem? Should we open the door to the whole field of rational numbers? Or, on the contrary, should we exclude division altogether and just work with +, – and ×? Another option is to replace division with the remainder operation. (This last approach looks intriguing. Sets that have all-unique sums, products, differences and remainders seem to be rare, but they do exist. One example is {3, 6, 16, 47}, which yields the result set {0, 1, 2, 3, 4, 5, 9, 10, 13, 15, 18, 19, 22, 31, 41, 44, 48, 50, 53, 63, 96, 141, 282, 752}).
  5. Have all these questions been answered already, perhaps in some other context?

Finally, some data. Here are a few small (by some measure) kkf sets, along with the result sets they generate from the operations {+, –, ×, ÷}:

k=4:

{2, 8, 9, 11} ⇒ {1, 2, 3, 4, 6, 7, 9, 10, 11, 13, 16, 17, 18, 19, 20, 22, 72, 88, 99}
{3, 6, 10, 11} ⇒ {1, 2, 3, 4, 5, 7, 8, 9, 13, 14, 16, 17, 18, 21, 30, 33, 60, 66, 110}
{4, 6, 9, 10} ⇒ {1, 2, 3, 4, 5, 6, 10, 13, 14, 15, 16, 19, 24, 36, 40, 54, 60, 90}
{5, 6, 9, 11} ⇒ {1, 2, 3, 4, 5, 6, 11, 14, 15, 16, 17, 20, 30, 45, 54, 55, 66, 99}

k=5:
{2, 5, 13, 18, 19} ⇒ {1, 3, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 23, 24, 26, 31, 32, 36, 37, 38, 65, 90, 95, 234, 247, 342}
{9, 11, 16, 19, 20} ⇒ {1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 20, 25, 27, 28, 29, 30, 31, 35, 36, 39, 99, 144, 171, 176, 180, 209, 220, 304, 320, 380}}

k=6:
{2, 3, 17, 19, 26, 29} ⇒ {1, 2, 3, 5, 6, 7, 9, 10, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 31, 32, 34, 36, 38, 43, 45, 46, 48, 51, 52, 55, 57, 58, 78, 87, 323, 442, 493, 494, 551, 754}
{7, 11, 13, 16, 23, 24} ⇒ {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 16, 17, 18, 20, 23, 24, 27, 29, 30, 31, 34, 35, 36, 37, 39, 40, 47, 77, 91, 112, 143, 161, 168, 176, 208, 253, 264, 299, 312, 368, 384, 552}
{13, 17, 19, 22, 29, 30} ⇒ {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 16, 17, 30, 32, 35, 36, 39, 41, 42, 43, 46, 47, 48, 49, 51, 52, 59, 221, 247, 286, 323, 374, 377, 390, 418, 493, 510, 551, 570, 638, 660, 870}}

k = 7:
{6, 13, 17, 18, 27, 33, 35} ⇒ {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 27, 29, 30, 31, 33, 35, 39, 40, 41, 44, 45, 46, 48, 50, 51, 52, 53, 60, 62, 68, 78, 102, 108, 162, 198, 210, 221, 234, 306, 351, 429, 455, 459, 486, 561, 594, 595, 630, 891, 945, 1155}

This entry was posted in featured, games, mathematics.

12 Responses to Kenken-friendly numbers

  1. AlanM says:

    I’m pretty sure that Kenken also requires that a number not be repeated within a cage either, which renders some of your earlier examples invalid (but not, I think, your kkfs).

  2. brian says:

    @AlanM: No such rule in the kenkens I waste my time on (published in the Boston Globe, copyrighted by “KENKEN PUZZLE”). The 3 x 2 x 2 cage above is from one of those puzzles.

  3. unekdoud says:

    There’s an interesting parallel with an insert-operator puzzle:
    Given a set of numbers, add binary operators and (optionally) permute the set so that the result comes out to a target.
    The analogous question in that case is what the initial set of numbers should be to maximize the number of possible targets. I believe the best way to start is also to look at Golomb rulers. However, the calculations are slightly more complicated.

    If the cages in Kenken are allowed to have repeated numbers, then the diagonal elements for the addition and multiplication tables should be considered. (Subtraction and division cages always contain two distinct numbers, so the diagonal elements don’t come into play there.)

    Is a Golomb ruler sliding algorithm the best way to find kkf sets? Could a greedy algorithm get the same results?

    Also, I like the idea of Kenken over non-integer rings (for instance, a Kenken mod 7 would have no issues with division). It might be hard to find non-mathematician players though.

  4. Barry Cipra says:

    Suppose we try to “grow” a kkf set using a greedy algorithm starting with 2 and 3 and always adding the smallest possible positive integer. If I’ve done all the arithmetic correctly, the sequence starts

    2,3,5,19,31,49,….

    For example, the starting numbers 2 and 3 produce the result set {1,5,6} (1=3-2, 5=2+3, 6=2×3), so you can’t take 4 for the next number since 4-3=1 (or, for that matter, 4+2=6), but 5 is OK, since it introduces new results {2,3,7,8,10,15}. For the next term, we rule out everything through 18:

    6+2=5+3
    7-2=2+3
    8+2=2×5
    9-3=2×3
    10-2=3+5
    11-3=3+5
    12-2=2×5
    13-3=2×5
    14/2=2+5 (note, this is the first time division necessarily comes into play)
    15/3=2+3
    16/2=3+5
    17-2=3×5
    18/3=2×3

    But 19 expands the results set with 9 distinct new numbers:

    {14,16,17,21,22,24,38,57,95}.

    If 31 and 49 are also the correct next terms, then the results set to that point omits only the numbers

    4,9,11,13,19,20,23,25,27,31,32,35,37,…

    Some or all of these may eventually wind up in the results set as the greedy algorithm extends the kkf set, but it’s also possible that some may never wind up as results.

  5. brian says:

    unekdoud writes:

    If the cages in Kenken are allowed to have repeated numbers, then the diagonal elements for the addition and multiplication tables should be considered.

    Numbers can repeat only in cages that include at least three cells. I’ve considered only pairwise kkf sets. Extending the search to the third dimension looks arduous and messy. As you point out, it would have to include the matrix diagonals. (Or some of them. We allow a * a * b but not a * a * a.)

    Is a Golomb ruler sliding algorithm the best way to find kkf sets? Could a greedy algorithm get the same results?

    Neither the Golomb sliderule algorithm nor the greedy algorithm that Barry Cipra submitted generates all the kkf sets. Exhaustive search is the only way I know to find them all, or to find the smallest ones (for some reasonable definition of smallest).

  6. brian says:

    Barry Cipra writes:

    Suppose we try to “grow” a kkf set using a greedy algorithm starting with 2 and 3 and always adding the smallest possible positive integer. If I’ve done all the arithmetic correctly, the sequence starts

    2,3,5,19,31,49,….

    I’ve calculated some more elements of the sequence:

    2, 3, 5, 19, 31, 49, 86, 109, 118, 183, 254, 293, 379, 424, 443, 509,
    572, 603, 814, 922, 1085, 1231, 1307, 1431, 1695, 1751, 1982, 2221,
    2415, 2655, 2939, 3058, 3071, 3757, 3805, 4109, 4337, 4558, 5137,
    5466, 5568, 6208, 6524, 6689, 7419, 7899, 8129, 8482, 8554, 9394, 9537

    It’s not in the OEIS; somebody should submit it.

    The result set for the kkf set above has 3,860 elements and begins

    1, 2, 3, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23, 24, 26, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 43, 44, 45, 46, 47, 48, 50,…

    Thus some of the missing elements you noted have now shown up, but some haven’t.

    A further question:

    I tried applying your construction using the remainder (or modulo) operation instead of division. Curious result. The sequence starts a little differently: {2, 3} doesn’t work because 3 mod 2 = 3 – 2. But {2, 4} is okay (result set {0, 2, 6, 8}). The third element of the set is 11 (result set {0, 1, 2, 3, 6, 7, 8, 9, 13, 15, 22, 44}). I have searched up to 10^6 and not found a fourth element. Is there anything beyond {2, 4, 11}?

  7. Barry Cipra says:

    Brian, if I understand correctly what you’re doing with remainders instead of division, then it seems clear there’s no fourth element. As soon as you add 4, you’ve precluded all other even numbers, since 2N mod 2 = 4 mod 2 = 0, and as soon as you add 11, you’ve precluded all other odd numbers, since 2N+1 mod 2 = 11 mod 2 = 1.

    As for the numbers that remain “missing in action” from the results set (it looks like it’s down to 4,11,20,25,27,40,41,42,49,….), cool! My guess is that eventually everything’ll be picked up (I see 9 bit the dust at 118-109, and 13 joined the results set at 3071-2058), but it may take a long time.

  8. brian says:

    Aha! Thank you, Barry.

    And so it follows that all such sets are finite. If m is the smallest element of the set, then we can have at most m+1 elements before we run out of congruence classes.

  9. David Nacin says:

    With your jokenken, the solution is indeed unique and can be found by a deductive process.

    1. If a product of two distinct numbers from your set is -1 then the numbers must be -1 and 1. This means i or -i must be in row two column one.

    2. To solve abc=d for d in the set, there is one solution with a=b=c, one with a,b,c all different and two others.

    3. Looking at these possibilities for abc=i we can work our way clockwise around the board from row two column one. The entries will be completely determined based on whether we put -1,1 or 1,-1 in the times -1 box. Then you can see that only one of the initial choices works out.

    I think complex number KenKen is a great idea. I wish there was a website for them.

  10. mathgrant says:

    I’d like to point out that Thomas Snyder (http://motris.livejournal.com/tag/kenken/calcudoku) has done a LOT of experimentation with Ken-Ken, including one that uses the set {1, 2, 4, 7, 14, 28}, several in which the operations aren’t given (so 12 could be 12+, 12-, 12*, or 12/), and even one where you’re not told which clue goes with which region. His handmade puzzles easily put the Ken-Ken puzzles in a newspaper to shame.

  11. brian says:

    @mathgrant: Great stuff! Thanks for the link.

    Another reader has pointed me to the PyKen project (http://code.google.com/p/pyken/#), which includes facilities for generating puzzles based on the Gaussian integers and other variants that are likely to appeal to the mathematically bent.

  12. Jim Ward says:

    I wonder what the current computer kenken limit is. What the largest grid that can be solved by a bit-player reader’s PC?