Essays/Kakuro
< Essays
Jump to navigation
Jump to search
Introduction
Kakuro カックロ is a numeric version of crossword puzzles and is also known as "cross sums". You can find out more about it at:
A Kakuro puzzle is here represented as a boxed matrix. Each box is either 'x' (an inactive square) or _ (a blank square) or has two numbers, which if nonzero indicates that the vertical entry below or the horizontal entry to the right must have that sum. (The first number is the vertical sum; the second number is the horizontal sum.) To solve a puzzle, fill the blank squares with numbers from 1 to 9 so that an entry contains no duplicate numbers and has the required sum.
For example, the puzzle depicted above would be represented as follows. Its solution is also shown.
x=. 'x' k0=: ".;._2 ] 0 : 0 x ; x ; x ; 6 0 ; 3 0 x ; 4 0 ; 3 3 ; _ ; _ 0 10 ; _ ; _ ; _ ; _ 0 3 ; _ ; _ ; x ; x ) k0 ┌────┬───┬───┬───┬───┐ │x │x │x │6 0│3 0│ ├────┼───┼───┼───┼───┤ │x │4 0│3 3│_ │_ │ ├────┼───┼───┼───┼───┤ │0 10│_ │_ │_ │_ │ ├────┼───┼───┼───┼───┤ │0 3 │_ │_ │x │x │ └────┴───┴───┴───┴───┘ kakuro k0 ┌────┬───┬───┬───┬───┐ │x │x │x │6 0│3 0│ ├────┼───┼───┼───┼───┤ │x │4 0│3 3│2 │1 │ ├────┼───┼───┼───┼───┤ │0 10│3 │1 │4 │2 │ ├────┼───┼───┼───┼───┤ │0 3 │1 │2 │x │x │ └────┴───┴───┴───┴───┘
A Kakuro Solver
NB. cross sums for x where y is list of lists of possible numbers for each column
csl=: 4 : 0
|: (#~ x = +/"1) (#~ *./@~:"1 *. x >: +/"1)@(,/)@:(,."0 _)&:>/ y
)
NB. joint possibilities for list of indices x and sums y
jposs=: 4 : 0
b=. (1+>./;x)#,:0 1 1 1 1 1 1 1 1 1 NB. possible numbers for each square
v=. i.#x
p=. (#x)$a:
for. i.#x do.
j=. v {~ (i.<./) */@({&(+/"1 b))&> v{x NB. index of entry with fewest est. possibilities
v=. v -. j NB. remove from future consideration
k=. j{::x NB. indices of squares of j-th entry
t=. (j{y) csl <@I."1 k{b NB. joint possibilities for j-th entry
b=. b k}~ (i.10) e."1 t NB. update lists of possible numbers
p=. p j}~ <t
end.
)
NB. x - indices of the squares in entries
NB. y - corresp. joint possibilities
NB. reduce joint possibilities by finding forced moves
force=: 4 : 0
j=. ; x
r=. (j *.//. ; (i.10)&e."1&.> y) (~.j)} ((1+>./j),10)$0
y (*./@({"_1) #"1 [)&.> {&r&.> x
)
NB. same arguments as "force"; find any and all solutions
solve=: 4 : 0 " 1
p=. x force^:_ y NB. reduce joint possibilities by forced moves
n=. {:@$&> p NB. # joint possibilities
if. 0 e. n do. (0,#y)$y return. end. NB. done if some square has no possibilities
if. *./1=n do. ,:p return. end. NB. done if found unique solution
j=. (i.<./) n+(1=n)*>./n NB. index of entry with smallest # possibilities > 1
; x <@solve p j}"0 1~ ('';1) <;.1 >j{p NB. fan out the joint possibilities of that entry
)
NB. indices of the squares in each entry and the required sums
entries=: 3 : 0
t=. (|.&.>,y),,|:y NB. make all entries horizontal
b=. t e. <_ NB. blank squares
p=. b<}.b,0 NB. starts of entries
i=. b #&.>&(p&(<;.1)) (i.*/$y),,|:i.$y NB. indices of squares of entries
s=. {.&> p#t NB. corresponding sums
i;s
)
NB. find all solutions of Kakuro puzzle y
kakuro=: 3 : 0
'i s'=. entries y
y (;i)"_}"1 2~ <"0@;"1 ,&.> i solve i jposs s
)
Sample Puzzles
x=. 'x' k1=: ".;._2 ] 0 : 0 NB. http://en.wikipedia.com/wiki/Kakuro x ; 23 0 ; 30 0 ; x ; x ; 27 0 ; 12 0 ; 16 0 0 16 ; _ ; _ ; x ; 17 24 ; _ ; _ ; _ 0 17 ; _ ; _ ; 15 29 ; _ ; _ ; _ ; _ 0 35 ; _ ; _ ; _ ; _ ; _ ; 12 0 ; x x ; 0 7 ; _ ; _ ; 7 8 ; _ ; _ ; 7 0 x ; 11 0 ; 10 16 ; _ ; _ ; _ ; _ ; _ 0 21 ; _ ; _ ; _ ; _ ; 0 5 ; _ ; _ 0 6 ; _ ; _ ; _ ; x ; 0 3 ; _ ; _ ) k2=: ".;._2 ] 0 : 0 NB. http://www.kakuro.com x ; 13 0 ; 34 0 ; x ; x ; x ; 34 0 ; 10 0 0 16 ; _ ; _ ; 29 0 ; x ; 28 8 ; _ ; _ 0 7 ; _ ; _ ; _ ; 10 9 ; _ ; _ ; _ 0 41 ; _ ; _ ; _ ; _ ; _ ; _ ; _ 0 29 ; _ ; _ ; _ ; _ ; _ ; _ ; _ x ; 0 7 ; _ ; _ ; 16 16 ; _ ; _ ; x x ; 11 0 ; 7 23 ; _ ; _ ; _ ; 21 0 ; 23 0 0 28 ; _ ; _ ; _ ; _ ; _ ; _ ; _ 0 12 ; _ ; _ ; _ ; 0 20 ; _ ; _ ; _ 0 4 ; _ ; _ ; x ; x ; 0 16 ; _ ; _ ) k3=: ".;._2 ] 0 : 0 NB. http://www.kakuropuzzle.com/challenge/12453-24281.gif x ; 6 0 ; 3 0 ; 9 0 ; 12 0 ; 12 0 ; x ; x ; x ; 21 0 ; 15 0 0 15 ; _ ; _ ; _ ; _ ; _ ; 7 0 ; x ; 0 5 ; _ ; _ 0 21 ; _ ; _ ; _ ; _ ; _ ; _ ; 3 0 ; 0 7 ; _ ; _ x ; x ; x ; 10 12 ; _ ; _ ; _ ; _ ; 11 3 ; _ ; _ x ; x ; 21 4 ; _ ; _ ; x ; 0 11 ; _ ; _ ; _ ; _ x ; 15 3 ; _ ; _ ; x ; x ; x ; 0 12 ; _ ; _ ; _ 0 10 ; _ ; _ ; _ ; 3 0 ; x ; x ; 10 7 ; _ ; _ ; x 0 10 ; _ ; _ ; _ ; _ ; 10 0 ; 9 5 ; _ ; _ ; x ; x 0 4 ; _ ; _ ; 0 10 ; _ ; _ ; _ ; _ ; 8 0 ; 3 0 ; 6 0 0 9 ; _ ; _ ; x ; 0 21 ; _ ; _ ; _ ; _ ; _ ; _ 0 10 ; _ ; _ ; x ; x ; 0 15 ; _ ; _ ; _ ; _ ; _ ) k4=: ".;._2 ] 0 : 0 NB. http://www.kakuro.com x ; x ; 38 0 ; 3 0 ; x ; 23 0 ; 4 0 ; 16 0 x ; 13 11 ; _ ; _ ; 29 18 ; _ ; _ ; _ 0 28 ; _ ; _ ; _ ; _ ; _ ; _ ; _ 0 16 ; _ ; _ ; 11 12 ; _ ; _ ; 22 0 ; 14 0 x ; 11 13 ; _ ; _ ; _ ; 4 14 ; _ ; _ 0 29 ; _ ; _ ; _ ; _ ; _ ; _ ; _ 0 15 ; _ ; _ ; 6 7 ; _ ; _ ; _ ; 5 0 x ; 6 0 ; 17 6 ; _ ; _ ; 12 4 ; _ ; _ 0 41 ; _ ; _ ; _ ; _ ; _ ; _ ; _ 0 13 ; _ ; _ ; _ ; 0 7 ; _ ; _ ; x ) k5=: ".;._2 ] 0 : 0 x ; x ; x ; 10 0 ; 13 0 ; 13 0 ; x ; x ; 10 0 ; 34 0 ; x ; 16 0 ; 11 0 ; x ; x ; 13 0 ; 10 0; 13 0 ; x ; x x ; 10 0 ; 8 21 ; _ ; _ ; _ ; x ; 14 6 ; _ ; _ ; 0 15 ; _ ; _ ; 9 0 ; 0 20 ; _ ; _ ; _ ; 5 0 ; 14 0 0 15 ; _ ; _ ; _ ; _ ; _ ; 13 23 ; _ ; _ ; _ ; 18 7 ; _ ; _ ; _ ; 12 16 ; _ ; _ ; _ ; _ ; _ 0 10 ; _ ; _ ; 9 0 ; 15 23 ; _ ; _ ; _ ; 0 19 ; _ ; _ ; _ ; 0 23 ; _ ; _ ; _ ; 16 0 ; 12 11 ; _ ; _ x ; 3 0 ; 41 23 ; _ ; _ ; _ ; _ ; 13 0 ; 6 13 ; _ ; _ ; _ ; 12 0 ; 4 22 ; _ ; _ ; _ ; _ ; 41 0 ; 6 0 0 13 ; _ ; _ ; _ ; _ ; 8 0 ; 38 30 ; _ ; _ ; _ ; _ ; _ ; _ ; _ ; 34 0 ; 17 24 ; _ ; _ ; _ ; _ 0 3 ; _ ; _ ; 11 0 ; 0 29 ; _ ; _ ; _ ; _ ; 23 0 ; 5 0 ; 34 14 ; _ ; _ ; _ ; _ ; x ; 9 3 ; _ ; _ x ; 0 7 ; _ ; _ ; 6 4 ; _ ; _ ; 4 0 ; 0 7 ; _ ; _ ; _ ; x ; 7 15 ; _ ; _ ; 5 15 ; _ ; _ ; x x ; 9 17 ; _ ; _ ; _ ; 14 6 ; _ ; _ ; 13 13 ; _ ; _ ; _ ; 7 5 ; _ ; _ ; 11 8 ; _ ; _ ; _ ; 15 0 0 7 ; _ ; _ ; 9 38 ; _ ; _ ; _ ; _ ; _ ; _ ; 7 38 ; _ ; _ ; _ ; _ ; _ ; _ ; 14 15 ; _ ; _ 0 23 ; _ ; _ ; _ ; 0 7 ; _ ; _ ; 0 17 ; _ ; _ ; _ ; _ ; _ ; 0 8 ; _ ; _ ; 0 10 ; _ ; _ ; _ 0 11 ; _ ; _ ; _ ; 0 14 ; _ ; _ ; x ; 0 23 ; _ ; _ ; _ ; x ; 0 10 ; _ ; _ ; 0 23 ; _ ; _ ; _ ) k6=: ".;._2 ] 0 : 0 x ; 24 0 ; 28 0 ; x ; 41 0 ; 7 0 0 8 ; _ ; _ ; 16 9 ; _ ; _ 0 34 ; _ ; _ ; _ ; _ ; _ 0 24 ; _ ; _ ; _ ; _ ; _ x ; 23 7 ; _ ; _ ; _ ; 14 0 0 34 ; _ ; _ ; _ ; _ ; _ 0 20 ; _ ; _ ; _ ; _ ; _ 0 14 ; _ ; _ ; 0 3 ; _ ; _ ) k7=: ".;._2 ] 0 : 0 NB. http://www.kakuroconquest.com puzzle 15375 x; 8 0 ; 11 0 ; 22 0 ; 6 0 ; x ; x ; 25 0 ; 13 0 ; 10 0 0 24 ; _ ; _ ; _ ; _ ; x ; 0 11 ; _ ; _ ; _ 0 14 ; _ ; _ ; _ ; _ ; 40 0 ; 11 24 ; _ ; _ ; _ x ; 27 0 ; 18 38 ; _ ; _ ; _ ; _ ; _ ; _ ; x 0 13 ; _ ; _ ; 16 0 ; 12 8 ; _ ; _ ; _ ; 21 0 ; 10 0 0 17 ; _ ; _ ; _ ; _ ; _ ; 13 0 ; 10 11 ; _ ; _ 0 45 ; _ ; _ ; _ ; _ ; _ ; _ ; _ ; _ ; _ 0 16 ; _ ; _ ; 24 0 ; 11 28 ; _ ; _ ; _ ; _ ; _ x ; x ; 13 7 ; _ ; _ ; _ ; 20 0 ;6 13 ; _ ; _ x ; 10 35 ; _ ; _ ; _ ; _ ; _ ; _ ; 6 0 ; 12 0 0 9 ; _ ; _ ; _ ; x ; 0 14 ; _ ; _ ; _ ; _ 0 24 ; _ ; _ ; _ ; x ; 0 24 ; _ ; _ ; _ ; _ )
The following examples shows k2 and its solution. Intermediate values are included to demonstrate that k2 can be solved using forced moves alone.
k2
┌────┬────┬────┬────┬─────┬────┬────┬────┐
│x │13 0│34 0│x │x │x │34 0│10 0│
├────┼────┼────┼────┼─────┼────┼────┼────┤
│0 16│_ │_ │29 0│x │28 8│_ │_ │
├────┼────┼────┼────┼─────┼────┼────┼────┤
│0 7 │_ │_ │_ │10 9 │_ │_ │_ │
├────┼────┼────┼────┼─────┼────┼────┼────┤
│0 41│_ │_ │_ │_ │_ │_ │_ │
├────┼────┼────┼────┼─────┼────┼────┼────┤
│0 29│_ │_ │_ │_ │_ │_ │_ │
├────┼────┼────┼────┼─────┼────┼────┼────┤
│x │0 7 │_ │_ │16 16│_ │_ │x │
├────┼────┼────┼────┼─────┼────┼────┼────┤
│x │11 0│7 23│_ │_ │_ │21 0│23 0│
├────┼────┼────┼────┼─────┼────┼────┼────┤
│0 28│_ │_ │_ │_ │_ │_ │_ │
├────┼────┼────┼────┼─────┼────┼────┼────┤
│0 12│_ │_ │_ │0 20 │_ │_ │_ │
├────┼────┼────┼────┼─────┼────┼────┼────┤
│0 4 │_ │_ │x │x │0 16│_ │_ │
└────┴────┴────┴────┴─────┴────┴────┴────┘
kakuro k2
┌────┬────┬────┬────┬─────┬────┬────┬────┐
│x │13 0│34 0│x │x │x │34 0│10 0│
├────┼────┼────┼────┼─────┼────┼────┼────┤
│0 16│7 │9 │29 0│x │28 8│7 │1 │
├────┼────┼────┼────┼─────┼────┼────┼────┤
│0 7 │1 │4 │2 │10 9 │2 │4 │3 │
├────┼────┼────┼────┼─────┼────┼────┼────┤
│0 41│2 │7 │6 │9 │5 │8 │4 │
├────┼────┼────┼────┼─────┼────┼────┼────┤
│0 29│3 │8 │5 │1 │4 │6 │2 │
├────┼────┼────┼────┼─────┼────┼────┼────┤
│x │0 7 │6 │1 │16 16│7 │9 │x │
├────┼────┼────┼────┼─────┼────┼────┼────┤
│x │11 0│7 23│8 │9 │6 │21 0│23 0│
├────┼────┼────┼────┼─────┼────┼────┼────┤
│0 28│2 │4 │3 │7 │1 │5 │6 │
├────┼────┼────┼────┼─────┼────┼────┼────┤
│0 12│6 │2 │4 │0 20 │3 │9 │8 │
├────┼────┼────┼────┼─────┼────┼────┼────┤
│0 4 │3 │1 │x │x │0 16│7 │9 │
└────┴────┴────┴────┴─────┴────┴────┴────┘
'i s'=: entries k2
$ i
26
$ s
26
i NB. indices of the squares of each entry
┌────┬─────┬────────┬────────┬────────────────────┬────────────────────┬─────┬
│9 10│14 15│17 18 19│21 22 23│25 26 27 28 29 30 31│33 34 35 36 37 38 39│42 43│ ...
└────┴─────┴────────┴────────┴────────────────────┴────────────────────┴─────┴
s NB. corresponding sums
16 8 7 9 41 29 7 16 23 28 12 20 4 16 13 11 34 7 29 10 16 28 34 21 10 23
p=: i jposs s
$&.> p
┌───┬───┬───┬────┬────┬────┬───┬───┬───┬────┬────┬───┬───┬───┬───┬────┬───┬───┬
│2 2│2 6│3 6│3 18│7 18│7 48│2 6│2 2│3 2│7 16│3 10│3 5│2 2│2 2│4 4│3 10│5 4│3 2│ ...
└───┴───┴───┴────┴────┴────┴───┴───┴───┴────┴────┴───┴───┴───┴───┴────┴───┴───┴
p NB. initial joint possibilities
┌───┬───────────┬───────────┬───────────────────────────────────┬───────────────
│7 9│1 2 3 5 6 7│1 1 2 2 4 4│1 1 1 1 2 2 2 2 3 3 3 3 4 4 5 5 6 6│2 2 2 2 2 2 2 2
│9 7│7 6 5 3 2 1│2 4 1 4 1 2│2 3 5 6 1 3 4 6 1 2 4 5 2 3 1 3 1 2│7 7 7 7 7 7 8 8
│ │ │4 2 4 1 2 1│6 5 3 2 6 4 3 1 5 4 2 1 3 2 3 1 2 1│6 6 8 8 9 9 6 6 ...
│ │ │ │ │8 9 6 9 6 8 7 9
│ │ │ │ │5 5 5 5 5 5 5 5
│ │ │ │ │9 8 9 6 8 6 9 7
│ │ │ │ │4 4 4 4 4 4 4 4
└───┴───────────┴───────────┴───────────────────────────────────┴───────────────
NB. # of joint possibilities after each iteration
{:@$&> i force^:a: p
2 6 6 18 18 48 6 2 2 16 10 5 2 2 4 10 4 2 144 8 2 48 8 8 18 2
1 2 2 4 10 48 1 1 1 16 5 3 1 1 1 4 2 2 144 4 1 6 2 2 6 1
1 1 1 3 2 4 1 1 1 8 4 1 1 1 1 2 1 2 6 4 1 4 2 1 4 1
1 1 1 3 1 4 1 1 1 3 2 1 1 1 1 2 1 2 2 1 1 4 1 1 1 1
1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 2 1 1 1 1 1 4 1 1 1 1
1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
A Kakuro puzzle may have more than one solution. For example:
k3
┌────┬────┬────┬─────┬────┬────┬────┬────┬────┬────┬────┐
│x │6 0 │3 0 │9 0 │12 0│12 0│x │x │x │21 0│15 0│
├────┼────┼────┼─────┼────┼────┼────┼────┼────┼────┼────┤
│0 15│_ │_ │_ │_ │_ │7 0 │x │0 5 │_ │_ │
├────┼────┼────┼─────┼────┼────┼────┼────┼────┼────┼────┤
│0 21│_ │_ │_ │_ │_ │_ │3 0 │0 7 │_ │_ │
├────┼────┼────┼─────┼────┼────┼────┼────┼────┼────┼────┤
│x │x │x │10 12│_ │_ │_ │_ │11 3│_ │_ │
├────┼────┼────┼─────┼────┼────┼────┼────┼────┼────┼────┤
│x │x │21 4│_ │_ │x │0 11│_ │_ │_ │_ │
├────┼────┼────┼─────┼────┼────┼────┼────┼────┼────┼────┤
│x │15 3│_ │_ │x │x │x │0 12│_ │_ │_ │
├────┼────┼────┼─────┼────┼────┼────┼────┼────┼────┼────┤
│0 10│_ │_ │_ │3 0 │x │x │10 7│_ │_ │x │
├────┼────┼────┼─────┼────┼────┼────┼────┼────┼────┼────┤
│0 10│_ │_ │_ │_ │10 0│9 5 │_ │_ │x │x │
├────┼────┼────┼─────┼────┼────┼────┼────┼────┼────┼────┤
│0 4 │_ │_ │0 10 │_ │_ │_ │_ │8 0 │3 0 │6 0 │
├────┼────┼────┼─────┼────┼────┼────┼────┼────┼────┼────┤
│0 9 │_ │_ │x │0 21│_ │_ │_ │_ │_ │_ │
├────┼────┼────┼─────┼────┼────┼────┼────┼────┼────┼────┤
│0 10│_ │_ │x │x │0 15│_ │_ │_ │_ │_ │
└────┴────┴────┴─────┴────┴────┴────┴────┴────┴────┴────┘
t=: kakuro k3
$ t
40 11 11
NB. that is, there are 40 solutions
(0{t) = 1{t
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 0 0
1 1 1 1 1 1 1 0 1 0 0
_2 _4 {. 0{t
┌─┬─┬─┬─┐
│1│5│2│4│
├─┼─┼─┼─┤
│4│3│1│2│
└─┴─┴─┴─┘
_2 _4 {. 1{t
┌─┬─┬─┬─┐
│4│5│1│2│
├─┼─┼─┼─┤
│1│3│2│4│
└─┴─┴─┴─┘
Kakuro Combinations
Kakuro combinations can be generated by selecting combinations of 1+i.9 that have the required sum.
comb=: 4 : 0 NB. All size x combinations of i.y k=. i.>:d=.y-x z=. (d$<i.0 0),<i.1 0 for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end. ; z ) kc=: ((= +/"1) # ]) >:@comb&9
comb is from the for. page of the dictionary; x kc y generates all combinations of size y that sum to x .
18 kc 4 1 2 6 9 1 2 7 8 1 3 5 9 1 3 6 8 1 4 5 8 1 4 6 7 2 3 4 9 2 3 5 8 2 3 6 7 2 4 5 7 3 4 5 6
See also
Contributed by Roger Hui.