Sudoku Solver

This file contains a sudoku solver.

• sudoku-solver.lisp

Example:

sudoku-solver> (use-package :com.informatimago.sudoku-solver)tsudoku-solver> (let* ((sudoku #2A((x x x 8 x 4 2 x x)
                                  (6 x 8 x 2 x x x 4)
                                  (2 1 x 6 5 3 x x 8)
                                  (x 7 x 2 x 6 x 9 x)
                                  (x x x x 3 x 1 x x)
                                  (4 2 3 x x 9 x 5 7)
                                  (x 6 x 4 1 5 7 x x)
                                  (x x 7 x x 8 3 x x)
                                  (x 5 9 x x x x 1 x))))
                 (multiple-value-bind (solutions tries) (sudoku-solver sudoku)
                   (terpri)
                   (sudoku-print sudoku)
                   (format t "  has ~D solution~:*~P,~%  found in ~D tries.~2%"
                           (length solutions) tries)
                   (map nil 'sudoku-print solutions)))

+---+---+---+---+---+---+---+---+---+
| .   6   2 | .   .   4 | .   .   . |
|   +   +   |   +   +   |   +   +   |
| .   .   1 | 7   .   2 | 6   .   5 |
|   +   +   |   +   +   |   +   +   |
| .   8   . | .   .   3 | .   7   9 |
+---+---+---+---+---+---+---+---+---+
| 8   .   6 | 2   .   . | 4   .   . |
|   +   +   |   +   +   |   +   +   |
| .   2   5 | .   3   . | 1   .   . |
|   +   +   |   +   +   |   +   +   |
| 4   .   3 | 6   .   9 | 5   8   . |
+---+---+---+---+---+---+---+---+---+
| 2   .   . | .   1   . | 7   3   . |
|   +   +   |   +   +   |   +   +   |
| .   .   . | 9   .   5 | .   .   1 |
|   +   +   |   +   +   |   +   +   |
| .   4   8 | .   .   7 | .   .   . |
+---+---+---+---+---+---+---+---+---+

  has 1 solution,
  found in 44 tries.

+---+---+---+---+---+---+---+---+---+
| 7   6   2 | 5   9   4 | 3   1   8 |
|   +   +   |   +   +   |   +   +   |
| 3   9   1 | 7   8   2 | 6   4   5 |
|   +   +   |   +   +   |   +   +   |
| 5   8   4 | 1   6   3 | 2   7   9 |
+---+---+---+---+---+---+---+---+---+
| 8   7   6 | 2   5   1 | 4   9   3 |
|   +   +   |   +   +   |   +   +   |
| 9   2   5 | 4   3   8 | 1   6   7 |
|   +   +   |   +   +   |   +   +   |
| 4   1   3 | 6   7   9 | 5   8   2 |
+---+---+---+---+---+---+---+---+---+
| 2   5   9 | 8   1   6 | 7   3   4 |
|   +   +   |   +   +   |   +   +   |
| 6   3   7 | 9   4   5 | 8   2   1 |
|   +   +   |   +   +   |   +   +   |
| 1   4   8 | 3   2   7 | 9   5   6 |
+---+---+---+---+---+---+---+---+---+

nilsudoku-solver>