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