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
