If I remember correctly, Hui built permutations (lists of indices) up front that represented the sudoku structures (rows, columns, squares), and that because he had found that the claim that there's only one solution was not always accurate, he conducted a breadth first search (with a different copy of the partially solved sudoku puzzle) for some cases.
That said, I took a quick look at your code, and it seems like the merge is working (it's updating only a single cell at a time, but it is updating...). FYI, -- Raul On Sat, Feb 26, 2022 at 8:46 AM 'Viktor Grigorov' via Programming <[email protected]> wrote: > > Hello, > > I would like to share my progress with the sudoku solver I started awhiles > back. I combed and tested every line, I discovered a major mistake, namely > indices of a wrong face of the 3 3 3 3 mat, one not corresponding to one of > the 9 big squares (when shaped as 9 9). I'm still disappointed I could not > figure out how to shirk the control structure, the one to iterate over cells, > let alone make a one-liner. I looked at modifier trains vocabulary in the > wiki, wrote down on paper what corresponded to which PoS, and try some 10 or > so with any permutation of parentheses. Still I could not get it to parse as > I wished it to. Explicit win this round. > > Having achieved a mild success, I finally decided it wouldn't be spoiling > myself to see Hui's text on his solver. Using the unsolved sudoku on the > page, I found out that mine is 2.5--10x slower. I am assuming this is due to > constant un/boxing and amending. Up til this undertaking, I'd never used > boxes, and I'm no programmer, and I've been stuck on ch.14 of Learning J for > a few months, so I lack some critical informatoin or am misusing them. I saw > some similarities in the approaches: his regions is my nines; his I is my i, > but I still haven't fulled gotten what his implementations does exactly, but > he works with 2-dim mats without boxes, whereas I wanted to contract it as > much as possible and possibly use symmetries. > > > NB. easy/hard unsolved/solved countesy of nudokueu=:<"0(3 3 3 3$EU=:4 0 6 0 2 > 3 0 0 9 0 9 8 1 0 6 0 3 5 0 2 0 8 9 7 0 0 6 2 3 4 0 1 5 9 6 8 0 8 0 3 6 0 0 0 > 4 0 6 9 2 0 0 0 0 0 9 5 1 0 3 0 4 8 0 0 4 3 9 7 1 6 5 2 6 7 0 0 5 0 3 9 1) > es=:<"0(3 3 3 3$ES=:4 1 6 5 2 3 8 7 9 7 9 8 1 4 6 2 3 5 3 2 5 8 9 7 1 4 6 2 3 > 4 7 1 5 9 6 8 1 8 7 3 6 9 5 2 4 5 6 9 2 8 4 7 1 3 9 5 1 6 3 2 4 8 7 8 4 3 9 7 > 1 6 5 2 6 7 2 4 5 8 3 9 1) > hu=:<"0(3 3 3 3$HU=:3 0 0 0 5 0 0 0 7 0 0 0 0 0 0 2 0 5 2 0 0 6 0 0 1 0 8 0 5 > 7 3 1 6 9 0 0 0 0 9 0 8 7 0 1 0 0 0 0 0 0 0 5 7 0 1 0 4 0 0 0 7 2 9 0 0 0 0 0 > 1 0 5 0 0 7 0 9 0 0 0 6 0) > hs=:<"0(3 3 3 3$HS=:3 1 8 2 5 4 6 9 7 7 4 6 1 9 8 2 3 5 2 9 5 6 7 3 1 4 8 4 5 > 7 3 1 6 9 8 2 6 2 9 5 8 7 3 1 4 8 3 1 4 2 9 5 7 6 1 6 4 8 3 5 7 2 9 9 8 2 7 6 > 1 4 5 3 5 7 3 9 4 2 8 6 1) > > mn=:((1+i.9)#~[:-.(1+i.9)e.,)@(((1:=#)#])@>@,) NB. missing numbers of boxed > >1-dim > is=:e.#[ NB. intersection > Q=:i.3 NB. auxiliary noun, assuming square faces > vari=:[{."_1]A.~#@:]([(]*i.@:%)&!-)[ NB. permutations > https://code.jsoftware.com/wiki/Phrases/Sets > > NB.nines=:~.(4 vari 0;0;1;1;2;2;q;q) > NB.nines=:((8&=@(+/@:(#@>)))"1#])nines NB. contains q twice > NB.nines=:(((#@>@{.)~:(#@>@{:))"1#])nines NB. cells 1 and 4 diff > NB.nines=:((-.@((3&=@#@:>@(0&{))*.(3&=@#@:>@(2&{))))"1#])nines NB. only cells > 2 or 4 len 3 > nines=:((-.@((3&=@#@:>@(0&{))*.(3&=@#@:>@(2&{))))"1#])@(((#@>@{.)~:(#@>@{:))"1#])@((8&=@(+/@:(#@>)))"1#])@~.(4 > vari 0;0;1;1;2;2;Q;Q) > > i=:~.(4 vari 0;0;0;0;1;1;1;1;2;2;2;2) NB. 3 3 3 3 indices > frc=:(nines&((2&=@(+/)@:([=]))"1 1 1#[)) NB. gets a cell's corresp. fac, row, > col in boxed form in 3 4 shape, e.g., frc 34 { i > > NB.if empty (0-containing), amend with the intersection of the missing > numbers of its nines; > NB.elif possibilities (could-be numbers for a cell), for each of its frc, > amend w/ its one unique possibility, having removed self > NB.else, treat as if empty > > solver=:solve^:_ > NB.q cell indices ; w cell value ; e amend value > solve=:3 :0 > NB.for_ijk. ((0&=)#(i.@#))EU do. NB. for all 0 or >1-len cells? > for_ijk.i.81 do. > if.(0&=)w=.>(<q=.ijk{i){y do. > y=.(is/(<mn(<"1 Q{frc q){y))(<q)}y > elseif.(1:<#)w do. > > if.(1:=#)e=.(0&~:#])@,@~.@(w((-.@([e."1]))#[)(~.@;@(((<w)~:])#])@((1:<(#@>))#])@:,"2@((<"1 > Q{frc q){])))y do. > y=.(<e)(<q)}y > else. > y=.(is/(<mn(<"1 Q{frc q){y))(<q)}y > end. > end. > end. > y > ) > > Due to some shape thing (1-len lists gets boxed vs scalars getting boxed?), > comapring directly with = doesn't work as desired, so I visually compare > (<(9 9 $, solver eu)),(<(<"0 (9 9 $, sudoku EU))) > (<(9 9 $, solver X)),(<(<"0 (9 9 $, sudoku x))) > (<(9 9 $, solver hu)),(<(<"0 (9 9 $, sudoku HU))) > > To be solved remains 1., why amends with nothing happen; 2., why the amend > value takes values is shouldn't. No amount of space make this quickly/easily > legible for me, so please excuse my forgoing space. > > I would like to make this into an 'essay' once working for all solvables, if > it can be made more tacit or eloquent. In any case, I'd appreciate any > criticism or recommendations. > > Cheers, > v > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
