bug-apl
[Top][All Lists]

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

 From: Christian Robert Subject: Re: [Bug-apl] ⎕DLX (2) Date: Thu, 24 Nov 2016 00:34:44 -0500 User-agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.5.0

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

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