[Bug-apl] ⎕DLX

[Juergen Sauermann]

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