Page 1 of 2
How to check if a comon sudoku puzzle is solvable
Posted: Sun Feb 18, 2007 12:05 am
by pedrotuga
I am writing a sudoku solver in python. It will solve the popular 9x9 puzzles.
I want to keep the code simple so i will just use trackback. A cool feature would be a an web form where users would submit their puzzles so i could add them to my puzzle database. But in order to do that i need to check if the puzzle is solvable.
Not if there is a layout of numbers that validate in the end, but if there is one unique solution that can be achieved from the initial set of filled number.
Is it be possible to perform such a checking?
Posted: Sun Feb 18, 2007 12:22 am
by Kieran Huggins
It's doable for sure - just try to figure out the algorithm you use when doing them by hand, then try to re-create it as the mother of all a recursive functions.
Posted: Sun Feb 18, 2007 12:27 am
by pedrotuga
Kieran Huggins wrote:It's doable for sure - just try to figure out the algorithm you use when doing them by hand, then try to re-create it as the mother of all a recursive functions.
The problem is me not knowing how to do it by hand. Remember i want to check if the initial condition is enough to solve a puzzle, not if there is a valid puzzle that includes the initial condition.
Posted: Sun Feb 18, 2007 12:36 am
by Kieran Huggins
sounds like knowing #1 includes knowing #2
Posted: Sun Feb 18, 2007 1:19 am
by pedrotuga
Kieran Huggins wrote:sounds like knowing #1 includes knowing #2
that's right, it does, but they are not the same thing.
If i start to solve the puzzle right after i and i get true i verify #2 but not #1. Now... how do i verify #1?
Posted: Sun Feb 18, 2007 2:11 am
by Kieran Huggins
write an algorithm that solves the puzzle from the initial condition, if it works it's a valid puzzle.
Posted: Sun Feb 18, 2007 3:43 am
by nickvd
I remember seeing a one line ... python? script posted on digg a while back. I don't 'get' sudoku, so I didn't really pay much attention

Re: How to check if a comon sudoku puzzle is solvable
Posted: Sun Feb 18, 2007 5:15 am
by Mordred
pedrotuga wrote:...so i will just use trackback.
Famous last words #324
Are you aware of the amount ot backtracking (btw, it's backtracking, not trackback) calls you'll have to make? If you're planning to do this each time a user submits a sudoku, you might as well just put a button that says "DOS me".
What you better do is make a quick and dirty partial solver - for example just check the possibilities in the current state, if there are solvable squares, solve them and proceed until the partial solver cannot do any more work. Push the state on a stack and start backtracking on a cell with a minimum amount of variants (pull a random between them, if there are many). After each backtracking step you run the partial solver, hoping that it will either solve or disprove the sudoku right away, or it will lift some weigh off the backtracker.
If you want a faster solver, write a smarter partial solver. I've seen a forum for sudoku solver coders, check them out for useful tips.
Btw, I've written a partial sudoku solver with a neural network (I'm actually just using neurons as a means for parallelisation) - it is slow, compared to a "real" solver, but if you have a real parallel hardware (and not just emulate it on a PC) it will work several times faster, IIRC it solved the "easy" sudokus in something like 10-15 steps.

Posted: Sun Feb 18, 2007 1:23 pm
by Ambush Commander
Posted: Sun Feb 18, 2007 4:34 pm
by Kieran Huggins
I started writing one last night when I got tired of staring at the same old code.. it's kinda fun! Mine solves easy and medium puzzles in < 6 steps, but it chokes on hard and evil puzzles. I'm going to implement "guess forking" later today and see if that's enough to square things away - I'll post the code in another thread when I'm done.
Maybe we should all build sudoku solvers, or at least refactor each other's? Sounds like a fun project for phpdn, and a good way to compare our relative coding styles / approaches.
Posted: Mon Feb 19, 2007 3:01 am
by pedrotuga
Mordred, i am not willing to make an insert-your-puzzle-we-solve it webpage nor creating a widely used application.
Of course that would be a DoS me atitude, i am very aware of that.
The reason why i writing this is because i am trying to find out the wonders of python everybody talk about. I cant find them. If i would just need to solve a problem i would just use PHP which i am far more productive on.
About all the "oh mine is not brute force" talk out there ( i don't mean specific in this thread ) it's a whole theory world that i don't really get the point. Like.. is i have to perform a bigger amount of operations to put out a smaller number of possibilities i dont get the "less iterations" expression meaning.
I will check column, line and region ( 3x3 ) uniqueness. I think that reduces the possibilites pretty much.
Anyway.. the wikipedia link didn't had any description of any checking method.
About all of us making a solver and comparing code styles, no prob. I can post my code.
Back to the original question. Does anybodyknows how to check if a puzzle is possible?
Posted: Mon Feb 19, 2007 4:41 am
by Mordred
A puzzle is solvable if your solver can solve it

Actually not quite, by definition a sudoku puzzle is required to have a unique solution, which means you have to backtrack all the way through, instead of stopping at the first found solution, but this is an easy modification.
I will check column, line and region ( 3x3 ) uniqueness. I think that reduces the possibilites pretty much.
For easy and medium puzzles - yes, pretty much, and the other iterative (as opposed to recursive = trial and error) checks are quite a PITA to implement IIRC.
Some links from the comments of my code:
http://www.angusj.com/sudoku/hints.php (iterative solving)
http://www.setbb.com/sudoku/ (coders forum)
@
Kieran Huggins: You are aware that
"guess forking" is in fact backtracking, i.e. you have no guarantee that
one forking will solve the puzzle?
Posted: Mon Feb 19, 2007 9:34 am
by Kieran Huggins
Yeah - I've been using probability methods to optimize the order of the fork trials, but it would try every combination by the end of the puzzle (if needs be).
I never considered that you'd have to test for exactly one solution... I guess I will be crunching every fork after all!
Posted: Mon Feb 19, 2007 10:09 am
by jayshields
Wouldn't it be easier to develop a script that creates every unique (finished) Sudoku puzzle possible and then check if a puzzle is solvable by checking it against your pre-made puzzles?
It sounds stupid at first, but if you think about it, after a few "evil" level puzzles have been put through your "check if it's solvable" script you will have probably done all the calculations to make every unique (finished) Sudoku puzzle possible.
I haven't really thought about the above in enough detail to say it's completely true, but it's just something I wanted to throw out there.
Posted: Mon Feb 19, 2007 10:21 am
by Mordred
Right. Just make sure your id column in the database is not int, as the autoincrement will overflow...
http://www.afjarvis.staff.shef.ac.uk/sudoku/
