How to check if a comon sudoku puzzle is solvable
Moderator: General Moderators
How to check if a comon sudoku puzzle is solvable
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?
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?
- Kieran Huggins
- DevNet Master
- Posts: 3635
- Joined: Wed Dec 06, 2006 4:14 pm
- Location: Toronto, Canada
- Contact:
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.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.
- Kieran Huggins
- DevNet Master
- Posts: 3635
- Joined: Wed Dec 06, 2006 4:14 pm
- Location: Toronto, Canada
- Contact:
- Kieran Huggins
- DevNet Master
- Posts: 3635
- Joined: Wed Dec 06, 2006 4:14 pm
- Location: Toronto, Canada
- Contact:
Re: How to check if a comon sudoku puzzle is solvable
Famous last words #324pedrotuga wrote:...so i will just use trackback.
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.
- Ambush Commander
- DevNet Master
- Posts: 3698
- Joined: Mon Oct 25, 2004 9:29 pm
- Location: New Jersey, US
- Kieran Huggins
- DevNet Master
- Posts: 3635
- Joined: Wed Dec 06, 2006 4:14 pm
- Location: Toronto, Canada
- Contact:
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.
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.
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?
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?
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.
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?
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.
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.I will check column, line and region ( 3x3 ) uniqueness. I think that reduces the possibilites pretty much.
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?
- Kieran Huggins
- DevNet Master
- Posts: 3635
- Joined: Wed Dec 06, 2006 4:14 pm
- Location: Toronto, Canada
- Contact:
- jayshields
- DevNet Resident
- Posts: 1912
- Joined: Mon Aug 22, 2005 12:11 pm
- Location: Leeds/Manchester, England
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.
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.
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/

http://www.afjarvis.staff.shef.ac.uk/sudoku/