Sudoku Solver
in [Lisp]
|
Prev: Where To Begin
Next: What is the best Open-Source Lisp?
From: Frank Buss on 20 Feb 2006 16:44 Just a minor cleanup of the code I wrote some months ago, because I wrote a letter to the editor of the german issue of Scientific American, because the author of an article about Sudoku wrote, that it is possible to write a solver in a few hundred lines of Prolog, so I thought it is a good idea to write it in 50 lines of Common Lisp :-) http://www.frank-buss.de/lisp/sudoku.html -- Frank Buss, fb(a)frank-buss.de http://www.frank-buss.de, http://www.it4-systems.de
From: PeateyK on 20 Feb 2006 17:02 Frank Buss wrote: > Just a minor cleanup of the code I wrote some months ago, because I wrote a > letter to the editor of the german issue of Scientific American, because > the author of an article about Sudoku wrote, that it is possible to write a > solver in a few hundred lines of Prolog, so I thought it is a good idea to > write it in 50 lines of Common Lisp :-) > > http://www.frank-buss.de/lisp/sudoku.html > > -- > Frank Buss, fb(a)frank-buss.de > http://www.frank-buss.de, http://www.it4-systems.de Thanks Frank, your version is easier to understand than this one, which may be faster but longer and more difficult to grok for me: http://www.jalat.com/blogs/lisp?id=4
From: Marcin 'Qrczak' Kowalczyk on 20 Feb 2006 19:22 Frank Buss <fb(a)frank-buss.de> writes: > Just a minor cleanup of the code I wrote some months ago, because > I wrote a letter to the editor of the german issue of Scientific > American, because the author of an article about Sudoku wrote, that > it is possible to write a solver in a few hundred lines of Prolog, > so I thought it is a good idea to write it in 50 lines of Common > Lisp :-) > > http://www.frank-buss.de/lisp/sudoku.html I translated it straightforwardly to my language Kogut. It came a little bit shorter: http://cvs.sourceforge.net/viewcvs.py/kokogut/kokogut/examples/small/Sudoku.ko?view=markup -- __("< Marcin Kowalczyk \__/ qrczak(a)knm.org.pl ^^ http://qrnik.knm.org.pl/~qrczak/
From: Jon Harrop on 20 Feb 2006 19:32 Frank Buss wrote: > Just a minor cleanup of the code I wrote some months ago, because I wrote > a letter to the editor of the german issue of Scientific American, because > the author of an article about Sudoku wrote, that it is possible to write > a solver in a few hundred lines of Prolog, so I thought it is a good idea > to write it in 50 lines of Common Lisp :-) > > http://www.frank-buss.de/lisp/sudoku.html Wow, that's huge! You should try writing a short program. ;-) http://www.ffconsultancy.com/free/sudoku -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/products/ocaml_for_scientists/chapter1.html
From: Wade Humeniuk on 20 Feb 2006 20:28
Marcin 'Qrczak' Kowalczyk wrote: > Frank Buss <fb(a)frank-buss.de> writes: > >> Just a minor cleanup of the code I wrote some months ago, because >> I wrote a letter to the editor of the german issue of Scientific >> American, because the author of an article about Sudoku wrote, that >> it is possible to write a solver in a few hundred lines of Prolog, >> so I thought it is a good idea to write it in 50 lines of Common >> Lisp :-) >> >> http://www.frank-buss.de/lisp/sudoku.html > > I translated it straightforwardly to my language Kogut. > It came a little bit shorter: > > http://cvs.sourceforge.net/viewcvs.py/kokogut/kokogut/examples/small/Sudoku.ko?view=markup > Editing Frank's slightly we can get, (30 lines) (defun digits-in-region (sudoku x y) (loop repeat 3 for x from (* 3 (floor x 3)) append (loop repeat 3 for y from (* 3 (floor y 3)) for digit = (aref sudoku y x) unless (zerop digit) collect digit))) (defun digits-in-row (sudoku y) (remove-if #'zerop (loop for x from 0 below 9 collect (aref sudoku y x)))) (defun digits-in-column (sudoku x) (remove-if #'zerop (loop for y from 0 below 9 collect (aref sudoku y x)))) (defun create-missing (list) (set-difference '(1 2 3 4 5 6 7 8 9) list)) (defun possible-digits (sudoku x y) (create-missing (union (digits-in-region sudoku x y) (union (digits-in-row sudoku y) (digits-in-column sudoku x))))) (defun solve-next (sudoku x y) (when (= y 9) (throw 'done sudoku)) (multiple-value-bind (nextx nexty) (if (< x 8) (values (1+ x) y) (values 0 (1+ y))) (if (/= 0 (aref sudoku y x)) (solve-next sudoku nextx nexty) (dolist (digit (possible-digits sudoku x y)) (setf (aref sudoku y x) digit) (solve-next sudoku nextx nexty) (setf (aref sudoku y x) 0))))) (defun solve (sudoku) (pprint (catch 'done (solve-next (make-array '(9 9) :initial-contents sudoku) 0 0)))) CL-USER 30 > (time (solve '((0 0 2 3 0 0 7 0 0) (0 0 4 0 0 9 0 0 0) (6 0 0 0 0 0 0 5 0) (0 7 0 0 0 2 0 6 0) (0 0 3 7 0 0 4 0 0) (0 1 0 0 0 0 0 2 0) (0 3 0 0 0 0 0 0 9) (0 0 0 4 0 0 6 0 0) (0 0 5 0 0 8 2 0 0)))) Timing the evaluation of (SOLVE (QUOTE ((0 0 2 3 0 0 7 0 0) (0 0 4 0 0 9 0 0 0) (6 0 0 0 0 0 0 5 0) (0 7 0 0 0 2 0 6 0) (0 0 3 7 0 0 4 0 0) (0 1 0 0 0 0 0 2 0) (0 3 0 0 0 0 0 0 9) (0 0 0 4 0 0 6 0 0) (0 0 5 0 0 8 2 0 0)))) #2A((1 8 2 3 5 6 7 9 4) (3 5 4 2 7 9 8 1 6) (6 9 7 8 1 4 3 5 2) (4 7 9 5 8 2 1 6 3) (2 6 3 7 9 1 4 8 5) (5 1 8 6 4 3 9 2 7) (8 3 6 1 2 7 5 4 9) (9 2 1 4 3 5 6 7 8) (7 4 5 9 6 8 2 3 1)) user time = 0.260 system time = 0.000 Elapsed time = 0:00:00 Allocation = 4240 bytes standard / 6672017 bytes conses 0 Page faults Calls to %EVAL 34 CL-USER 31 > |