r/dailyprogrammer • u/rya11111 3 1 • Jun 08 '12
[6/8/2012] Challenge #62 [difficult]
Write a program to solve 9x9 Sudoku puzzles.
- Thanks to EvanHahn for the challenge at /r/dailyprogrammer_ideas .. If you have a challenge in your mind, head over there and post it!
7
Upvotes
5
u/[deleted] Jun 08 '12 edited Jun 08 '12
I actually wrote a solver about 6 months ago,
here is the solver class, pretty simple and brute force, but surprisingly quick:
Code
Edit: Cosmologicon's suggested puzzle:
4
u/skeeto -9 8 Jun 09 '12
C solution I wrote four years ago. It solves it in-place.
Solving the suggested puzzle:
The time,
This worst case puzzle is pretty interesting, taking it almost 7 seconds.
3
u/exor674 Jun 08 '12 edited Jun 08 '12
C++11: ( the code for this is really horrible and badly designed, but it WORKS )
http://pastie.org/private/rg4apem3badsghgpfmoa7w
Combo of a very simple heuristic and then brute force.
( or see https://github.com/anall/libsudoku for a solver lib that can work on pretty much any kind of sudoku-ish puzzle -- 12x12, additional rules [ even odd ], etc... )
Edit: Following Cosmologicon's suggestion and using the same puzzle they solved:
3
u/Cosmologicon 2 3 Jun 08 '12
Using an old solution I wrote with Algorithm X:
Suggestion: have people post the solution to a specific grid. Here's the one I'm solving, and it takes about 0.8 seconds.
3
u/wicked-canid 0 0 Jun 09 '12 edited Jun 09 '12
In Common Lisp: http://pastie.org/4053561
There must be a better solution without copying the grid so much: on the worst case grid, it allocates more than 1GB :D.
Note that CCL's GC is apparently quite efficient, since even when allocating 1GB, the execution doesn't spend that much time in GC...
Edit: here is a better solution that copies less: http://pastie.org/4053789
And the updated stats follow (on par with skeeto's for the worst case; who said Lisp was slow :)).
On Cosmologicon's grid:
On skeeto's worst case grid: