## 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 . 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)

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.