How to check if a comon sudoku puzzle is solvable

XML, Perl, Python, and other languages can be discussed here, even if it isn't PHP (We might forgive you).

Moderator: General Moderators

User avatar
pedrotuga
Forum Contributor
Posts: 249
Joined: Tue Dec 13, 2005 11:08 pm

How to check if a comon sudoku puzzle is solvable

Post 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?
User avatar
Kieran Huggins
DevNet Master
Posts: 3635
Joined: Wed Dec 06, 2006 4:14 pm
Location: Toronto, Canada
Contact:

Post 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.
User avatar
pedrotuga
Forum Contributor
Posts: 249
Joined: Tue Dec 13, 2005 11:08 pm

Post 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.
User avatar
Kieran Huggins
DevNet Master
Posts: 3635
Joined: Wed Dec 06, 2006 4:14 pm
Location: Toronto, Canada
Contact:

Post by Kieran Huggins »

sounds like knowing #1 includes knowing #2
User avatar
pedrotuga
Forum Contributor
Posts: 249
Joined: Tue Dec 13, 2005 11:08 pm

Post 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?
User avatar
Kieran Huggins
DevNet Master
Posts: 3635
Joined: Wed Dec 06, 2006 4:14 pm
Location: Toronto, Canada
Contact:

Post by Kieran Huggins »

write an algorithm that solves the puzzle from the initial condition, if it works it's a valid puzzle.
nickvd
DevNet Resident
Posts: 1027
Joined: Thu Mar 10, 2005 5:27 pm
Location: Southern Ontario
Contact:

Post 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 :)
User avatar
Mordred
DevNet Resident
Posts: 1579
Joined: Sun Sep 03, 2006 5:19 am
Location: Sofia, Bulgaria

Re: How to check if a comon sudoku puzzle is solvable

Post 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. ;)
User avatar
Ambush Commander
DevNet Master
Posts: 3698
Joined: Mon Oct 25, 2004 9:29 pm
Location: New Jersey, US

Post by Ambush Commander »

User avatar
Kieran Huggins
DevNet Master
Posts: 3635
Joined: Wed Dec 06, 2006 4:14 pm
Location: Toronto, Canada
Contact:

Post 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.
User avatar
pedrotuga
Forum Contributor
Posts: 249
Joined: Tue Dec 13, 2005 11:08 pm

Post 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?
User avatar
Mordred
DevNet Resident
Posts: 1579
Joined: Sun Sep 03, 2006 5:19 am
Location: Sofia, Bulgaria

Post 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?
User avatar
Kieran Huggins
DevNet Master
Posts: 3635
Joined: Wed Dec 06, 2006 4:14 pm
Location: Toronto, Canada
Contact:

Post 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!
User avatar
jayshields
DevNet Resident
Posts: 1912
Joined: Mon Aug 22, 2005 12:11 pm
Location: Leeds/Manchester, England

Post 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.
User avatar
Mordred
DevNet Resident
Posts: 1579
Joined: Sun Sep 03, 2006 5:19 am
Location: Sofia, Bulgaria

Post 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/

:twisted:
Post Reply