Essays/KenKen

From J Wiki
Jump to: navigation, search

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

KenKen0.gif     KenKen.gif

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.