Are *all* Sudoku configurations solvable?

Factual Questions
21

[QUOTE=Blaster Master]
That would be difficult to prove. They only way you can say it has a unique solution is by running it through a Sudoku solver and verifying that, when the series of known Sudoku rules are applied iteratively, it produces a unique solution. That is, IF there is only a single solution, that information MUST be somehow within the puzzle, and so there must be some for of logic that can extract that information, otherwise, it wouldn’t dictate a single solution.

[/quote]

A sudoku site in the UK admitted a year or so ago that their algorithm for constructing puzzles had a bug, leading to some that required “guessing” - actually branching. I don’t know if anyone ever proved this, though.

By unsolvable is really unsolvable or unsolvable under a set of rules? The latter is clearly true, the former isn’t (assuming a legal configuration) since it would be fairly easy to resort to a recursive backtracking algorithm whenever no squares can be filled in by a given set of rules. Since the puzzle is finite the heuristic will terminate, and since there are a lot of constrained squares after a choice I suspect it would be reasonably efficient, given a decent set of rules.

22

[QUOTE=ftg]
I have no idea why people think that trial-and-error is so special.
[/QUOTE]
Maybe I can help you. It’s not about anything being ‘special’. It’s about two distinct situations.

You are trying to solve a Sudoku puzzle.

Scenario A. Given the information you have, you can deduce at least one more correct number placement. This increases the amount of information you have and you can proceed to the next stage of solving the puzzle. You do not have make a guess or a hypothetical entry and explore the consequences.

Scenario B. Given the information you have, you cannot deduce one more correct number placement. What you can do is insert one number as a hypothetical solution, examine the consequences, and see if it leads to an illegal result.

Many Sudoku fans feel differently about these two situations. Some prefer it if the solution only involves Scenario A. This doesn’t mean the puzzle is necessarily easy. The valid deduction process from one step to the next may be easy to discover or very challenging.

It is fair and accurate to say that in Scenario B, the ‘hypothesise and explore’ process is a kind of deduction, but, to repeat myself, many enthusaists feel it constitutes a different kind of challenge - one that some like and others don’t.

In Scenario B, there are cases where the ‘exploration’ does not need to proceed very far before a flaw is discovered, so the solver can eliminate the guess very quickly. In other cases, the flaw may be such that it can only be discovered after a very long deductive process involving multiple hypotheses chained together, to a degree that many fans just don’t think is worth the time and effort.

That’s why some enthusiasts feel differently about the two scenarios.

23

[QUOTE=ftg]
This keeps coming up and I don’t know why. Of course it’s always possible to solve a correctly designed Suduko without guessing.
[/QUOTE]

But the question is, are there INCORRECTLY designed suduko which

  1. have a unique correct solution
  2. are unsolvable without guessing?
24

But as ianzin said, ones which require guessing are NOT necessarily incorrect. That’s a matter of taste, not of rule.

Further, as ftg said in more technical language, “guessing” is really just a way of saying “the next deduction I need to make is bigger than my feeble short term memory can hold, so I must resort to writing it down in pencil”.

25

They are incorrect- solving a suduko should be a matter of logic, not luck.

26

I debate posting this because I do not want to start a bicker.

What some folks call “guessing” has nothing to do with “luck”.

There is no logical difference between looking at a cell and saying “I can’t put a 3 there because there’s already a 3 in the same column” versus “I can’t put a 3 there because if I do then after 5 more moves I’ll be screwed.”

Both are equally logical & equally fact-based. Where they differ is in whether you or I can do them in our head.

As ianzin said, it’s OK for you to decide you prefer one or the other, or to declare you think puzzles like his B are outside of your definition of “puzzles I’m willing to play”.

Just don’t go making the deep philosophical / logical error of believing there is a real difference, or a bright line difference, between the two. There isn’t. That’s a well-settled fact of information science. It’s not an obvious fact to the casual layman, but it is a fact.

27

Yes there is a difference, because a Suduko is a puzzle that should be solveable through logic without maths. Its not supposed to some sort of peroblem that an engineer needs to work out to build a bridge, or anything like that.

Lets put it another way I’m not a mathmatician so I hope I’m getting this right. If you can solve a suduko without guessing then the algorithm completes in polynomial time. But if you start making guesses, that is try every possibility in turn until you eventually hit on the right one, then it becomes non-polynomial. And while it is “solvable” in a sense, trying every possible guess could take several thousand years.

So, instead of “solvable” in the question, imagine it said “solveable in polynomial time” if that would make you happier.

28

[QUOTE=totoismomo]
Can you tell me more about this boolean encoding method of solving? I can’t seem reference to it here , here, or here.
[/QUOTE]

Holy moly. Somebody completely blotted out the NP-Completeness section of the Wikipedia page. (And the edit page is so full of cruft I can’t find a suitable older version.) They even took out useful links. Sheesh. Wiki-jerks.

The idea is to start with a bunch of variables like X[i,j,k] that would be true if the square at (i,j) contains the number k. You build up a Boolean formula of a lot of clauses such as X[0,0,9] OR NOT X[0,1,9]. That is, if the cell at (0,0) contains a 9 then the cell at (0,1) cannot contain a 9. There are a lot of such clauses requiring that each cell contains a number, and no dups in blocks, rows and columns.

You then substitute your “knowns”. If there is a 4 at (3,7), you replace X[3,7,4] with 1 (or TRUE), etc.

You now have a big Boolean formula in CNF. You use the usual Boolean algebra rules to multiply thru to get a formula in DNF. You have a single term whole remaining variables tell you what the solution is. E.g., if it contains X[2,5,3] then there is a 3 at (2,5). (It will also contain negative literals, but those just reinforce the solution.)

Note that if the puzzle is badly constructed, then you can end up with a 0 (FALSE) term which means the puzzle has no solution or 2+ terms which means the puzzle has multiple solutions.

I again want to repeat that no guessing is ever required. For humans, as has been mentioned, it’s just a question of how far you can look ahead. Some are better than others. It would be idiotic to say that looking 2 levels ahead is not guessing but 3 levels ahead is guessing.

So, everybody who asked more about my post about various situations. Same answer. No guessing is ever required. Never. Period.

29

Perhaps you don’t like the word “guessing.” Instead of that, lets say “exhaustive testing” where you try each possible arangement in turn :

Let’s try putting put a one in that spot. On the next step ahead, lets try poutting a a seven in that spot … finishing with a three, five and one in the last three spotsl. Doesn’t work. Okay, lets make it three one and five in the last spots. Doesn’t work, lets make it one, three and five, doesn’t work, lets make it one, five and three. I’ll find the solution eventually, see you in seven and a half million years.

Are there possible arrangements of suduko that can be solved ONLY through such exhaustive testing?

30

[QUOTE=Peter Morris]
Perhaps you don’t like the word “guessing.” Instead of that, lets say “exhaustive testing” where you try each possible arangement in turn :

Let’s try putting put a one in that spot. On the next step ahead, lets try poutting a a seven in that spot … finishing with a three, five and one in the last three spotsl. Doesn’t work. Okay, lets make it three one and five in the last spots. Doesn’t work, lets make it one, three and five, doesn’t work, lets make it one, five and three. I’ll find the solution eventually, see you in seven and a half million years.

Are there possible arrangements of suduko that can be solved ONLY through such exhaustive testing?
[/QUOTE]

No one knows. If there were, it would imply a supra-polynomial lower bound on the worst-case running time of a Sudoku solver, which implies that P != NP.

31

[QUOTE=LSLGuy]
I debate posting this because I do not want to start a bicker.

What some folks call “guessing” has nothing to do with “luck”.

There is no logical difference between looking at a cell and saying “I can’t put a 3 there because there’s already a 3 in the same column” versus “I can’t put a 3 there because if I do then after 5 more moves I’ll be screwed.”

Both are equally logical & equally fact-based. Where they differ is in whether you or I can do them in our head.

As ianzin said, it’s OK for you to decide you prefer one or the other, or to declare you think puzzles like his B are outside of your definition of “puzzles I’m willing to play”.

Just don’t go making the deep philosophical / logical error of believing there is a real difference, or a bright line difference, between the two. There isn’t. That’s a well-settled fact of information science. It’s not an obvious fact to the casual layman, but it is a fact.
[/QUOTE]

But what you are talking about isn’t guessing it is on a par with playing chess. When I was taught to play decent chess I was taught to look at the board and look for a series of possibilities - checks, captures, forks , pins, nets and ties. And then start looking one more move ahead in the same way.

In Sudoku I expect to be able to find at least one more number without “guessing” even if it requires doing the equivalent in memory of having all the possible numbers of all the unassigned squares written in the squares. Guessing would be a case where having all those values pencilled in no logic would give you a 100% definite number.

32

Couple of years back I saw somewhere (sorry-can’t remember where) that some numbercrunchers had determined that a puzzle has to have at least seventeen “clues” in order to have only one possible solution. Not that I’ve ever seen a puzzle with that few given numbers - the logic rules needed to solve something like that must be brainbusters.

Dell (the puzzle people, not the computer people) regularly publishes a book called “Sudoku Challenge” that always includes a four-page section of “Solving Tips”, most of which are much too complicated for this old moronic moose to remember.
Through cheating I’ve discovered that just one given number can make the difference between a very difficult puzzle and an easy one.

33

What some refer to as “guessing” in this thread I would consider as just more complicated deduction. I have solved hundreds of Sudokus and have to admit that I’ve only encountered one such puzzle. Of course I don’t know if I just missed something during the solution which forced the branching approach. However, I cleared said puzzle and tried numerous times to re-solve it without branching but failed each time. To be honest, although I didn’t like the puzzle because it was so hard, I enjoyed trying to find a more direct solution. I do consider it a legitimate solvable puzzle.

34

[QUOTE=Peter Morris]
Perhaps you don’t like the word “guessing.” Instead of that, lets say “exhaustive testing” where you try each possible arangement in turn :

Let’s try putting put a one in that spot. On the next step ahead, lets try poutting a a seven in that spot … finishing with a three, five and one in the last three spotsl. Doesn’t work. Okay, lets make it three one and five in the last spots. Doesn’t work, lets make it one, three and five, doesn’t work, lets make it one, five and three. I’ll find the solution eventually, see you in seven and a half million years.

Are there possible arrangements of suduko that can be solved ONLY through such exhaustive testing?
[/QUOTE]

You’re just trying to avoid the obvious. There is no problem, repeat, no problem that can be solved by guessing (who cares about the word, I’m only talking about methods) that cannot also be solved without guessing. Efficiency of solution doesn’t matter when one considers the worst case scenario for guessing as the last guess is of course the one that works. This is an extremely well known and quite simple theorem in Computer Science. (The general result for Turing Machines is due to Pat Fisher. The reduction to a Boolean formula for all NP problems is due to Steve Cook.)

Note that my 2nd post contains a simple algorithm to solve all Suduko’s without guessing. (And if you use Quine-McCluskey type methods, it can be faster. Faster still if you apply other advanced methods. But NP-Complete lurks around the corner of course.)

It’s like asking: Can you only factor integers by guessing? Of course not. Sieve of Eratosthenes is an (inefficient) counter example.

35

In the intros I’ve read, I’ve gotten the sense that “guessing” stands for making a wild stab at putting a number in a square, not the branching algorithm mentioned here. Is the desire to have puzzles that can be solved with no lookahead, or only a limited number of lookahead steps?

Peter Morris, only a very brain dead solver would need to be anywhere close to exhaustive. Most squares are limited 2- 3 choices at most. I’ll admit that I am not longer clever enough to do all really hard ones without “guessing,” but I can always find a square with only two choices, in fact several. I’ve gotten good at picking the right square to guess - you can see the number of forced assignments after a guess. The more forced assignments mean that you reach a contradiction faster if you guess wrong. So this strategy is exhaustive but only in a trivial sense that you exhaust one of two choices most of the time. I suppose if you really want to wait a long time, you can do a totally stupid algorithm that picks all legal possibilities with no rules at all.