Soduko Theory

[Guest slacker]

In the UK, Soduko is currently quite popular - daily puzzles in the Telegraph & Times newspapers I believe.

 

I wrote a program that solves these instantaneously, just using logic. On some puzzles, the two logic functions I repeatedly call may grind to a halt so I added a "guess" stage that takes a each possible value left for each unknown cell in turn and tries to continue logically. I have found that this has solved all the puzzles it has come across.

 

On the Telegraph web page, there is a PDF guide where a "Truly diabolical" puzzle is defined as one where you have to "guess" at more than one stage. However, the example given can be solved by a single "guess stage".

 

My question: Is there a proof that no Soduko requires more than one guess stage? If these truly diabolical sodukos exist, I'll just add recursion to my guess code but I won't bother if it is redundant.

[5614]

On the off chance the guy comes back:

 

It would depend on the individual puzzle, it would be possible to create one yes... I mean, if you left a blank table the first few numbers could be inserted, effectively, anywhere... now whilst you don't get blank tables it is theoretically possible.

 

Also would it be possible for me to get a copy of that program?!?

[Guest Steevo]

We also started the Soduko puzzles in the Sydney Morning Herald and I thought, why only solve the puzzle in front of me when I could work out how to solve them all..

 

It's not quite finished, it needs a tidy up to make it 'user friendly' but it does the job in under 5 seconds. In the end it will involve user input when a guess is required. And will hopefully roll back the programmed 'guesses' if the user's guess is no good.

 

PM me if you want a copy of the finished product... If you think I'm a spoiler then don't ask for a copy of the app.

 

Cheers

 

Steve

[gordex]

Well, I've found the ultimate soduko site -- it has a tutorial, a solver, some links and alot of PDF files with soduko puzzles, with different dificullities (I think they add new boards all the time). It is at: http://sudoku.hapetekhasagol.com

[gnpatterson]

To address the original question. If you have an perfectly logical method you should not need to guess at all, even with the most difficult puzzle. I have done a many of the "evil" class of puzzle but have not had to "guess" though I use some pencil marks to add information to the puzzle.

[Dreamtime]

Right, the truth is that you do not ever need to guess.

The mathematical proof is simple: If you need to guess, there are several solutions (at least at one point) and that makes the soduko invalid.

 

Also, I have constructed a program that uses pattern matching to solve sodukos. As far as I know, I am the first one who does not need to resort to brute force. With a little optimisation of my implementation, that should be the fastest algorithm possible. It is completely deterministic, too (meaning: You cannot get stuck and you always obtain the only solution in a finite number of steps).

If you are interested, I can explain the idea behind my algorithm to you.

[Dreamtime]

PS: The number of steps needed in my algorithm is very limited and you won't have to wait even one second for the solution to drop (no matter how hard the soduko is). Although, I must admit that my implementation is very cumbersome as it is now. I do a lot of conversions between different views of the data involved.

I was too eager to try it out, so I didn't have time to straighten it out.

[RyanJ]

This may prove interesting for you. Its a new technique for solving soduko using SQL Never seen SQL used like this before so I foudn it quite interesting.

 

Cheers,

 

Ryan Jones

[swansont]

Right' date=' the truth is that you do not ever need to guess.

The mathematical proof is simple: If you need to guess, there are several solutions (at least at one point) and that makes the soduko invalid.

[/quote']

 

 

What do you mean by invalid?

 

I was under the impression that the difficulty level was related to how overconstrained the problem was. If, because of the given intitial information, the problem is underconstrained, you would have to guess, but does that Sudoku have only one solution, or are there several possible solutions?

[RyanJ]

What do you mean by invalid?

 

I was under the impression that the difficulty level was related to how overconstrained the problem was. If' date=' because of the given intitial information, the problem is underconstrained, you would have to guess, but does that Sudoku have only one solution, or are there several possible solutions?[/quote']

 

They are normally designed to only allow 1 solution but I have seen a few cases that have had 2 or three

 

Cheers,

 

Ryan Jones

[Dreamtime]

What do you mean by invalid?

 

I was under the impression that the difficulty level was related to how overconstrained the problem was. If' date=' because of the given intitial information, the problem is underconstrained, you would have to guess, but does that Sudoku have only one solution, or are there several possible solutions?[/quote']

 

Well, if "the problem is underconstrained", then it has several solutions. It's like an equation system with fewer equations than variables.

By the way, does anybody have an answer to the following questions: How do you determine, if the Soduko is neither overconstrained nor underconstrained, that is to say it has one solution and absolutely no redundant information? How do you construct such a Soduko and how many numbers must be given at least?

 

I thought the whole point of a Soduko was to solve it, so what good is a Soduko that has several solutions?

I haven't seen an exact mathematical definition of a Soduko yet, but in my eyes, it is like a system of equations, which is designed to be solved unambiguously. It gives an incomplete view of one single complete grid of numbers.

So I call a Soduko "invalid", if it has more than one solution, because then you cannot solve it properly. You are never "done", since you have at least two empty spots left.

 

Note: Several different Sodukos may have the same solution, since you can choose which numbers you get from the beginning.

Also note: Having to guess is not a necessity in itself, it's only the way we think that is flawed. If you can truly see the whole structure of the Soduko (like my program), you do not need to guess (according to my definition of "invalid"). There is only one pattern that combines with the other patterns (if you define a pattern as matching part of the solution).

[Dreamtime]

This may prove interesting for you. Its a new technique for solving soduko using SQL Never seen SQL used like this before so I foudn it quite interesting.

 

Cheers' date='

 

Ryan Jones[/quote']

 

Very interesting.

 

But still, it keeps staring at one cell at a time. It doesn't see the whole picture.

Programming like that is not ideal, your program might miss something.

Just an aside: My program doesn't use a procedural language, either. I have chosen Erlang, because functional programming languages are very suitable for solving these kind of problems recursively.

[RyanJ]

Very interesting.

 

But still' date=' it keeps staring at one cell at a time. It doesn't see the whole picture.

Programming like that is not ideal, your program might miss something.

Just an aside: My program doesn't use a procedural language, either. I have chosen Erlang, because functional programming languages are very suitable for solving these kind of problems recursively. [/quote']

 

Yes it does go through a single cell unit at one item and so it is very ineffecive. I have seen ideas for adaptive and progressive addaption where the algorithm uses all the values in the table at the same time in an attempt to get a result more quickly. Unfortunatly they were in a magazine and I have yet to find a working example online

 

Cheers,

 

Ryan Jones