Re: [Bug-apl] ⎕DLX (2)

[Juergen Sauermann]

Hi Xtian,

the constraint matrix *B* for *⎕DLX B* should contain 0 1 or 2 (either
as numbers or as characters (blank is also allowed and means 0)
If the matrix contains other numbers or characters than you get a DOMAIN 
ERROR.

Referring to Knuth's original paper, 1 stands for a primary constraint 
while 2 stands
for a secondary constraint. A mix of 1 and 2 in the same column is not 
allowed.
As far as I can see, in the sudoku case all constraints are primary, so 
z should contain
only 0s and 1s.

I also believe that the number of rows (729 == 9×9×9) stated in one of 
your links is correct,
but the number of columns (9×9×4=324) is maybe not. I would suppose that 
it is 9×(9+9+9+2)=171
for 9 digits×(9 rows + 9 columns + 9 boxes + 2 main diagonals).

If you have a matrix *z* with numbers indicating the digits for the 
different constraints (which is
easier to troubleshoot than a pure 0/1 matrix) , then instead of *⎕DLX 
z* you can probably
simply use *⎕DLX ∼z∈0 '0 '*to avoid the DOMAIN ERROR. This works, of course,
only if there are no secondary constraints involved, like for sudokus.

/// Jürgen


On 11/24/2016 06:34 AM, Christian Robert wrote:
> ps: Got there 
> (http://www.stolaf.edu/people/hansonr/sudoku/exactcovermatrix.htm see 
> previous post)
>
> from:
>
>   http://garethrees.org/2007/06/10/zendoku-generation/#section-4
>
> Very interesting article explaining DLX.
>
> Xtian.
>
> On 2016-11-24 00:26, Christian Robert wrote:
> > Juergen,
> >
> > Well, I did a test for Sudoku.
> >
> > from http://www.stolaf.edu/people/hansonr/sudoku/exactcovermatrix.htm
> >
> > I extracted the matrix of constraints and put it in "z".
> >
> > Strangely the matrix is sized at rho (729,(4 x 81)) a bit 
> > incompatible with your Q8 example.
> >
> > and ⎕DLX give me a DOMAIN error.
> >
> > Attached, you can find my "test.apl" workspace, (no need to retype 
> > all those numbers by yourself).
> >
> > any help would be appreciated.
> >
> > Xtian.
> >
> >       )load test.apl
> > DUMPED 2016-11-24 00:06:52 (GMT-5)
> >       )vars
> > y   z
> >       ⍴y
> > 729
> >       ⍴z
> > 729 324
> >
> > // Samples
> >
> >       z[⍳81;(0×81)+⍳81] z[⍳81;(1×81)+⍳81]
> >  1 1
> >  2 2
> >  3 3
> >  4 4
> >  5 5
> >  6 6
> >  7 7
> >  8 8
> >  9 9
> > 1 1
> > 2 2
> > 3 3
> > 4 4
> > 5 5
> > 6 6
> > 7 7
> > 8 8
> > 9 9
> > 1 1
> > 2 2
> > 3 3
> > 4 4
> > 5 5
> > 6 6
> > 7 7
> > 8 8
> > 9 9
> > 1 1
> > 2 2
> > 3 3
> > 4 4
> > 5 5
> > 6 6
> > 7 7
> > 8 8
> > 9 9
> > 1 1
> > 2 2
> > 3 3
> > 4 4
> > 5 5
> > 6 6
> > 7 7
> > 8 8
> > 9 9
> > 1 1
> > 2 2
> > 3 3
> > 4 4
> > 5 5
> > 6 6
> > 7 7
> > 8 8
> > 9 9
> > 1 1
> > 2 2
> > 3 3
> > 4 4
> > 5 5
> > 6 6
> > 7 7
> > 8 8
> > 9 9
> > 1 1
> > 2 2
> > 3 3
> > 4 4
> > 5 5
> > 6 6
> > 7 7
> > 8 8
> > 9 9
> > 1 1
> > 2 2
> > 3 3
> > 4 4
> > 5 5
> > 6 6
> > 7 7
> > 8 8
> > 9 9
> >
> >       z[⍳81;(2×81)+⍳81] z[⍳81;(3×81)+⍳81]
> >  1 1
> > 2 2
> > 3 3
> > 4 4
> > 5 5
> > 6 6
> > 7 7
> > 8 8
> > 9 9
> > 1 1
> > 2 2
> > 3 3
> > 4 4
> > 5 5
> > 6 6
> > 7 7
> > 8 8
> > 9 9
> > 1 1
> > 2 2
> > 3 3
> > 4 4
> > 5 5
> > 6 6
> > 7 7
> > 8 8
> > 9 9
> > 1 1
> > 2 2
> > 3 3
> > 4 4
> > 5 5
> > 6 6
> > 7 7
> > 8 8
> > 9 9
> > 1                                                       1
> > 2                                                       2
> > 3                                                       3
> > 4                                                       4
> > 5                                                       5
> > 6                                                       6
> > 7                                                       7
> > 8                                                       8
> > 9                                                       9
> > 1                                              1
> > 2                                              2
> > 3                                              3
> > 4                                              4
> > 5                                              5
> > 6                                              6
> > 7                                              7
> > 8                                              8
> > 9                                              9
> > 1                                              1
> > 2                                              2
> > 3                                              3
> > 4                                              4
> > 5                                              5
> > 6                                              6
> > 7                                              7
> > 8                                              8
> > 9                                              9
> > 1                                     1
> > 2                                     2
> > 3                                     3
> > 4                                     4
> > 5                                     5
> > 6                                     6
> > 7                                     7
> > 8                                     8
> > 9                                     9
> > 1                            1
> > 2                            2
> > 3                            3
> > 4                            4
> > 5                            5
> > 6                            6
> > 7                            7
> > 8                            8
> > 9                            9
> >
> >       ⎕dlx z
> > DOMAIN ERROR
> >       ⎕DLX z
> >       ^    ^
> >
> >
> >
> > On 2016-11-23 10:50, Juergen Sauermann wrote:
> > > Hi,
> > >
> > > i am happy to announce the implementation of a new system
> > > function *⎕DLX* in GNU APL. *SVN 810*.
> > >
> > > *⎕DLX *is an implementation of Donald Knuth's DLX algorithm, which 
> > > is also
> > > known as "Dancing Links" or "Algorithm X".
> > >
> > > *⎕DLX *is a backtracking machinery which can be used to solve problems
> > > that involve backtracking, such as the 8 queens problem or sudokus.
> > >
> > > For example, solving the 8 queens problem (which probably every 
> > > programmer has
> > > tried at some point in time) becomes an APL 3-liner like this with 
> > > *⎕DLX*:
> > >
> > > *      RC←8↑'1' ◊ D←15↑¯8↑'2'   ⍝ helper for constructing Q8
> > >       Q8←⊃{(R⌽RC),(C⌽RC),((C-R)⌽D),((¯7-R+C)⌽D) ⊣ (R C)←-8 8⊤⍵-⎕IO} 
> > > ¨ ⍳64
> > >       Z←⎕DLX Q8   ⍝ solve Q8
> > >
> > >       {⎕UCS (65+⌊⍵÷8) (49+8∣⍵←⍵-⎕IO)} ¨ Z   ⍝ display result
> > >  A1 B6 C8 D3 E7 F4 G2 H5 *
> > >
> > > See *info apl *for details. Sudokus can be solved in a similar way 
> > > and are left as an
> > > exercise for the reader.
> > >
> > > Enjoy,
> > > /// Jürgen