I’ve released an updated version of the beta release of ARM uLisp, adding a few features to the first beta release. For details of the features in the first beta see: New beta version of ARM uLisp with new features for feedback.
Get the new release from GitHub here: uLisp ARM Beta.
The main new features are:
- More helpful error messages from format; for example
> (format t "The result is ~a ~q" 42)
The result is 42
"The result is ~a ~q"
^
Error: 'format' invalid directive
- The ability to predefine a one-dimensional or two-dimensional array; for example:
> (defvar a #2a((1 2 3) (4 5 6)))
a
> a
#2A((1 2 3) (4 5 6))
Sudoku solver
Here’s an amusing sudoku solver that I’ve been using as a benchmark; it demonstrates the new array and format features. It is based on a program by Daniele Mazzocchio of Kernel Panic: Sudokiller.lisp.
First you define the problem, using 0 for empty cells. This is one designed by Dr Arto Inkala of Finland, said to be the world’s hardest sudoku!
(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.