The New Sudoku Players' Forum

[Guest]

Like many others, I've written a solver for Su Doku puzzles:

http://www.blott-online.com/sudoku/index.html

However, my interest here is not actually in solving puzzles, but rather in understanding the underlying rules at play.

Specifically, a solver might be called complete if, for any grid for which a unique solution exists, the solver will find that unique solution.

1) Does a set of heuristics exist such that a solver based on repeatedly applying those heuristics is complete?

2) I know that my own solver is not complete. Perhaps it is the case that no purely logic based solver can be complete. If that is the case, what is a canonical example of a puzzle with a unique solution which logic-based solvers cannot solve?

I'm not interested in solvers based on guessing; enumerating all possibilities is not elegant - even if heuristics are used to reduce the search space.

Please follow up if you have any insight into the completeness of logic-based solvers and their completeness or limitations.

Thanks,
Steve[/url]

[JTM]

Briefly,

Yes it is possible to check the ability of any given solver to solve *every* su doku, but you would have to have a program capable of generating *every* su doku having a unique solution, to test its completeness.

So how do you prove you've generated every sudoku having a unique solution? It's possible, but not easy. And it would take a *very* long time.

Google "NP complete theorem", to find out how hard.

[JTM]

Sorry, didn't answer your questions fully:

1) Does a set of heuristics exist such that a solver based on repeatedly applying those heuristics is complete?

See my previous answer. You'd have to generate every puzzle and wait for your solver to solve all of them. This brings in Turing's Undecidability Theorem...

2) I know that my own solver is not complete. Perhaps it is the case that no purely logic based solver can be complete. If that is the case, what is a canonical example of a puzzle with a unique solution which logic-based solvers cannot solve?

Turing's Undecidability Theorem:

How long does a program need to run to obtain a solution? A second? A day? From now until the end of the universe? (If so, who's going to be around to verify it?)

It can't be proven that a puzzle with a unique solution exists that a logic based solver can't solve, we can never know. Hence heuristics, to give us answers that are near enough as there.

[simes]

You might want to take a look in the programmers forum at http://www.setbb.com/phpbb/?mforum=sudoku. It has discussions on various solving techniques.

[Guest]

Hi:

Today was the first I had ever heard of this Sudoku puzzle. I was able to work through an example puzzle and arrive at the solution. It is challenging, but fairly straight-forward to solve.

That solution process showed me that I can solve Soduku using a technique that is almost identical to how I solve logic problems.

My point is this: it is very easy to create a program that will methodically solve a given Soduku and arrive at the one-and-only answer. There is absolutely no need for any sort of inelegant, brute-force solution method. And THAT means that you can be certain that your solver has arrived at the correct solution.

I will work up a Visual Basic .NET program that can solve these puzzles, but it will take a few days to complete. I'll post back then.

...in the mean time, accept it as your challenge to take another look at these puzzles and try to discover my solution methodology.

Good Luck,
KEITH

[simes]

This message sure looks familiar...

I posted a reply to it in this other thread... http://forum.enjoysudoku.com/viewtopic.php?p=1900#p1900

[amygdala]

Turing's Undecidability Theorem:
[...]
It can't be proven that a puzzle with a unique solution exists that a logic based solver can't solve, we can never know. Hence heuristics, to give us answers that are near enough as there.

Well, doesn't that depend on the heuristics that solve the puzzle, and the problem itself? Not all problems are instances of the halting problem - and until you can prove that Sudoku is, I'm not sure that there are no feasible heuristics, that doesn't include brute-force. Sudoku yilds a very finite search-space, so any arguments based on the halting problem fails miserably.

I wrote a brute-force solver that finds an existing solution, or fails only if none are there (duh just stressing the point, that it does always terminate) - to turn your sentence around, I believe it can be proven, that if there exists a unique solution it WILL be found (at least by brute-force), so of course, it can't be proven that it won't... Because that is a false statement - that is, if you count brute-force as a logic approach to solving, which I certainly do (although it's not exaclty a heuristic as such)...

I'm just trying to make you clarify your statement since I (obviously) didn't quite understand it ;) Not trying to nitpick, I'm just fascinated with computability...

-A