On the way to school yesterday an interesting question occurred to me. How many ways are there to arrange the numbers 1, 2, 3, 4 in a 4×4 grid according to KenKen rules? After driving a few more miles, I came up with “the answer” of 288. I shared this with my first class of the morning; unfortunately, at the end of my presentation I realized that my answer was wrong.
My analysis: Looking at the first row of the 4×4 grid, there are 4 ways to fill in the first square, but only 3 ways to choose the second number, 2 ways to pick the third number, and finally, only 1 way to fill in the last square. This is 4!, a common result in permutations.
Then the trouble started. There are certainly 3 ways to fill the first square in the second row since you cannot duplicate the number above it. But then I mistakenly thought that there were only 2 ways to choose the number for the second square since you could not repeat the numbers above and to the left. But in KenKen it can be possible for these numbers to be the same. OOPS!
So sometimes there are only 2 ways to choose a number for the second spot in row 2, and sometimes there are 3 ways. At this point the problem became more interesting and challenging. It seems that someone must have solved this problem already. I’ve emailed two KenKen sites, and so far received one reply which agrees with my second solution of 3,456 ways. But I’m not convinced this is the correct answer either.
I tried to contact Will Shortz, Puzzle Editor of the New York Times, but had no luck finding his email address. If any readers have a solution to this conundrum, please post a Comment to help us out.
To receive all new posts – subscribe via email or RSS Web Feed.
Related posts:
Do you have a conference or staff development activity coming up? Find out why you should book me to speak by
This is a hard question – I’m not sure how to solve it.
At first, I thought 3,456 was correct too. But during lunch today, I think there are actually less than 3,456 possible puzzles (ignoring cages and math operations).
Here’s my logic:
Starting with a simpler problem and building from there:
1×1 grid = 1
1
2×2 grid = 2
2 * 1
where:
12 or 21
21 12
3×3 grid = 12
6 * 2 * 1
where:
row 1 row 2 row 3
123 <- xxx xxx(1)
132 xxx(1) xxx(1)
213 xxx(3) xxx(3)
231 231 <- xxx
312 312 312
321 xxx(2) xxx(2)
note, the numbers in () indicate why the arrangement was removed
4×4 grid = 864
24 * 9 * 4 * 1
row 1 : 24 permutations
row 2 : 9 permutations remain (after removing column conflicts)
row 3 : 4 permutations remain (after removing column conflicts)
row 4 : 1 permutation remains (after removing column conflicts)
So there you have it, I think there are 864 different possible puzzles in a 4×4 grid.
That didn’t turn out right, it looks like my comment lost some of its formatting. Let’s try it one more time:
At first, I thought 3,456 was correct too. But during lunch today, I think there are actually less than 3,456 possible puzzles (ignoring cages and math operations).
Here's my logic:
Starting with a simpler problem and building from there:
1x1 grid = 1
1
2x2 grid = 2
2 * 1
where:
12 or 21
21 12
3x3 grid = 12
6 * 2 * 1
where:
row 1 row 2 row 3
123 <- xxx xxx(1)
132 xxx(1) xxx(1)
213 xxx(3) xxx(3)
231 231 <- xxx
312 312 312
321 xxx(2) xxx(2)
note, the numbers in () indicate why the arrangement was removed
4x4 grid = 864
24 * 9 * 4 * 1
row 1 : 24 permutations
row 2 : 9 permutations remain (after removing column conflicts)
row 3 : 4 permutations remain (after removing column conflicts)
row 4 : 1 permutation remains (after removing column conflicts)
So there you have it, I think there are 864 different possible puzzles in a 4x4 grid.
NOTE: This comment is the text of an email from Ken to Mr. L and is posted here with Ken’s permission.
Bill,
Great question!
I’ve never thought about it, but at first guess, I thought it would be 331,776 different arrangements of 1, 2, 3, 4, or 24^4.
That seemed far too large. On second look, I noticed that does not account for repeat values within each row, so I thought the answer might be 24!/20! or 255,024.
But that also seemed too large. A final third and closer look resulted in an interesting number in itself, 3,456 unique arrangements.
Here’s my reasoning:
4 3 2 1
3 | 3 2 1
2 | 2 | 2 1
1 | 1 | 1 | 1
- “corner 1″ : formed from row 1 and column 1 = 4!3! = 144
- “corner 2″ : formed from row 2 and column 2 (excluding corner 1) = 3!2! = 12
- “corner 3″ : formed from row 3 and column 3 (excluding corners 1 and 2) = 2!1! = 2
- “corner 4″ : formed from row 4 and column 4 (excluding corners 1, 2, and 3) = 1! = 1
144 * 12 * 2 * 1 = 3,456
How’s that? I don’t know if it’s right or wrong, but that’s the answer I came up with. Let me know what you think.
Ken
NOTE: This comment is the text of an email from Ken to Mr. L and is posted here with Ken’s permission.
After thinking about this more, I was not convinced either and suspected the number was less than previously thought. I did some research on “latin squares”, the foundation of kenken (and sudoku) and found that for a 4×4 grid, there are 576 unique arrangements.
http://en.wikipedia.org/wiki/Latin_square
http://mathworld.wolfram.com/LatinSquare.html
But, I am not sure on the math that leads to 576. If you can shed some light on the solution, please share.
Thanks.
btw, I created a new “load” game that should be more intuitive. If you can, please take a look and let me know what you think.
http://www.webkendoku.com/load.php
Ken
I find this exchange fascinating. It catches the mind and gets one thinking at several layers. Part of the problem is that the puzzle is not clearly stated, leading to multiple interpretations. If anyone is interested in similar mental exercises, you can try reading “Increase Your Brain Power”, which was just released and includes a few chapters with puzzles on this level (plus both simpler and more complicated puzzles).
[...] have the solution to the KenKen Conundrum posed recently. I asked my students to solve the following problem, and several of them succeeded. [...]
The really intersting bit is the third row. The first row has 4! =24 permutions. The second row has 9 permissable permutations for each permutaion on the first row. The 9 can be arrived at by counting the “bad” cases. Exactly one permutation would be indentical to the first row, 8 would have exactly one conflict and 6 would have exactly 6 conflicts with the first row. Subtracting 1+6+8=15 from the total of 4!=24 permutations for the second row leaves the 9 permissable permutations for the second row.
Now based on column conflicts alone, there are 2 possible values for each value in the third row, meaning that there are 16 possible permutations that would not violate the column restrictions. 24*9*16 = 3456, Mr. L’s initial answer. However, you might see that intuitively this doesn’t make much sense, since row 3 would have more permuations than row two, despite having more constraints – this answer does not consider the row restrictions in row 3!
So let’s consider what is known about row 3. We know the fourth element is defined by the first 3, so only has one possibility. We know the first element in the row only has column restraints so has 2 possible values for each permutation of rows 1 and 2.
Element 2 of row 3 can have 1 or 2 possible values depending on the columnn restraints from row 1 and 2 and the row restraint provided by the first element in row 3. Similarly, element 3 can have 0 (over constrainted), 1 or 2 possibilities depending on the column restraints of row 1 and 2 and the row restraints of the first two elements in row 3. By inspection I saw that 3 of the permissable permuations for row 2 would result in 4 permissable permutations in row 3, while the other 6 permuations in row 2 would only result in 2 permissable permuations in row 3 (i.e. the row is full specified by the first element). So the total number of permutations for a 4×4 Ken Ken is (24*3*4)+(24*6*2)=576
Crystal was right on the money through the first two rows. Things get complicated in row 3 though. For some choices of permutations in row 2, there are 4 valid permutations for row 3. For other choices of permutations in row 2, there are only 2 valid permutations in row 3. As it turns out, of the 9 valid choices of permutations for row 2, 3 will lead to 4 valid permutations of row 3, while the remaining 6 permutations of row 2 will only lead to 2 valid permutations of row 3. I didn’t have any insight to leap to the previous point – just did it by inspection. So the total number of valid permutations of a 4×4 ken ken is 24*[(6*2)+(3*4)] = 24*24 = 576.
According to wikipedia there is not a general solution to this problem for a nxn square – and 4×4 is about the last case where it is feasible to work it out in a few minutes.
Finally, I found a web site which tackles the problem I have been working on – thank you.
For Ken Ken squares of size 2×2, 3×3, and 4×4, I find 2, 12, and 864 possibilities, respectively. So, I agree with a number of your responders. My goal was to work this out for 6×6, but at present I have not even finished the 5×5 case. The bigger the NxN value the more branch points there are, and there does not seem to be any obvious pattern to it that you can write down. I would like to see the formula for NxN if anybody knows it. It would be very hard to get it by empirical extrapolation from the three cases I solved.
P. Kunasz
The problem can be generalized, if you understand how a kenken field is built. First you fill the field with numbers in a simple scheme:
Say our field is 3×3
123
312
231
After that you shuffle the vertical lines and you get something like that:
231
123
312
After that you shuffle the horizontal lines:
312
231
123
You now have a random kenken. For each operation you have 3! possibilities. The total permutations of a 3×3 kenken is thereby (3!)^2
And to generalise it for a n*n kenken:
(n!)^2
cheers,
wintix
RESULTS OF A COLLEAGUE’S FORTRAN PROGRAMBELOW. 4X4 CASE ALSO CHECKED BY HAND, BOTH IN THE ABSTRACT, AND GRID-BY-GRID. GOING BEYOND THESE CASES GETS INTO DOUBLE, THEN QUADRUPLE PRECISION COMPUTER INSTRUCTIONS BECAUSE THE RESULT BLOWS UP SO RAPIDLY. SO,HAS ANYONE FOUND A GENERAL EXPRESSION?
RESULTS OF CODE:
Grid size (n): 2
Number of grids: 2
Grid size (n): 3
Number of grids: 12
Grid size (n): 4
Number of grids: 576
Grid size (n): 5
Number of grids: 161280
Grid size (n): 6
Number of grids: 812851200
Grid size (n): 7
Number of grids: 61479419904000
This might be the number of arrangements for the underlying numbers but they do not represent the added complexity of the pattern of cages. It is not addressing the question of how many KenKen puzzles there are.
For a 4×4 KenKen we would need to multiply 576 by the number of valid cage patterns and also realize each cage can have one of 4 mathematical operators.
Might want to start with the 3×3…
Zytheran,
Paul K’s answer gives ALL the possible combinations, regardless of cages, since the rules of how the numbers can be arranged in the grid will still apply. The cages and the operations they contain simply guide the player with number placement. These are determined by the KenKen Generator Programs after the numbers have been filled, and depend on a difficulty level. The possible combinations of numbers that may be chosen from is quite limited to the grid’s size, as explained by several contributors to this thread. Perhaps you would enjoy rewriting the code for one if actually playing has ceased to be diverting.
A KenKen grid, before cages, is called by mathematicians a Latin square. The problem of counting the number of NxN Latin squares is still unsolved. The results of the computer program above are correct up to N=7. Look up “Latin squares” in Wikipedia for more information.
extrapolation puzzle
if 7+6 = 113 and
9+1= 810 and
5+3 = 28 and
9+6 = 315 then what does 7+2 = ?
The answer to the extrapolation puzzle is 59. The first digit is 7 – 2, the next digit is 7+2.