1RS-DLX

A Common Lisp implementation of Knuth's Algorithm X using the dancing links technique.

Knuth's example from the “Dancing Links” paper.

(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

The terminal output is displayed below.

Found a solution containing
first row with columns (C E F)
fourth row with columns (A D)
fifth row with columns (B G)

Of course, the obligatory Sudoku example also exists:

(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))