rs-dlx
2024-10-12
Knuth's Algorithm X with dancing links.
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)))) ⇒ nilThe 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))