NB. Sudoku solver in J NB. Algorithm X implementation via http://youtu.be/DmT80OseAGs NB. ctrl+f 'FINAL LISTING' to see final results NB. a couple of puzzles to use s44 =: ".;._2 ] 0 : 0 0 0 0 0 0 0 2 1 3 0 0 4 0 0 0 0 ) s99 =: ".;._2 ] 0 : 0 0 0 1 6 9 0 5 0 0 4 0 0 2 7 0 0 0 1 0 7 0 0 0 0 0 9 0 0 0 0 0 0 0 0 3 0 0 0 0 4 3 0 0 0 7 0 0 0 7 8 0 6 0 0 0 0 6 0 0 0 8 0 5 0 2 0 1 4 0 0 6 0 0 1 0 3 5 0 0 4 0 ) NB. Let's begin! i. 3 3 NB. 3x3 array 0 1 2 3 4 5 6 7 8 ([: i. ,~) 3 0 1 2 3 4 5 6 7 8 (] #"1 [: i. ,~) 3 NB. replicate row item 0 0 0 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 (] # ] #"1 [: i. ,~) 3 NB. and replicate rows 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 3 3 3 4 4 4 5 5 5 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 6 6 6 7 7 7 8 8 8 6 6 6 7 7 7 8 8 8 NB. 'box numbers' for each coordinate box =: ] # ] #"1 [: i. ,~ box 2 NB. we will proceed with 4x4 puzzles instead of 9x9 0 0 1 1 0 0 1 1 2 2 3 3 2 2 3 3 (i.) 4 0 1 2 3 (,"0/~ @: i.) 4 NB. append table 0 0 0 1 0 2 0 3 1 0 1 1 1 2 1 3 2 0 2 1 2 2 2 3 3 0 3 1 3 2 3 3 ([: <"_2 ,"-/~@:i.) 4 NB. box it so that we have a rank 2 array +---+---+---+---+ |0 0|0 1|0 2|0 3| +---+---+---+---+ |1 0|1 1|1 2|1 3| +---+---+---+---+ |2 0|2 1|2 2|2 3| +---+---+---+---+ |3 0|3 1|3 2|3 3| +---+---+---+---+ box@:%: 4 0 0 1 1 0 0 1 1 2 2 3 3 2 2 3 3 (box@:%: ,~&.> [: <"_2 ,"0/~ @: i.) 4 NB. now append each box number to r/c +-----+-----+-----+-----+ |0 0 0|0 1 0|0 2 1|0 3 1| +-----+-----+-----+-----+ |1 0 0|1 1 0|1 2 1|1 3 1| +-----+-----+-----+-----+ |2 0 2|2 1 2|2 2 3|2 3 3| +-----+-----+-----+-----+ |3 0 2|3 1 2|3 2 3|3 3 3| +-----+-----+-----+-----+ (box@:%: <@,~"_2 ,"0/~ @: i.) 4 NB. slight optimization +-----+-----+-----+-----+ |0 0 0|0 1 0|0 2 1|0 3 1| +-----+-----+-----+-----+ |1 0 0|1 1 0|1 2 1|1 3 1| +-----+-----+-----+-----+ |2 0 2|2 1 2|2 2 3|2 3 3| +-----+-----+-----+-----+ |3 0 2|3 1 2|3 2 3|3 3 3| +-----+-----+-----+-----+ NB. row-column-box numbers rcb =: box@:%: <@,~"_2 ,"-/~@:i. rcb 4 +-----+-----+-----+-----+ |0 0 0|0 1 0|0 2 1|0 3 1| +-----+-----+-----+-----+ |1 0 0|1 1 0|1 2 1|1 3 1| +-----+-----+-----+-----+ |2 0 2|2 1 2|2 2 3|2 3 3| +-----+-----+-----+-----+ |3 0 2|3 1 2|3 2 3|3 3 3| +-----+-----+-----+-----+ (<2 2 3) =&.> rcb 4 NB. shares an rcb component with <2 2 3 +-----+-----+-----+-----+ |0 0 0|0 0 0|0 1 0|0 0 0| +-----+-----+-----+-----+ |0 0 0|0 0 0|0 1 0|0 0 0| +-----+-----+-----+-----+ |1 0 0|1 0 0|1 1 1|1 0 1| +-----+-----+-----+-----+ |0 0 0|0 0 0|0 1 1|0 0 1| +-----+-----+-----+-----+ (<2 2 3) (1 e. =)&.> rcb 4 NB. contention map +-+-+-+-+ |0|0|1|0| +-+-+-+-+ |0|0|1|0| +-+-+-+-+ |1|1|1|1| +-+-+-+-+ |0|0|1|1| +-+-+-+-+ (<2 2 3) (1 e. =)&> rcb 4 NB. we can drop the boxes 0 0 1 0 0 0 1 0 1 1 1 1 0 0 1 1 (1 e. =)&>/~ rcb 4 NB. contention using all of its cells 1 1 1 1 1 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 0 ... NB. snip 0 0 1 1 1 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 1 1 1 1 $ (1 e. =)&>/~ rcb 4 NB. 4x4 map of 4x4 contention sets 4 4 4 4 $ <"2 (1 e. =)&>/~ rcb 4 4 4 <"2 (1 e. =)&>/~ rcb 4 +-------+-------+-------+-------+ |1 1 1 1|1 1 1 1|1 1 1 1|1 1 1 1| |1 1 0 0|1 1 0 0|0 0 1 1|0 0 1 1| |1 0 0 0|0 1 0 0|0 0 1 0|0 0 0 1| |1 0 0 0|0 1 0 0|0 0 1 0|0 0 0 1| +-------+-------+-------+-------+ |1 1 0 0|1 1 0 0|0 0 1 1|0 0 1 1| |1 1 1 1|1 1 1 1|1 1 1 1|1 1 1 1| |1 0 0 0|0 1 0 0|0 0 1 0|0 0 0 1| |1 0 0 0|0 1 0 0|0 0 1 0|0 0 0 1| +-------+-------+-------+-------+ |1 0 0 0|0 1 0 0|0 0 1 0|0 0 0 1| |1 0 0 0|0 1 0 0|0 0 1 0|0 0 0 1| |1 1 1 1|1 1 1 1|1 1 1 1|1 1 1 1| |1 1 0 0|1 1 0 0|0 0 1 1|0 0 1 1| +-------+-------+-------+-------+ |1 0 0 0|0 1 0 0|0 0 1 0|0 0 0 1| |1 0 0 0|0 1 0 0|0 0 1 0|0 0 0 1| |1 1 0 0|1 1 0 0|0 0 1 1|0 0 1 1| |1 1 1 1|1 1 1 1|1 1 1 1|1 1 1 1| +-------+-------+-------+-------+ ([: <"2 (1 e. =)&>/~) rcb 4 +-------+-------+-------+-------+ |1 1 1 1|1 1 1 1|1 1 1 1|1 1 1 1| |1 1 0 0|1 1 0 0|0 0 1 1|0 0 1 1| |1 0 0 0|0 1 0 0|0 0 1 0|0 0 0 1| ... NB. snip |1 1 0 0|1 1 0 0|0 0 1 1|0 0 1 1| |1 1 1 1|1 1 1 1|1 1 1 1|1 1 1 1| +-------+-------+-------+-------+ cmap =: [: <"2 (1 e. =)&>/~ s44 0 0 0 0 0 0 2 1 3 0 0 4 0 0 0 0 cmap rcb # s44 NB. this is how you get the contention map for a puzzle +-------+-------+-------+-------+ |1 1 1 1|1 1 1 1|1 1 1 1|1 1 1 1| |1 1 0 0|1 1 0 0|0 0 1 1|0 0 1 1| |1 0 0 0|0 1 0 0|0 0 1 0|0 0 0 1| ... NB. snip |1 1 0 0|1 1 0 0|0 0 1 1|0 0 1 1| |1 1 1 1|1 1 1 1|1 1 1 1|1 1 1 1| +-------+-------+-------+-------+ (<2 1) ({ cmap@:rcb@:#) s44 NB. which cells are in contention with cell <2 1 +-------+ |0 1 0 0| |0 1 0 0| |1 1 1 1| |1 1 0 0| +-------+ (<2 1) ({:: cmap@:rcb@:#) s44 NB. use Fetch to unbox 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 (<2 1) (] * ({:: cmap@:rcb@:#)) s44 NB. keep only cells in contention with <2 1 0 0 0 0 0 0 0 0 3 0 0 4 0 0 0 0 (<2 1) #@:] s44 NB. size of the puzzle 4 (<2 1) >:@:i. @: #@:] s44 NB. puzzle's possible values 1 2 3 4 (<2 1) (>:@:i.@:#@:] -. ] * ({:: cmap@:rcb@:#)) s44 NB. all values -. those in contention 1 2 NB. numbers available at x in puzzle y avl =: >:@:i.@:#@:] -. ] * ({:: cmap@:rcb@:#) (<0 0) avl s44 1 2 4 88 (<2 1) } s44 NB. we can use } to Amend the puzzle 0 0 0 0 0 0 2 1 3 88 0 4 0 0 0 0 99 (<0 0) } s44 NB. x m} y puts x at cell m in y 99 0 0 0 0 0 2 1 3 0 0 4 0 0 0 0 (<0 0) avl s44 1 2 4 ((<0 0) avl s44) (<0 0)}"0 _ s44 NB. "0 _ makes it pair each cell with entire grid 1 0 0 0 0 0 2 1 3 0 0 4 0 0 0 0 2 0 0 0 0 0 2 1 3 0 0 4 0 0 0 0 4 0 0 0 0 0 2 1 3 0 0 4 0 0 0 0 <"2 ((<0 0) avl s44) (<0 0)}"0 _ s44 NB. box up the grids +-------+-------+-------+ |1 0 0 0|2 0 0 0|4 0 0 0| |0 0 2 1|0 0 2 1|0 0 2 1| |3 0 0 4|3 0 0 4|3 0 0 4| |0 0 0 0|0 0 0 0|0 0 0 0| +-------+-------+-------+ NB. placement vector of available cells pvec =: 4 : '<"2 (x avl y) x}"0 _ y' NB. no way to make this tacit, due to "0 _ (<0 0) pvec s44 +-------+-------+-------+ |1 0 0 0|2 0 0 0|4 0 0 0| |0 0 2 1|0 0 2 1|0 0 2 1| |3 0 0 4|3 0 0 4|3 0 0 4| |0 0 0 0|0 0 0 0|0 0 0 0| +-------+-------+-------+ (<1 1) (pvec >)"0 (<0 0) pvec s44 +-------+-------+ |1 0 0 0|1 0 0 0| |0 3 2 1|0 4 2 1| |3 0 0 4|3 0 0 4| |0 0 0 0|0 0 0 0| +-------+-------+ |2 0 0 0|2 0 0 0| |0 3 2 1|0 4 2 1| |3 0 0 4|3 0 0 4| |0 0 0 0|0 0 0 0| +-------+-------+ |4 0 0 0| | |0 3 2 1| | |3 0 0 4| | |0 0 0 0| | +-------+-------+ (<1 1)&pvec&.> (<0 0) pvec s44 NB. pvec with another cell under all boxes +-----------------+-----------------+---------+ |+-------+-------+|+-------+-------+|+-------+| ||1 0 0 0|1 0 0 0|||2 0 0 0|2 0 0 0|||4 0 0 0|| ||0 3 2 1|0 4 2 1|||0 3 2 1|0 4 2 1|||0 3 2 1|| ||3 0 0 4|3 0 0 4|||3 0 0 4|3 0 0 4|||3 0 0 4|| ||0 0 0 0|0 0 0 0|||0 0 0 0|0 0 0 0|||0 0 0 0|| |+-------+-------+|+-------+-------+|+-------+| +-----------------+-----------------+---------+ ; (<1 1)&pvec&.> (<0 0) pvec s44 NB. raze +-------+-------+-------+-------+-------+ |1 0 0 0|1 0 0 0|2 0 0 0|2 0 0 0|4 0 0 0| |0 3 2 1|0 4 2 1|0 3 2 1|0 4 2 1|0 3 2 1| |3 0 0 4|3 0 0 4|3 0 0 4|3 0 0 4|3 0 0 4| |0 0 0 0|0 0 0 0|0 0 0 0|0 0 0 0|0 0 0 0| +-------+-------+-------+-------+-------+ ; (<1 0)&pvec&.> ; (<1 1)&pvec&.> (<0 0) pvec s44 NB. add another cell +-------+-------+ |1 0 0 0|2 0 0 0| |4 3 2 1|4 3 2 1| |3 0 0 4|3 0 0 4| |0 0 0 0|0 0 0 0| +-------+-------+ ; (<1 0)&pvec&.> ; (<1 1)&pvec&.> ; (<0 0)&pvec&.> < s44 NB. extrapolate! +-------+-------+ |1 0 0 0|2 0 0 0| |4 3 2 1|4 3 2 1| |3 0 0 4|3 0 0 4| |0 0 0 0|0 0 0 0| +-------+-------+ NB. collect all pvecs pvex =: 4 : '; x & pvec &. > y' NB. can be made tacit, though we lose the beauty of &. pvex =: <@(pvec >)"0 (;@:) (<1 0) pvex (<1 1) pvex (<0 0) pvex < s44 +-------+-------+ |1 0 0 0|2 0 0 0| |4 3 2 1|4 3 2 1| |3 0 0 4|3 0 0 4| |0 0 0 0|0 0 0 0| +-------+-------+ pvex/ (<1 0),(<1 1),(<0 0), < s44 NB. expressed as a fold +-------+-------+ |1 0 0 0|2 0 0 0| |4 3 2 1|4 3 2 1| |3 0 0 4|3 0 0 4| |0 0 0 0|0 0 0 0| +-------+-------+ pvex/ (<2 1),(<1 0),(<1 1),(<0 0), < s44 NB. another empty cell +-------+-------+-------+-------+ |1 0 0 0|1 0 0 0|2 0 0 0|2 0 0 0| |4 3 2 1|4 3 2 1|4 3 2 1|4 3 2 1| |3 1 0 4|3 2 0 4|3 1 0 4|3 2 0 4| |0 0 0 0|0 0 0 0|0 0 0 0|0 0 0 0| +-------+-------+-------+-------+ (#) s44 NB. size 4 ([: ,"0/~@i. #) s44 NB. append-table 0 0 0 1 ... NB. snip 3 2 3 3 ([: <"1 [: ,"0/~@i. #) s44 NB. box the pairs +---+---+---+---+ |0 0|0 1|0 2|0 3| +---+---+---+---+ |1 0|1 1|1 2|1 3| +---+---+---+---+ |2 0|2 1|2 2|2 3| +---+---+---+---+ |3 0|3 1|3 2|3 3| +---+---+---+---+ , ([: <"1 [: ,"0/~@i. #) s44 NB. make it a list +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |0 0|0 1|0 2|0 3|1 0|1 1|1 2|1 3|2 0|2 1|2 2|2 3|3 0|3 1|3 2|3 3| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 0 = s44 NB. cells that are empty 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 , 0 = s44 NB. in a list 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 (0&= #&, [: <"1 [: ,"0/~@i. #) s44 NB. select the pairs by the empty cells +---+---+---+---+---+---+---+---+---+---+---+---+ |0 0|0 1|0 2|0 3|1 0|1 1|2 1|2 2|3 0|3 1|3 2|3 3| +---+---+---+---+---+---+---+---+---+---+---+---+ NB. list of all the cells that need filling emt =: 0&= #&, [: <"1 [: ,"0/~@i. # emt s44 +---+---+---+---+---+---+---+---+---+---+---+---+ |0 0|0 1|0 2|0 3|1 0|1 1|2 1|2 2|3 0|3 1|3 2|3 3| +---+---+---+---+---+---+---+---+---+---+---+---+ pvex/ (emt s44) , < s44 +-------+ |2 1 4 3| |4 3 2 1| |3 2 1 4| |1 4 3 2| +-------+ svec =: pvex/@:(emt , <) NB. solution vector svec s44 +-------+ |2 1 4 3| |4 3 2 1| |3 2 1 4| |1 4 3 2| +-------+ NB. so the FINAL LISTING is below box =: [ # [ #"1 [: i. ,~ rcb =: box@:%: <@,"_2~ ,"0/~@:i. cmap =: [: <"2 (1 e. =)&>/~ avl =: >:@:i.@:#@:] -. ] * ({:: cmap@:rcb@:#) pvec =: 4 : '<"2 (x avl y) x}"0 _ y' pvex =: 4 : 'x & pvec &. > (; @:) y' pvex =: <@(pvec >)"0 (;@:) NB. alternative tacit emt =: 0&= #&, [: <"1 [: ,"0/~@:i. # svec =: [: pvex/ emt , < NB. However! NB. We can be more efficient about this. NB. notice that cmap rcb # y is constant throughout svec, but avl is called NB. a whole bunch of times and has to recalculate it every time. NB. We choose to make everything a bunch of adverbs, and pass in NB. (cmap rcb # y) as m: from svec to pvex to pvec to avl. box =: [ # [ #"1 [: i. ,~ rcb =: box@:%: <@,"_2~ ,"0/~@:i. cmap =: [: <"2 (1 e. =)&>/~ avl =: 1 : '>:@:i.@:#@:] -. (* {::&m)~' pvec =: 1 : (':' ; '(x m avl y) x}"0 _ y') pvex =: 1 : 'x & (m pvec) &. > (;@:)' emt =: 0&= #&, [: <"1 [: ,"0/~@:i. # svec =: 3 : '(cmap rcb # y) pvex / (emt y) , < y' NB. bonus tacit adverbs, where available avl =: {:: & (* `) (`: 6) ~ (>:@:i.@:#@:] ` -. `) (`: 6) pvex =: pvec (` >) (`: 6) (< @) (" 0) (; @:) NB. using alt version svec s99 +-----------------+ |2 8 1 6 9 3 5 7 4| |4 6 9 2 7 5 3 8 1| |5 7 3 8 1 4 2 9 6| |7 9 2 5 6 1 4 3 8| |6 5 8 4 3 9 1 2 7| |1 3 4 7 8 2 6 5 9| |3 4 6 9 2 7 8 1 5| |9 2 5 1 4 8 7 6 3| |8 1 7 3 5 6 9 4 2| +-----------------+ ts =: 6!:2 , [: 7!:2 ] ts 'svec s99' 0.750548 3.20525e6 NB. Thanks for playing! NB. www.jsoftware.com NB. www.TryAPL.org