Programming Challenge Idea: Sudoku Solver

[bassplayinMacFiend]

I've recently discovered the Sudoku number game. See www.sudoku.com for explanation and rules, and visit www.websudoku.com for billions of free games (no, I am not affiliated with either of these sites).

I would be willing to whip up a GUI shell so the focus could be on the algorithm part of the challenge and could have an Xcode project posted by midweek if there was any interest in this.

Since Sudoku is a logic puzzle, there must be some way of computationally calculating the solution to any particular puzzle. I was thinking of using 4 puzzles from websudoku, picking one puzzle from each of the offered categories. The categories are easy, medium, hard and evil.

I'm pretty slow at Sudoku. I can solve an easy puzzle in 10 minutes, give or take, and I spend about an hour solving an evil puzzle. I was thinking a computer should solve an easy problem in a minute or less and say 5 minutes for an evil puzzle. Of course it could take much less time since computers are so fast now.

I'm thinking the winning algorithm could be determined either by how long it takes to solve a puzzle, or how many iterations it takes to solve a puzzle. Or if someone with good analysis skills examined the code the winner could be based on algorithm efficiency.

I don't know if there is solver code already available on the 'net but I would hope that all entries would be the submitter's original code.

So, what do you guys and gals say? Is there any interest in this challenge?

[Kickaha]

Classic constraint problem. :) I bet it could be whipped up in Prolog pretty quickly.

There are five constraints for each cell: local 9x9, row, column, relative row, and relative column. Each constraint set provides a list of numbers that it could possibly be, and not be.

For each cell, hold a list of possible numbers. If the list is of length one, fill it in and remove that number from the related cell constraints.

If no list is of length one, you have to guess. Pick one of the cells with the shortest lengths, and randomly choose one of the numbers in it. Tracking which changes you make, so you can unroll them later, try that number and see what happens. If it solves, great. If not, unroll and try the next number.

That's pretty much the algorithm I use in my own head, right there. I can do the Hard level on that site in under 7 minutes on a fairly regular basis, and have broken 6:15 once.

[bassplayinMacFiend]

I've been doing some googling since I posted this, and there is a cool site (http://www.scanraid.com/sudoku.htm) that has about 9 different algorithms to determine the correct numbers without guessing.

I haven't used guessing in any of the puzzles I've solved including the evil ones. This is why I figured there must be some way to write an algorithm to solve even the toughest puzzles. I never thought there would be so many sudoku solver sites out there though. My google query returned 280,000 hits for 'sudoku solver'. Guess I'm way behind the curve for my idea. :)

Looks like my time estimates were way off as well. The solver sites I tried were able to calculate solutions in seconds.

[bassplayinMacFiend]

Guess you're right about your prolog idea. I found this prolog solver (http://user.it.uu.se/~justin/sudoku.pl).

[pmazer]

Just so you guys are aware, Sudoku has been proven to be an NP-complete problem (like Mindsweeper) so it's impossible to fully solve Sudoku without semi-brute-force.

[Kickaha]

Yes, a general Sudoku solver would be extremely difficult. Do you have a reference on the proof it's NP-hard? A solver that is solving a fairly filled-in puzzle, however, can do so very quickly.

The brute-force comes in when I said "pick one randomly and run with it until you hit a wall" ;)

And basspMf: the one you link to actually does do brute force guessing... that's what he means by 'bifurcation'. He's splitting (bifurcating) the solution space into two choices, and investigating each in turn. Ie, guessing.

[Paul]

That site you linked to seems to have a bug with their algorithms... The Sword-Fish and X-Wing tests can only be run once successfully, a second run from the same page will not produce any output, you need to run it from a fresh reload of the page...

[pmazer]

Kickaha,

There are many proofs on Google, one being on Wikipedia: http://en.wikipedia.org/wiki/Sudoku