bug-apl
[Top][All Lists]

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

 From: Juergen Sauermann Subject: Re: [Bug-apl] ⎕DLX (2) Date: Thu, 24 Nov 2016 12:56:11 +0100 User-agent: Mozilla/5.0 (X11; Linux i686; rv:45.0) Gecko/20100101 Thunderbird/45.2.0

```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.

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
```
```

```
```

```