Anonymous user
Sudoku: Difference between revisions
Undo revision 68770 by Zinabo (Talk) — Reverting unexplained deletion of Common Lisp example
Line 151:
=={{header|C}}==
See e.g. [http://www.techfinesse.com/game/sudoku_solver.php this GPLed solver] written in C.
=={{header|Common Lisp}}==
A simple solver without optimizations (except for pre-computing the possible entries of a cell).
<lang lisp>(defun row-neighbors (row column grid &aux (neighbors '()))
(dotimes (i 9 neighbors)
(let ((x (aref grid row i)))
(unless (or (eq '_ x) (= i column))
(push x neighbors)))))
(defun column-neighbors (row column grid &aux (neighbors '()))
(dotimes (i 9 neighbors)
(let ((x (aref grid i column)))
(unless (or (eq x '_) (= i row))
(push x neighbors)))))
(defun square-neighbors (row column grid &aux (neighbors '()))
(let* ((rmin (* 3 (floor row 3))) (rmax (+ rmin 3))
(cmin (* 3 (floor column 3))) (cmax (+ cmin 3)))
(do ((r rmin (1+ r))) ((= r rmax) neighbors)
(do ((c cmin (1+ c))) ((= c cmax))
(let ((x (aref grid r c)))
(unless (or (eq x '_) (= r row) (= c column))
(push x neighbors)))))))
(defun choices (row column grid)
(nset-difference
(list 1 2 3 4 5 6 7 8 9)
(nconc (row-neighbors row column grid)
(column-neighbors row column grid)
(square-neighbors row column grid))))
(defun solve (grid &optional (row 0) (column 0))
(cond
((= row 9)
grid)
((= column 9)
(solve grid (1+ row) 0))
((not (eq '_ (aref grid row column)))
(solve grid row (1+ column)))
(t (dolist (choice (choices row column grid) (setf (aref grid row column) '_))
(setf (aref grid row column) choice)
(when (eq grid (solve grid row (1+ column)))
(return grid))))))</lang>
Example:
<pre>> (defparameter *puzzle*
#2A((3 9 4 _ _ 2 6 7 _)
(_ _ _ 3 _ _ 4 _ _)
(5 _ _ 6 9 _ _ 2 _)
(_ 4 5 _ _ _ 9 _ _)
(6 _ _ _ _ _ _ _ 7)
(_ _ 7 _ _ _ 5 8 _)
(_ 1 _ _ 6 7 _ _ 8)
(_ _ 9 _ _ 8 _ _ _)
(_ 2 6 4 _ _ 7 3 5)))
*PUZZLE*
> (pprint (solve *puzzle*))
#2A((3 9 4 8 5 2 6 7 1)
(2 6 8 3 7 1 4 5 9)
(5 7 1 6 9 4 8 2 3)
(1 4 5 7 8 3 9 6 2)
(6 8 2 9 4 5 3 1 7)
(9 3 7 1 2 6 5 8 4)
(4 1 3 5 6 7 2 9 8)
(7 5 9 2 3 8 1 4 6)
(8 2 6 4 1 9 7 3 5))</pre>
=={{header|D}}==
| |||