40 ms·

Sudoku Solver in Common Lisp (2009)

33 points by deepaksurti 7y ago

deleted 7y ago
[deleted]
gnuvince 7y ago
Damn near impossible to read the code in those blockquote blocks :(
- deepaksurti 7y ago
  A more readable version on github. [1] [1] https://github.com/dmsurti/sudoku https://github.com/dmsurti/sudoku
- goldfishparty 7y ago
  The author doesn't understand what blockquotes are for I think.
notyourwork 7y ago
I enjoy these puzzles a lot in my commute time. Recently on a flight to Germany I built a solver in python. It was a pretty great way to consume a portion of the long flight from US. I’ve recently started reading up on optimization strategies, my first attempt was pretty straightforward. It’s a fun exercise I recommend for anyone who likes solving these puzzles manually.
- pge 7y ago
  If you haven't already seen it, check out Donald Knuth's Dancing Links algorithm for solving sudoku. Here's a good overview and intro (that includes a link to the paper). https://www.kevinhooke.com/2019/01/22/revisiting-donald-knuths-algorithm-x-and-dancing-links-to-solve-sudoku-puzzles/ https://www.kevinhooke.com/2019/01/22/revisiting-donald-knut...
doc_gunthrop 7y ago
If anyone is interested in these kind of coding challenges, there are a few Sudoku solver puzzles on Codewars: https://www.codewars.com/kata/search/?q=sudoku https://www.codewars.com/kata/search/?q=sudoku
chaoticmass 7y ago
I wrote a sudoku solver in Visual Basic 5 many years ago. I've lost the source code to it but I remember the algorithm mostly. I've been meaning to re-implement it in a new language as a learning/practice exercise.
goric 7y ago
If you found this interesting, see also Norvig's Sudoku Solver [1], with an implementation in Python. [1] http://norvig.com/sudoku.html http://norvig.com/sudoku.html
nickcw 7y ago
I had a go at solving sudokos, but I found the experience tedious, mechanical and far too easy to make a mistake. In fact just the frustration inducing thing to tickle the first of the virtues of a programmer: "Laziness". I then wrote a solver in Python which was far more fun than solving sudokus by hand and has the advantage that I never need to solve one of the dratted puzzles again ;-) I recommend it as an exercise for all programmers! I didn't document that process, but I did for solving a different puzzle which you may enjoy if you need inspiration: https://www.craig-wood.com/nick/articles/snake-puzzle/ https://www.craig-wood.com/nick/articles/snake-puzzle/
- eralps 7y ago
  I enjoy solving Sudoku puzzles. I had a puzzle book that I solve everyday on commute to school. Then I created a solver in Python as well, it uses backtracking. It can solve the puzzle instantly. Never solved another sudoku puzzle ever since.
pretty_dumm_guy 7y ago
One could also write a sudoku solver in z3. I did this for an assignment and it was fun. I have never programmed in Lisp before but there seems to be some similarity between them.
vyuh 7y ago
I wrote a program that generates all sudokus that satisfy constraints given in a partially filled grid. I thought it might be feasible to find out the distribution of 81 digit numbers that are valid Sudokus by such brute force. Since there are so many sudokus, I made the program capable of resuming an interrupted computation using a dump file. All this I did in C. It was quite a learning experience. Here goes: (https://github.com/vyuh/sud.c https://github.com/vyuh/sud.c) For some fun I also translated the algorithm to Javascript (https://github.com/vyuh/sud.js https://github.com/vyuh/sud.js) and Java (https://github.com/vyuh/sudoku-lister/blob/master/java/sudoku/s00d.java https://github.com/vyuh/sudoku-lister/blob/master/java/sudok...). The javascript code is used in a toy browser application i made (https://su-do-ku.herokuapp.com/ https://su-do-ku.herokuapp.com/). Some day I might generalize the program to larger Latin Squares (https://en.wikipedia.org/wiki/Latin_square https://en.wikipedia.org/wiki/Latin_square).

33 points by deepaksurti 7y ago

deleted 7y ago

[deleted]

gnuvince 7y ago

Damn near impossible to read the code in those blockquote blocks :(

deepaksurti 7y ago
A more readable version on github. [1] [1] https://github.com/dmsurti/sudoku https://github.com/dmsurti/sudoku
goldfishparty 7y ago
The author doesn't understand what blockquotes are for I think.

notyourwork 7y ago

I enjoy these puzzles a lot in my commute time. Recently on a flight to Germany I built a solver in python. It was a pretty great way to consume a portion of the long flight from US. I’ve recently started reading up on optimization strategies, my first attempt was pretty straightforward. It’s a fun exercise I recommend for anyone who likes solving these puzzles manually.

pge 7y ago
If you haven't already seen it, check out Donald Knuth's Dancing Links algorithm for solving sudoku. Here's a good overview and intro (that includes a link to the paper). https://www.kevinhooke.com/2019/01/22/revisiting-donald-knuths-algorithm-x-and-dancing-links-to-solve-sudoku-puzzles/ https://www.kevinhooke.com/2019/01/22/revisiting-donald-knut...

doc_gunthrop 7y ago

If anyone is interested in these kind of coding challenges, there are a few Sudoku solver puzzles on Codewars: https://www.codewars.com/kata/search/?q=sudoku https://www.codewars.com/kata/search/?q=sudoku

chaoticmass 7y ago

I wrote a sudoku solver in Visual Basic 5 many years ago. I've lost the source code to it but I remember the algorithm mostly. I've been meaning to re-implement it in a new language as a learning/practice exercise.

goric 7y ago

If you found this interesting, see also Norvig's Sudoku Solver [1], with an implementation in Python. [1] http://norvig.com/sudoku.html http://norvig.com/sudoku.html

nickcw 7y ago

I had a go at solving sudokos, but I found the experience tedious, mechanical and far too easy to make a mistake. In fact just the frustration inducing thing to tickle the first of the virtues of a programmer: "Laziness". I then wrote a solver in Python which was far more fun than solving sudokus by hand and has the advantage that I never need to solve one of the dratted puzzles again ;-) I recommend it as an exercise for all programmers! I didn't document that process, but I did for solving a different puzzle which you may enjoy if you need inspiration: https://www.craig-wood.com/nick/articles/snake-puzzle/ https://www.craig-wood.com/nick/articles/snake-puzzle/

eralps 7y ago
I enjoy solving Sudoku puzzles. I had a puzzle book that I solve everyday on commute to school. Then I created a solver in Python as well, it uses backtracking. It can solve the puzzle instantly. Never solved another sudoku puzzle ever since.

pretty_dumm_guy 7y ago

One could also write a sudoku solver in z3. I did this for an assignment and it was fun. I have never programmed in Lisp before but there seems to be some similarity between them.

vyuh 7y ago

I wrote a program that generates all sudokus that satisfy constraints given in a partially filled grid. I thought it might be feasible to find out the distribution of 81 digit numbers that are valid Sudokus by such brute force. Since there are so many sudokus, I made the program capable of resuming an interrupted computation using a dump file. All this I did in C. It was quite a learning experience. Here goes: (https://github.com/vyuh/sud.c https://github.com/vyuh/sud.c) For some fun I also translated the algorithm to Javascript (https://github.com/vyuh/sud.js https://github.com/vyuh/sud.js) and Java (https://github.com/vyuh/sudoku-lister/blob/master/java/sudoku/s00d.java https://github.com/vyuh/sudoku-lister/blob/master/java/sudok...). The javascript code is used in a toy browser application i made (https://su-do-ku.herokuapp.com/ https://su-do-ku.herokuapp.com/). Some day I might generalize the program to larger Latin Squares (https://en.wikipedia.org/wiki/Latin_square https://en.wikipedia.org/wiki/Latin_square).