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
