Following the post by J.C. Coez to the forum on July 28 (with a subject of "Diagonal generalization"), I looked into the Kakuro puzzles that he mentioned. Kakuro is a numeric version of crossword puzzles and is also known as "cross sums". You can find out more about it from: http://www.kakuropuzzle.com http://en.wikipedia.com/wiki/Kakuro
The following J program solves Kakuro puzzles. A puzzle is represented as a boxed matrix. Each box is either 'x' or _ (indicating a blank square) or has two numbers, which if nonzero indicates that the following vertical or horizontal "entry" must have that sum. (First number is vertical sum; second number is horizontal sum.) To solve a puzzle, fill the blank squares with digits from 1 to 9 so that an entry contains no duplicate digits and has the required sum. A Kakuro puzzle is supposed to have a unique solution, but this is not always true. See the k1 puzzle below. As this e-mail interface seems to be making a hash of long-ish lines, I will shortly put the program up on the Wiki, probably http://www.jsoftware.com/jwiki/Essays/Kakuro ------------------------------------------- NB. find vectors of length x of distinct digits 1-9 such that y=+/v cs=: 4 : 0 if. 0>:x do. i.0 0 elseif. 1= x do. y $~ ((0<y)*.y<:9),1 elseif. 1 do. (*./@~:"1 # ]) ; j ,.&.> (x-1) cs&.> y-j=. 1+i.9 end. ) NB. x - indices of rows/columns NB. y - corresp. joint possibilities NB. reduce joint possibilities by finding forced moves force=: 4 : 0 j=. ; x y1=. <"1&.> y q=. ~.&.> ; y1 r=. j (e. # [)&.>//.q NB. intersecting requirements u=. ~.j y #"1&.>~ y1 *./@:(e.&>)&.> (r {~ u i. ])&.>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. if. *./1=n do. ,:p return. end. NB. done if found solution j=. (i.<./) n + (1=n)*>./n NB. index of non-unique entry with smallest # possibilties ; x <@solve (('';1) <;.1 >j{p) j}"0 1 p ) fill=: 4 : 0 " 1 NB. fill original puzzle with solution x (<"0 ;,&.>x) (;i)"_} puz [ 'i puz'=. y ) check=: 4 : 0 NB. check Kakuro solutions x 'i s'=. y assert. (#&>i) -:"1 #&>x NB. correct # entries assert. s -:"1 +/&> x NB. satisfies sums assert. i =//.&;"1 x NB. consistent assignments assert. *./@~:&> x NB. unique digits in each row/column assert. ~: x NB. distinct solutions 1 ) kakuro=: 3 : 0 b=. y e. <_ p=. , b<}."1 b,.0 NB. rows s=. {:&> p # ,y NB. sums i=. (p <;.1 , b) #&.> p <;.1 i.*/$y NB. indices p=. , |:b<}.b,0 NB. columns s=. s,{.&> p # ,|:y NB. sums i=. i,(p <;.1 ,|:b) #&.> p <;.1 ,|:i.$y NB. indices p=. (#&>i) |:@cs&.> s NB. joint possibilities q=. ,&.> i solve p assert. q check i;s q fill i;<y NB. fill original puzzle with solutions ) x=. 'x' k0=: ".;._2 ] 0 : 0 NB. from 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 ; _ ; _ ) k1=: ".;._2 ] 0 : 0 NB. from 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 ; _ ; _ ; _ ; _ ; _ ) k0 +----+----+-----+-----+-----+----+----+----+ |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 |_ |_ | +----+----+-----+-----+-----+----+----+----+ kakuro k0 +----+----+-----+-----+-----+----+----+----+ |x |23 0|30 0 |x |x |27 0|12 0|16 0| +----+----+-----+-----+-----+----+----+----+ |0 16|9 |7 |x |17 24|8 |7 |9 | +----+----+-----+-----+-----+----+----+----+ |0 17|8 |9 |15 29|8 |9 |5 |7 | +----+----+-----+-----+-----+----+----+----+ |0 35|6 |8 |5 |9 |7 |12 0|x | +----+----+-----+-----+-----+----+----+----+ |x |0 7 |6 |1 |7 8 |2 |6 |7 0 | +----+----+-----+-----+-----+----+----+----+ |x |11 0|10 16|4 |6 |1 |3 |2 | +----+----+-----+-----+-----+----+----+----+ |0 21|8 |9 |3 |1 |0 5 |1 |4 | +----+----+-----+-----+-----+----+----+----+ |0 6 |3 |1 |2 |x |0 3 |2 |1 | +----+----+-----+-----+-----+----+----+----+ k1 +----+----+----+-----+----+----+----+----+----+----+----+ |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 k1 $ t 40 11 11 (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| +-+-+-+-+ ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
