rs-dlx

* RS-DLX

A Common Lisp implementation of [[https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X][Knuth's Algorithm X]] using the
[[https://en.wikipedia.org/wiki/Dancing_Links][dancing links]] technique.

Knuth's example from the “[[https://arxiv.org/abs/cs/0011047][Dancing Links]]” paper.
#+BEGIN_EXAMPLE lisp
(ql:quickload "rs-dlx")
(use-package :rs-dlx)

;; Define the incidence matrix.
(setf a (matrix-from-array #2A((0 0 1 0 1 1 0)
                               (1 0 0 1 0 0 1)
                               (0 1 1 0 0 1 0)
                               (1 0 0 1 0 0 0)
                               (0 1 0 0 0 0 1)
                               (0 0 0 1 1 0 1))))
 ⇒ #<ROOT (6 7)>

(setf (column-names a) '(A B C D E F G))
 ⇒ (A B C D E F G)

;; Find a solution.
(setf s (first (solve a)))
 ⇒ (0 3 4)

;; Print the result.
(progn
  (format t "Found a solution containing~%")
  (dolist (i s)
    (format t "~:R row with columns ~S~%"
            (1+ i) (map-matrix-row #'column-name a i))))
 ⇒ nil
#+END_EXAMPLE
The terminal output is displayed below.
#+BEGIN_EXAMPLE
Found a solution containing
first row with columns (C E F)
fourth row with columns (A D)
fifth row with columns (B G)
#+END_EXAMPLE

Of course, the obligatory Sudoku example also exists:
#+BEGIN_EXAMPLE lisp
(ql:quickload "rs-dlx/sudoku")

(rs-dlx-sudoku:solve
 "..569...."
 ".3......9"
 "..8....1."
 "47..3...."
 "1....4..8"
 ".....7..."
 "......471"
 "...2..3.."
 "...3.58..")
 ⇒ #2A((7 1 5 6 9 8 2 4 3)
       (6 3 4 7 1 2 5 8 9)
       (2 9 8 4 5 3 6 1 7)
       (4 7 6 8 3 9 1 5 2)
       (1 2 9 5 6 4 7 3 8)
       (5 8 3 1 2 7 9 6 4)
       (3 5 2 9 8 6 4 7 1)
       (8 6 7 2 4 1 3 9 5)
       (9 4 1 3 7 5 8 2 6))
#+END_EXAMPLE


rs-dlx

Upstream URL

Author

License

rs-dlx

Version:

License:

Authors:

Dependencies:

rs-dlx/sudoku

License:

Authors:

Dependencies:

rs-dlx/tests

License:

Authors:

Dependencies:

Dependencies (3)

Dependents (0)