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.
Note that this example won't run on ESP32 boards because they don't have enough stack space.
Description
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 board such as the Adafruit PyBadge the "world's hardest Sudoku" takes approximately 128 seconds to solve.
Here's the whole Sudoku program in a single file: Sudoku solver program.
Addendum
For a more efficient program for solving Sudoku puzzles, with an interesting discussion of the approach, see Peter Norvig's Solving Every Sudoku Puzzle.
- ^ Sudokiller.lisp on Kernel-Panic.