Sudoku solver

This sudoku solver demonstrates the new array and format features in uLisp Version 3.2. It is based on a program by Daniele Mazzocchio [1]. It will run on the Adafruit ARM M4 boards or the RISC-V boards.

First you define the problem, using 0 for empty cells. This is one designed by Dr Arto Inkala of Finland, said to be the hardest sudoku in the world!

(defvar board
  #2a((0 0 5 3 0 0 0 0 0)
      (8 0 0 0 0 0 0 2 0)
      (0 7 0 0 1 0 5 0 0)
      (4 0 0 0 0 5 3 0 0)
      (0 1 0 0 7 0 0 0 6)
      (0 0 3 2 0 0 0 8 0)
      (0 6 0 5 0 0 0 0 9)
      (0 0 4 0 0 0 0 3 0)
      (0 0 0 0 0 9 7 0 0)))

Note that the program fills in the array as it solves the sudoku, so if you want to run it again you need to reinitialise the array.

Here's the program:

(defun guess (index)
  (let ((row (truncate index 9))
        (col (mod index 9)))
    (cond
     ((or (>= row 9) (>= col 9)) t)
     ((plusp (aref board row col)) (guess (1+ index)))
     (t
      (dotimes (i 9 (fail row col))
        (when (check (1+ i) row col)
          (setf (aref board row col) (1+ i))
          (when (guess (1+ index)) (return t))))))))

(defun fail (row col)
  (setf (aref board row col) 0)
  nil)

The guess routine calls check to check that the number is the current cell obeys the sudoku rules:

(defun check (num row col)
  (let ((r (* (truncate row 3) 3))
        (c (* (truncate col 3) 3)))
    (dotimes (i 9 t)
      (when (or (= num (aref board row i))
                (= num (aref board i col))
                (= num (aref board (+ r (mod i 3))
                             (+ c (truncate i 3)))))
        (return nil)))))

Finally, print-board uses format statements to print the solution in a readable layout:

(defun print-board ()
  (dotimes (r 9)
    (if (zerop (mod r 3))
        (format t "~%+---+---+---+---+---+---+---+---+---+~%|") 
      (format t "~%+           +           +           +~%|"))
    (dotimes (c 9)
      (if (= 2 (mod c 3))
          (format t " ~a |" (aref board r c))
        (format t " ~a  " (aref board r c)))))
  (format t "~%+---+---+---+---+---+---+---+---+---+~%~%"))

To run the program call (solve):

(defun solve ()
  (if (guess 0) (print-board)
    (format t "Sorry, solution not found...")))

The program prints out the solution; for example here's the solution to a different sudoku, in case you want to try solving the world's hardest sudoku by hand before running the program.

> (solve)

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

On an ATSAMD51-based Adafruit PyBadge the world's hardest sudoku takes approximately 2.5 minutes to solve.

Here's the whole sudoku program in a single file: Sudoku solver program.


  1. ^ Sudokiller.lisp on Kernel-Panic.