Sudoku: Difference between revisions
Content deleted Content added
sudoku solver in common lisp |
|||
Line 84: | Line 84: | ||
=={{header|C}}== |
=={{header|C}}== |
||
See e.g. [http://www.techfinesse.com/game/sudoku_solver.php this GPLed solver] written in 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))) ((eql r rmax) neighbors) |
|||
(do ((c cmin (1+ c))) ((eql 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 |
|||
((eql row 9) |
|||
grid) |
|||
((eql column 9) |
|||
(solve grid (1+ row) 0)) |
|||
((numberp (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|J}}== |
=={{header|J}}== |