Essays/KenKen
Introduction
KenKen (賢賢) is a numeral-logical puzzle invented by Japanese educator Tetsuya Miyamoto in 2004, as described in http://www.nytimes.com/2009/02/09/arts/09ken.html
kk0 kk1
Fill the n-by-n grid with the digits 1 to n so that each digit appears once in each row and each column. The digits within each cage (heavily outlined box) must produce the target numbers shown, using the indicated operation addition, subtraction, multiplication, or division. If no operation is indicated then the target number is just reproduced as is. The digits in a cage can be in any order.
Input
Here, a KenKen puzzle is specified as a string of lines ending in LF or CRLF , with each line describing a cage: the target number, the operation symbol (if any), and the cells in the cage. The cells in an n-by-n grid are numbered as i.n,n . For example, the puzzle kk0 diagrammed above can be entered as:
kk0=: 0 : 0 1,0 11+,1 2 5 6 4+,3 7 8*,4 8 9 1-,10 11 7+,12 13 2%,14 15 )
The verb triplets converts the input into a 3-column matrix of boxes, with one row per cage. Each row has the target number, the operation symbol as a single character, and the sorted list of indices of the cells in the cage. (triplets also checks the input for consistency.)
For example:
triplets kk0 ┌──┬─┬───────┐ │1 │ │0 │ ├──┼─┼───────┤ │11│+│1 2 5 6│ ├──┼─┼───────┤ │4 │+│3 7 │ ├──┼─┼───────┤ │8 │*│4 8 9 │ ├──┼─┼───────┤ │1 │-│10 11 │ ├──┼─┼───────┤ │7 │+│12 13 │ ├──┼─┼───────┤ │2 │%│14 15 │ └──┴─┴───────┘
Initial Possibilities
The verb init computes a list of initial possibilities from the table of triplets, by applying n init1 y independently for each cage, where y is the triplet for that cage. The possibilities for a cage are an integer table.
If the operation symbol is blank, then the cage is necessarily a singleton and the "possibilities" are an 1-by-1 matrix of the target number.
Otherwise, let f be the indicated operation. init1 starts with the table >,{m$<1+i.n of all possible tuples (rows) of size m , where m is the number of cells in the cage. Then it discards tuples y for which f/y does not equal the target number (- or % cages are tested for +./target=f/"1 (i.!m) A. y), then tuples for which the digits in a row or a column of the grid are not distinct.
The possibilities for a cage are yoked for all the cells in that cage. As the computation proceeds, elimination is on entire tuples, so that the possibilities remained yoked. The possibilities totally capture the indicated operations and target numbers, so that they need not be referenced any further. (That is, only the last column of the 3-column table of triplets is needed any further.)
t=: triplets kk0
c=: {:"1 t
c ,: init t
┌─┬───────┬───┬─────┬─────┬─────┬─────┐
│0│1 2 5 6│3 7│4 8 9│10 11│12 13│14 15│
├─┼───────┼───┼─────┼─────┼─────┼─────┤
│1│1 3 3 4│1 3│1 2 4│1 2 │3 4 │1 2 │
│ │1 4 4 2│3 1│1 4 2│2 1 │4 3 │2 1 │
│ │2 3 4 2│ │2 1 4│2 3 │ │2 4 │
│ │2 4 3 2│ │2 4 1│3 2 │ │4 2 │
│ │2 4 4 1│ │4 1 2│3 4 │ │ │
│ │3 1 4 3│ │4 2 1│4 3 │ │ │
│ │3 2 2 4│ │ │ │ │ │
│ │3 4 1 3│ │ │ │ │ │
│ │4 1 2 4│ │ │ │ │ │
│ │4 2 1 4│ │ │ │ │ │
│ │4 2 2 3│ │ │ │ │ │
│ │4 3 3 1│ │ │ │ │ │
└─┴───────┴───┴─────┴─────┴─────┴─────┘
Algorithms
Three different solvers are presented:
- KenKenD , a direct method
- KenKenM , merging cages
- KenKen , elimination and "guessing"
Of these, KenKenM appears to be the best, being fast and short and easy to describe and understand.
For all three methods, failure to find a solution means that the input puzzle does not have a solution.
Direct Method
From the list of initial possibilities, a direct method obtains readily for finding the solution: Select the Latin square from the rank-3 array of all possible combinations of the possibilities. For example:
c=: {:"1 t=: triplets kk0
p=: init t
#&> p
1 12 2 6 6 2 4
*/ #&> p
6912
$ q=: 4 4 $"1 (;&> , { <"1&.> p) /:"1 ;c
6912 4 4
<"2 q
┌───────┬───────┬───────┬───────┬───────┬───────┬───────┬
│1 1 3 1│1 1 3 1│1 1 3 1│1 1 3 1│1 1 3 1│1 1 3 1│1 1 3 1│
│1 3 4 3│1 3 4 3│1 3 4 3│1 3 4 3│1 3 4 3│1 3 4 3│1 3 4 3│...
│2 4 1 2│2 4 1 2│2 4 1 2│2 4 1 2│2 4 1 2│2 4 1 2│2 4 1 2│
│3 4 1 2│3 4 2 1│3 4 2 4│3 4 4 2│4 3 1 2│4 3 2 1│4 3 2 4│
└───────┴───────┴───────┴───────┴───────┴───────┴───────┴
q #~ (4$15) ((-:"1 +/"1) * (-:"1 +/"2)) q{0,2^i.4
1 2 4 3
4 3 2 1
2 1 3 4
3 4 1 2
The direct method is codified as the verb KenKenD (see Collected Definitions). The method is impractical for larger puzzles (for example, the number of all possible combinations for kk1 is 3.88178e13 = */ #&> init triplets kk1), for which more parsimonious techniques are required.
The direct method does illustrate the point that the solution is contained within the list of possibilities. All the manipulations described in this text preserve this property.
Merging
Starting with the initial possibilities, merge cages together two at a time into larger cages until only one remains. Merging cages consists of generating all combinations of the possibilities, then discarding the combinations with duplicate entries in a row or column. Thus:
n=: 4
t=: triplets kk0
] d=: (<n,n) #:&.> {:"1 t
┌───┬───┬───┬───┬───┬───┬───┐
│0 0│0 1│0 3│1 0│2 2│3 0│3 2│
│ │0 2│1 3│2 0│2 3│3 1│3 3│
│ │1 1│ │2 1│ │ │ │
│ │1 2│ │ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┘
] p=: init t
┌─┬───────┬───┬─────┬───┬───┬───┐
│1│1 3 3 4│1 3│1 2 4│1 2│3 4│1 2│
│ │1 4 4 2│3 1│1 4 2│2 1│4 3│2 1│
│ │2 3 4 2│ │2 1 4│2 3│ │2 4│
│ │2 4 3 2│ │2 4 1│3 2│ │4 2│
│ │2 4 4 1│ │4 1 2│3 4│ │ │
│ │3 1 4 3│ │4 2 1│4 3│ │ │
│ │3 2 2 4│ │ │ │ │ │
│ │3 4 1 3│ │ │ │ │ │
│ │4 1 2 4│ │ │ │ │ │
│ │4 2 1 4│ │ │ │ │ │
│ │4 2 2 3│ │ │ │ │ │
│ │4 3 3 1│ │ │ │ │ │
└─┴───────┴───┴─────┴───┴───┴───┘
(1{d,.p) merge 2{d,.p
┌───┬───────────┐
│0 1│1 4 4 2 3 1│
│0 2│2 3 4 2 1 3│
│1 1│2 4 3 2 3 1│
│1 2│2 4 4 1 1 3│
│0 3│3 2 2 4 1 3│
│1 3│4 1 2 4 3 1│
│ │4 2 1 4 1 3│
│ │4 2 2 3 3 1│
└───┴───────────┘
In the initial possibilities for kk0 , cage 1 has 12 possibilities and cage 2 has 2 possibilities. When the two cages are merged, there is an intermediate result of 24 possibilities (all combinations), which are then pared down to 8 by removing duplicates in rows 0 and 1.
This method is codified as the verb KenKenM (see Collected Definitions).
mcounts=: 3 : 0
n=. %:#;c=. {:"1 t=. triplets y
p=. init t
q=. merge/\. ((<n,n) #:&.> c) ,. p
(#&> {:"1 q) ,.&|. */\. #&> p
)
mcounts&.> kk0;kk1;kk2;kk3
┌───────┬──────────────┬───────────────┬───────────────┐
│ 4 4│ 10 10│ 2 2│ 8 8│
│ 8 4│ 80 52│ 14 8│ 80 44│
│ 48 16│ 320 100│ 140 42│ 320 112│
│ 288 12│ 4160 146│ 280 36│ 4480 580│
│ 576 4│ 74880 162│ 11200 110│ 17920 548│
│6912 1│ 748800 506│ 134400 42│ 143360 648│
│6912 1│ 4.4928e6 212│ 5.2416e6 178│ 286720 660│
│ │ 4.4928e7 70│ 3.14496e7 151│ 6.88128e6 656│
│ │ 8.9856e7 78│ 3.14496e8 46│ 9.63379e7 1932│
│ │ 8.9856e7 60│ 5.66093e9 255│ 5.78028e8 376│
│ │ 8.9856e8 60│3.39656e10 154│ 4.62422e9 64│
│ │ 5.39136e9 62│1.35862e11 154│6.47391e10 288│
│ │4.31309e10 24│1.52166e13 108│6.47391e11 648│
│ │4.31309e11 18│2.40422e15 636│7.76869e12 728│
│ │6.46963e12 4│3.36591e16 1187│9.32243e13 312│
│ │3.88178e13 1│2.01954e17 868│3.35607e15 1944│
│ │3.88178e13 1│1.61564e18 948│3.35607e15 920│
│ │ │9.69381e18 356│6.71215e15 272│
│ │ │3.87752e19 44│1.34243e16 104│
│ │ │2.32651e20 29│ 1.8794e17 172│
│ │ │1.20979e22 2│1.12764e18 68│
│ │ │4.06489e24 1│1.12764e18 24│
│ │ │4.06489e25 1│6.76585e18 40│
│ │ │2.43893e26 1│1.35317e19 24│
│ │ │ │4.60077e20 8│
│ │ │ │2.76046e21 2│
│ │ │ │1.07658e23 1│
│ │ │ │2.15316e23 1│
│ │ │ │8.61265e23 1│
│ │ │ │1.03352e25 1│
└───────┴──────────────┴───────────────┴───────────────┘
mcounts on a KenKen puzzle produces a 2-column table of numbers where row i is the number of all possibilities for the first 1+i cages, followed by the actual number of possibities after merging. (The first number on the last row is the number of possibilities the direct method would have to contend with, before its single elimination step.) These numbers illustrate the efficacy of merging. They also show that merging is probably not a good method for solving KenKen puzzles by hand.
Elimination and "Guessing"
This method is similar to the one used to solve Sudoku, viz.,
- Eliminate possibilities using a simple deductive rule.
- "Guess" by fanning out the cage with the smallest number of possibilities.
The two steps are repeated until a solution is found.
Eliminations
If all the possibilities for a cage for a row (column) are permutations of the same digits, then the other cells in that row (column) can not use those digits. (The cage may have other cells not on that row (column); those other cells do not affect the elimination logic.) Examples of this can be found in the initial possibilities for puzzle kk0 :
- The possibilities for cage 3 7 (labeled 4+) are 1 3 and 3 1 in column 3. This means that the other cells in column 3 can not use 1 or 3.
- The possibilities for cage 12 13 (labeled 7+) are 3 4 and 4 3 in row 3. This means that the other cells in row 3 can not use 3 or 4.
- Singleton cages are special case: The possibilities for cage (0) are 1 in row 0 or column 0. This means that the other cells in row 0 or column 0 can not use 1.
The adverb elim performs this elimination, with 0 elim doing row eliminations and 1 elim column eliminations. In either case, elim discovers which subsets of cages have the requisite property, then performs the eliminations for those subsets.
The verb eliminate incorporates elim to do row and column eliminations repeatedly, until no more eliminations are possible.
"Guessing"
"Guessing" is used if one application of eliminate does not find a solution (for example for the larger and harder puzzles kk2 and kk3). By guessing, we mean fanning out the i-th cage of a list of possibilities y into a matrix of possibilities, viz., y i}"0 1~ <"2 ,:"1 i{::y .
For example, suppose the list of possibilities is:
┬───┬─────┬─────┬───┬─────┬─────┬ │3 1│4 5 7│1 2 6│3 6│8 6 7│3 4 8│ │ │5 4 7│2 1 6│4 1│8 7 6│3 5 7│ ...│ │5 7 4│2 6 1│4 7│ │4 3 8│... │ │7 5 4│6 2 1│5 2│ │4 5 6│ │ │ │ │5 8│ │5 3 7│ │ │ │ │ │ │5 4 6│ ┴───┴─────┴─────┴───┴─────┴─────┴
And the cage whose possibilities are 8 6 7 and 8 7 6 is fanned out. The result would be:
┬───┬─────┬─────┬───┬─────┬─────┬ │3 1│4 5 7│1 2 6│3 6│8 6 7│3 4 8│ │ │5 4 7│2 1 6│4 1│ │3 5 7│ │ │5 7 4│2 6 1│4 7│ │4 3 8│ │ │7 5 4│6 2 1│5 2│ │4 5 6│ │ │ │ │5 8│ │5 3 7│ │ │ │ │ │ │5 4 6│ ...┼───┼─────┼─────┼───┼─────┼─────┼... │3 1│4 5 7│1 2 6│3 6│8 7 6│3 4 8│ │ │5 4 7│2 1 6│4 1│ │3 5 7│ │ │5 7 4│2 6 1│4 7│ │4 3 8│ │ │7 5 4│6 2 1│5 2│ │4 5 6│ │ │ │ │5 8│ │5 3 7│ │ │ │ │ │ │5 4 6│ ┴───┴─────┴─────┴───┴─────┴─────┴
Elimination followed by guessing is repeated on each list of possibilities, until a solution is found.
As far as arriving at a solution, it does not matter which of the cages with more than one possibility is fanned out. The heuristic implemented here is to select the largest of the cage(s) with the fewest possibilities. It is possible that another heuristic, such as fanning out the largest of the cages(s) with the largest number of possibilities, would lead to a more efficient solver, but we have not investigated those alternative heuristics.
This method is codified as the verb KenKen (see Collected Definitions).
Collected Definitions
NB. KenKen aka KenDoku aka Mathdoku aka Calcudoku
triplets=: 3 : 0
assert. (1=#$y)*.2=3!:0 y NB. literal list
assert. *./y e. '0123456789,+-*% ',CRLF
q=. <;._2 y-.CR NB. box each line
assert. 1=+/&(','&=)&>q NB. each line contains a single comma
m=. q i.&>',' NB. index of comma in each line
l=. m {.&.> q NB. labels
b=. *./@(e.&'0123456789')&>l
assert. b+.({:&>l)e.'+-*%' NB. label is a number, or a number followed by +-*%
t=. _1&".&>(b-1)}.&.>l NB. target numbers
p=. (#b){.,(b-1){.&>l NB. operations
assert. 0<t
d=. ; c=. (1+m) /:~@,@(_1&".)@}.&.> q NB. cell numbers for cages
assert. (2=#&>c)>:p e. '-%' NB. - or % cages must have 2 cells
assert. (1=#&>c)>:p=' ' NB. blank cages must have 1 cell
assert. (#d) e. *: 1+i.9 NB. 1-by-1, 2-by-2, ... , 9-by-9
assert. (i.#d) e. d
n=. < 1 _1, 1 _1 * <.%.#d NB. neighbors
assert. *./&> (c+/&.>n) +./"1@e.&.> c NB. cells are connected
c /:~ (<"0 t),.(<"0 p),.c
)
NB. n init1 y -- initial possibilities for one cage
NB. y : the triplet (target, operation, cells) for one cage
init1=: 4 : 0
't p c'=. y
m=. #c
select. p
case. ' ' do. 1 1$t return.
case. '+' do. q=. (#~ t=+/"1) >,{m$<1+i.x
case. '*' do. q=. (#~ t=*/"1) >,{m$<((0=|&t) # ]) 1+i.x
case. '-' do. q=. (#~ [: +./"1 t = [: -/"1 ((i.!m)A.i.m) {"_ 1 ]) >,{(#c)$<1+i.x
case. '%' do. q=. (#~ [: +./"1 t = [: %/"1 ((i.!m)A.i.m) {"_ 1 ]) >,{(#c)$<1+i.x
end.
j=. , (|:(x,x)#:c) </."1 i.m NB. group by row and column indices
j=. j #~ 1<#&>j NB. groups with > 1 elements
q #~ */ j */@~:"1@:({"1)&> <q NB. cells in a group must be unique
)
init=: <.@%:@#@;@({:"1"_) <@init1"1 ] NB. initial possibilities from matrix of triplets
KenKenD=: 3 : 0 NB. Direct method; impractical for larger puzzles
n=. %:#d=. ; {:"1 t=. triplets y
q=. (,~n) $"1 d /:"1~ ;&> , { <"1&.> init t
q #~ (n$<:2^n) ((-:"1 +/"1)*(-:"1 +/"2)) q{0,2^i.n
)
NB. Merge two cages x and y, each is a pair of boxes ...
NB. ... ((m,2)-table of coordinates ; m-column table of possibilities)
merge=: 4 : 0
'j0 p0'=. x NB. coordinates and possibilities for x
'j1 p1'=. y NB. coordinates and possibilities for y
j=. j0,j1 NB. merge coordinates
p=. ((#p1)#p0),.(p0*&#p1)$p1 NB. all combinations of the two possibilites
c=. (|:j) </."1 i.#j NB. columns in p on the same grid row/column
b=. (|:j) (2=#@~.)/."1 (j0,&#j1)#0 1 NB. which of them come from both x and y?
p=. p #~ */ (b#&,c) */@~:@({"1)&> <p NB. remove combos on same row/column having duplicate entries
j;p
)
KenKenM=: 3 : 0
n=. %:#;c=. {:"1 t=. triplets y
'd z'=. merge/((<n,n)#:&.>c),.init t
assert. 1=#z
(n,n)$(,z)/:d
)
mcounts=: 3 : 0
n=. %:#;c=. {:"1 t=. triplets y
p=. init t
q=. merge/\. ((<n,n) #:&.> c) ,. p
(#&> {:"1 q) ,.&|. */\. #&> p
)
same=: 1&=@(+/)@~:
NB. eliminations from single row (m=0) or single column (m=1) cages
NB. x: cages; boxed indices from 0 to (n*n)-1
NB. y: corresponding to x, matrices of possible answers
elim=: 1 : 0
:
n=. <.%:# ;x
d=. (+/\@(|.!.0) (+i.)&.> ]) #&> x
i=. m&{"1@((n,n)&#:)&.> x NB. row/column numbers
e=. ; i </.&.> d NB. indices of caged single row/column
w=. e |:@:>@:{&.> < ; <"1@|:&.> y NB. corresp. cell values
z=. y
for_c. e #~ same@(/:~"1"_)&> w do.
k=. 1 i.~ d +./@e.&> c NB. index of cage of interest
b=. (k{::d) e. >c NB. columns of interest in cage k
v=. b#{.k{::z NB. cell values for the single row/column
u=. ({.b#k{::i)+n*k=i.#x NB. don't do cage k itself
z=. z #&.>~ -.@:(+./"1)@:(e.&v)&.> (i=&.>u) #"1&.> z
end.
)
eliminate=: ([ (0 elim) (1 elim))^:_ " 1
guessa=: 3 : 0
p=. */k=. {."1 s=. $&> y
if. p e. 0 1 do. (p,$y)$y return. end. NB. some cage has 0 poss., or all have 1 poss.
i=. {. /: (1=k),.1 _1*"1 s NB. pick the largest of the cages with the fewest poss.
y i}"0 1~ <"2 ,:"1 i{::y NB. each guess has a single possibility for that cage
)
guess=: 3 : 0
if. +./b=. */"1 ] 1 = #&> y do. NB. has a solution been found?
b#y NB. sol'n is found
else.
; <@guessa"1 y NB. sol'n not yet found; fan out each list of possibilities
end.
)
KenKen=: 3 : 0
c=. {:"1 t=. triplets y
z=. guess @ (c & eliminate) ^:_ ,: init t
assert. 1=#z
assert. 1=#&>z
(,~@%:@# $ ]) (,&.>,z) /:&; c
)
Sample Puzzles
NB. this is the 4-by-4 puzzle in the diagram above kk0=: 0 : 0 1,0 11+,1 2 5 6 4+,3 7 8*,4 8 9 1-,10 11 7+,12 13 2%,14 15 ) NB. this is the 6-by-6 puzzle in the diagram above kk1=: 0 : 0 3,0 3-,1 7 8+,2 3 8 1-,4 5 36*,6 12 13 2%,9 10 1-,11 17 5,14 5-,15 16 1-,18 24 3-,19 20 1-,21 22 9+,23 29 35 24*,25 30 31 6*,26 32 2-,27 28 1-,33 34 ) kk2=: 0 : 0 36*,0 1 2 3-,3 4 672*,5 6 7 15 23 25+,8 16 24 25 5-,9 17 3%,10 11 8+,12 13 9+,14 22 5-,18 26 1-,19 27 22+,20 21 28 29 13+,30 31 39 47 3%,32 40 140*,33 34 35 9+,36 37 38 3-,41 49 21+,42 43 44 15+,45 46 54 2-,48 56 13+,50 57 58 7-,51 59 3-,52 60 144*,53 61 62 15*,55 63 ) kk3=: 0 : 0 60*,0 1 9 5+,2 3 7-,4 5 12+,6 7 14 11+,8 16 16+,10 17 18 15*,11 19 7+,12 20 7,13 5-,15 23 1-,21 22 7-,24 25 42*,26 27 2,28 12+,29 30 31 2-,32 33 2-,34 35 3-,36 37 1-,38 39 2%,40 41 35*,42 50 58 1-,43 44 17+,45 53 61 30*,46 47 4-,48 49 4%,51 59 1-,52 60 3%,54 55 3-,56 57 2%,62 63 ) KenKen kk0 1 2 4 3 4 3 2 1 2 1 3 4 3 4 1 2 KenKen kk1 3 2 6 1 4 5 6 5 1 4 2 3 2 3 5 6 1 4 5 1 4 2 3 6 4 6 2 3 5 1 1 4 3 5 6 2 KenKen kk2 2 6 3 5 8 4 1 7 8 3 2 6 7 1 5 4 5 8 1 2 3 7 4 6 7 5 6 3 4 8 2 1 3 7 5 4 1 2 6 8 1 4 8 7 6 5 3 2 6 1 4 8 2 3 7 5 4 2 7 1 5 6 8 3 KenKen kk3 6 5 3 2 8 1 7 4 4 2 8 5 6 7 1 3 7 6 2 3 1 5 4 8 8 1 6 7 2 4 3 5 1 3 4 6 5 2 8 7 2 4 1 8 7 3 5 6 3 7 5 1 4 8 6 2 5 8 7 4 3 6 2 1
See also
Contributed by Roger Hui.