I got confused trying to reconcile Roger’s wiki essay version and his earlier
(I think)
forum posting. So here’s a new attempt to generalise his algorithm starting
from the
wiki essay. I’ve assumed the input’s ravel is of length an exact fourth power,
n4;
n1, n2, n3 are the lower powers, and n22 is 2#n2.
What I got wrong earlier is to assume 27 9 generalises to n3, n2 in ok .No! It
should be
3 1 * n2, since there are always only 3 members of regions, being related to
rows,
columns, and boxes. That was why I got index error in “free”.
I’ve put the one-liners and constant definitions within a cover function,
solve. This iPad’s J701 doesn’t allow {{ }} definitions, so multiline
functions remain outside solve.
Here’s the generalisation. I think it’s self-contained, apologies if not.
solve =: 3 : 0
'n1 n2 n3' =: 1 2 3 <.@^~ <.@%:^:2 n4 =: #, y
n22 =. 2#n2
j =. (]/. i.@#) ,{;~n1#i.n1
r =. n2#i.n22
c =. n4$|:i.n22
b =. (,j{n2#i.n2) { j
I =: ~."1 r,.c,.b
R =: j,(,|:)i.n22
regions=: R {"_ 1 ]
free =: 0&= > (1+i.n2) e."1 I&{
ok =: (1$~3 1*n2) -:"2 (0&= +. ~:"1)@regions
ac =: +/ .*&(1+i.n2) * 1 = +/"1
assign =: (+ (ac >. ar)@free)^:_"1
guess =: ; @: (<@guessa"1)
sudoku =: guess @: (ok # ]) @: assign ^:_ @ ,
see1 =: (;~n2$n1{.1)&(<;.1) @ ({&'.123456789abcdefghjklmnpqrst') @ (n22&$) @ ,
see =: <@see1"1`see1@.(1:=#@$)
diff =: * 0&=@}:@(0&,)
sudoku y
)
ar =: 3 : 0
m=. 1=+/"2 R{y
j=. I. +./"1 m
k=. 1 i."1~ j{m
i=. ,(k{"_1 |:"2 (j{R){y) #"1 j{R
(1+k) i}n4$0
)
guessa =: 3 : 0
if. -. 0 e. y do. ,:y return. end.
b=. free y
i=. (i.<./) (+/"1 b){n2p1,}.i.n2p1=.>:n2
y +"1 (1+I.i{b)*/i=i.n4
)
NB. I hope this looks ok in fixed font. It’s awful on this iPad!
see each (,;>@:{:@solve) nine NB. Show input & output for a 9x9 puzzle.
+-------------+-------------+
|+---+---+---+|+---+---+---+|
||2..|67.|...|||283|671|945||
||..6|...|2.1|||976|548|231||
||4..|...|8..|||415|392|876||
|+---+---+---+|+---+---+---+|
||5..|..9|3..|||567|419|382||
||.3.|...|.5.|||834|267|159||
||..2|8..|..7|||192|835|467||
|+---+---+---+|+---+---+---+|
||..1|...|..4|||321|786|594||
||7.8|...|6..|||758|924|613||
||...|.53|..8|||649|153|728||
|+---+---+---+|+---+---+---+|
+-------------+-------------+
see each (,;>@:{:@solve) sixteen2 NB. Show input & output for a 16x16 puzzle.
+---------------------+---------------------+
|+----+----+----+----+|+----+----+----+----+|
||36..|..4f|cbd2|8.5.|||36a1|7g4f|cbd2|895e||
||..f.|1.e.|..8.|d...|||72fc|1be5|6389|dg4a||
||.ed.|.8a.|.g5.|....|||9edb|28a3|4g51|f67c||
||.54.|....|...7|3b.2|||854g|c69d|eaf7|3b12||
|+----+----+----+----+|+----+----+----+----+|
||..9.|.7..|..3a|64..|||dg98|b7c1|fe3a|6425||
||.b..|4d..|....|7fa8|||eb63|4d2g|519c|7fa8||
||....|f...|..64|b.e.|||1c25|fa39|7864|bdeg||
||.f..|..6.|d2..|9c..|||af74|5e68|d2gb|9c31||
|+----+----+----+----+|+----+----+----+----+|
||c1..|.3.6|94e8|5...|||c1g7|a3f6|94e8|52db||
||....|d2.c|.5a3|1e9.|||64bf|d28c|g5a3|1e97||
||2..9|.5..|bc7.|.8f.|||2d39|g51e|bc76|a8f4||
||..8e|.47b|1d..|....|||5a8e|947b|1d2f|g3c6||
|+----+----+----+----+|+----+----+----+----+|
||4...|3.g.|.6..|....|||495a|3cg7|26bd|e18f||
||g7cd|e9.2|8...|.a..|||g7cd|e9b2|8f15|4a63||
||b.1.|.f..|....|.5..|||b316|8fd4|a7ce|25g9||
||f8..|6.5a|3...|.7b.|||f8e2|615a|394g|c7bd||
|+----+----+----+----+|+----+----+----+----+|
+---------------------+---------------------+
Mike
Sent from my iPad
> On 19 Jun 2022, at 18:26, 'Michael Day' via Programming
> <[email protected]> wrote:
>
> FWIW, I've been looking at this, and my own slower and more space-consuming
> versions.
> I tried amending Roger's similar original code, posted in the forum, I
> think, with obvious
> changes as follows. Some of his verbs, including your ac & ar I think
> differ in the wiki article
> from the ones I have. I've used suffixes x or hx for hex:
>
> NB. Hui's solution for 16x16?
>
> size2x =: 2#sizex =: *: smallx =: 4
> jx =. (]/. i.@#) ,{;~smallx#i.smallx
> rx =. size2x $"1 i.size2x
> cx =. (size2x$i.sizex){|:i.size2x
> bx =. (jx{sizex#i.sizex) { jx
> Ix =: rx,"1 cx ,"1 bx
> Rx =: jx,(,|:)i.size2x
>
> freex =: 0&= > (1+i.sizex)"_ e."1 Ix"_ { ,
> regionsx=: Rx"_ {"_ 1 ,"2
> eux =: e.&(i.sizex+1) *. 0&= +. ~:"1
> okx =: (1$~(smallx,1)*size2x)"_ -:"2 eux@regionsx
>
> s1ux =: 3 : 0
> m=. 1=+/"2 Rx{,/y
> j=. I. +./"1 m
> k=. 1 i."1~ j{m
> i=. ,(k{"_1 |:"2 (j{Rx){,/y) #"1 j{Rx
> size2x$(1+k) i}0$~*/size2x
> )
>
> NB. s1x =: +/ .*&(1+i.9) * 1: = +/"1
> NB. s1 =: (+ (s1x >. s1u)@free)^:_"2
> NB. sudoku =: s2 @: (ok # ]) @: s1 ^:_
>
> s1xx =: +/ .*&(1+i.sizex) * 1: = +/"1
> s1hx =: (+ (s1xx >. s1ux)@freex)^:_"2
>
> s2ax =: 3 : 0
> if. -. 0 e. ,y do. ,:y return. end.
> b=. freex y
> i=. (i.<./),(+/"1 b){(1+sizex),}.i.sizex
> d=. 1+I.i{,/b
> y +"2 d *"0 2 i=i.size2x
> )
>
> s2x =: ; @: (<@s2ax"2)
>
> sudokux =: s2x @: (okx # ]) @: s1hx ^:_
> NB. ==================================================================
>
> When I run this on my solvable array, sixteen2, it fails:
> s1x sixteen2
> |length error: s1x
> | s1x sixteen2
>
> Debug shows the error occurs in or around freex, but I haven't yet
> discovered how.
>
> Here's sixteen2:
> sixteen2
> 3 6 0 0 0 0 4 15 12 11 13 2 8 0 5 0
> 0 0 15 0 1 0 14 0 0 0 8 0 13 0 0 0
> 0 14 13 0 0 8 10 0 0 16 5 0 0 0 0 0
> 0 5 4 0 0 0 0 0 0 0 0 7 3 11 0 2
> 0 0 9 0 0 7 0 0 0 0 3 10 6 4 0 0
> 0 11 0 0 4 13 0 0 0 0 0 0 7 15 10 8
> 0 0 0 0 15 0 0 0 0 0 6 4 11 0 14 0
> 0 15 0 0 0 0 6 0 13 2 0 0 9 12 0 0
> 12 1 0 0 0 3 0 6 9 4 14 8 5 0 0 0
> 0 0 0 0 13 2 0 12 0 5 10 3 1 14 9 0
> 2 0 0 9 0 5 0 0 11 12 7 0 0 8 15 0
> 0 0 8 14 0 4 7 11 1 13 0 0 0 0 0 0
> 4 0 0 0 3 0 16 0 0 6 0 0 0 0 0 0
> 16 7 12 13 14 9 0 2 8 0 0 0 0 10 0 0
> 11 0 1 0 0 15 0 0 0 0 0 0 0 5 0 0
> 15 8 0 0 6 0 5 10 3 0 0 0 0 7 11 0
>
> My own code is more secure in APL, and too long-winded
> to share here!
>
> Cheers,
>
> Mike
>
>
>
>
>> On 19/06/2022 17:42, Brian Schott wrote:
>> Raul,
>>
>> I truly appreciate your comments and while they seem very reasonable I do
>> not know how to delve more deeply into the permutations as you suggest. I
>> am leaning more to dropping the idea of finding a solution based on Roger’s
>> algorithm. Instead I want to look more closely at his results for the verbs
>> AR and AC. In his algorithm he takes the larger of the two results, that is
>> the larger of AR or AC , where he expects one of each pair to be zero and
>> the other to be a valid candidate. Whenever there is a nonzero AC it is a
>> unique and correct candidate, but the values for AR are selected using
>> index of, i. . I am suspicious that the selection of AR is almost arbitrary
>> and is causing the problem. I think a human being could do a better job of
>> selecting among the alternatives from AR.
>>
>> By the way in my definition for the verb AR the final negative one should
>> be a zero, but it doesn’t change things much. Also in my text above I am
>> capitalizing AR and AC but they are lowercase verbs.
>>
>> If I am correct about using AR and AC to help a human, I would use a
>> variation on AC that shows all of the possible results instead of the one
>> captured by the ‘index of’ primitive. In light of that I am looking for
>> ways to use 4 x 4 arrangements of dots to display each of the cell’s
>> information. I was looking in the Unicode lists for 4 x 4 dot arrangements
>> but was unable to find any, so I am trying to imagine alternatives. So far
>> I can only think of using viewmat to construct the dot patterns.
>>
>> Any more ideas?
>>
>>
>>
>>> --
>> (B=) <-----my sig
>> Brian Schott
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
>
>
> --
> This email has been checked for viruses by Avast antivirus software.
> https://www.avast.com/antivirus
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
