The New Sudoku Players' Forum

[swordfish7]

Hi, I am new to these message boards and fairly new to sudoku. I was doing one of these out of a newspaper the other day and after 2 or 3 hours i had it all filled out and then i realized that i had one number wrong, so the whole entire page was wrong. Being a computer science student, i realized that i had just spent 2 hours doing what my computer could do in a fraction of a second, and i havd screwed it up. so i decided to write a sudoku solving program (in JAVA).

My question is as follows:

-is every legitimate sudoku game, say from a newspaper or a puzzel book, entirely logically solvable? or do you reach a point on some games where you have to make a guess?

I haven't played enough games to know this for sure but i'm guessing that they can be completely solved by logic. However, any input on this would be very appreciated. If i have to write my program to guess numbers when it gets stuck it will be much more difficult to program and solving time will be much greater!

Cheers!

Swordfish

[Hud]

No guessing allowed. Some advanced techniques seem a bit like guesswork, but they are logical also.

[ab]

It's possible to create sudoku puzzles with one solution that require you to guess at some point. Look for instance at this thread:
http://forum.enjoysudoku.com/viewtopic.php?t=1914
However puzzles published in newspapers usually can be solved using logical deduction.

Look at the advanced techniques forum for discussions on techniques used for creating and solving puzzles. Also if you're a programmer have a go at creating a solver. It's fun. I've created one that uses hidden and naked singles, doubles and triples, as well as x wings, generalised x wings, and box line interactions. It solves a lot of puzzles, but not all of the Times fiendish puzzles.

To solve all of the Guardian' puzzles you just need hidden and naked singles and pairs and box line interactions. That will solve many other paper's puzzles too as well as the channel4 puzzles on teletext.

You can make a solver that solves all puzzles by just programming hidden and naked singles and then try filling in given cells. If there is only one legal candidate (ie all the others lead to a contradiction) then you can place it. It's not very elegant but it works.

[tso]

It's possible to create sudoku puzzles with one solution that require you to guess at some point. Look for instance at this thread:
http://forum.enjoysudoku.com/viewtopic.php?t=1914

No it is not. In fact, the thread you gave contradicts your point.

Time and time again a puzzle has been presented that "required guessing" only to fall to a new logical technique. A puzzle may require *you* to guess, maybe even *me*. This debate has been played out many times in this forum. Much if it is just semantics. There were those who have claimed (wrongly) that xy-wings, forcing chain and coloring are just fancy ways of guessing.

(The forum has a search facility at the top of the page, though more useful search can be conducted by using and advanced google search of the sudoku.com domain.)

[Moschopulus]

It's possible to create sudoku puzzles with one solution that require you to guess at some point. Look for instance at this thread:
http://forum.enjoysudoku.com/viewtopic.php?t=1914

No it is not.

Can you prove this?

[ravel]

If i have to write my program to guess numbers when it gets stuck it will be much more difficult to program and solving time will be much greater!

I dont think so. The easiest program only handles singles (and guesses) and will be faster than most multi-technique programs, because searching for patterns normally needs longer than it is saving time for the solution.

[ravel]

Can you prove this?

If you accept a proof by contradiction, it is easy: Using singles you have nothing to do but a lot of case distinctions to prove that each wrong candidate can be eliminated.

IMHO a proof without contradiction also is possible about this way: Take the elimination path (network) you would get with the above method for one candidate n in a cell C. The contradiction at the end will be either be "no candidate for a cell" or "no cell for a candidate in a unit". Then you can start with all candidates in the cell or with the candidate in all cells of the unit and go back all the steps and case distinctions. E.g. if the step was: Fixing candidate k in cell D only leaves candidate l in E you now have, [edit: of course the opposite:] if l is NOT in E, k is NOT in D.
Then for all starting points you will end up in the conclusion, that n cannot be in C.

PS:

In symbols:
If a proof by contradiction gives
n in C => not (x in D) for all digits x
then there is also a proof
x in D => not (n in C) for all x
or
n in C => not (m in unit U)
then there is a proof
m in (any cell of) U => not (n in C)

Thus for each sudoku a solution can be given with only logical steps. Finding a solution manually (besides of very simple sudokus) always needs a portion of try & error (or a lot of luck), eg something like "trying to find x-wings or coloring chains", where you do not know in advance, if there is one.

[Richard]

Looking ahead one move (e.g. if I put a 2 in this cell, will that contradict with the values already in other cells?) is normal when solving a sudoku. It's the activity we go through when deciding what values are possible in any cell. It's so normal we don't think of it as looking ahead but it is.

Looking ahead more than one move is less common, but is still completely logical. Thus what seems like a guess can be done in a fully logical manner - e.g. faced with a cell that must contain either a 7 or a 9, I can ask the question: If I put a 7 in this cell, can I still solve the puzzle? I may have to look ahead a number of moves to answer the question, (I may even solve the puzzle before I'm sure) but providing I allow myself the possibility to track back, undo everything I've done and put a 9 in the cell instead, I'm using logic. If I have to track back and put a 9 in the cell instead of the 7, I have proven that placing a 7 there is inconsistent and so the value must be a 9. If I don't have to track back, I've proven that putting a 7 there is consistent.

So, yes, any puzzle can be solved by logic, because trial and error with undo is logic.

Richard
Strictly Sudoku

[tso]

Can the directions to the restaurant from the hotel be so long and convoluted that the desk clerk will be able to truthfully say "You can't get there from here"?

Can you prove this cannot be the case?

[tarek]

Implication chains can solve ANY puzzle ..........
without the help of Uniqueness patterns, Colouring, NICE loops or even T&E

The colmplexity however can be so severe at times, making it a LOGICAL excuse to take a guess

Tarek

[ravel]

Can the directions to the restaurant from the hotel be so long and convoluted that the desk clerk will be able to truthfully say "You can't get there from here"?

Can you prove this cannot be the case?

Well, suppose the hotel and the restaurant are in different space ships flying with speed of light in different directions. You wont come from one to the other then

[tso]

Can the directions to the restaurant from the hotel be so long and convoluted that the desk clerk will be able to truthfully say "You can't get there from here"?

Can you prove this cannot be the case?

Well, suppose the hotel and the restaurant are in different space ships flying with speed of light in different directions. You wont come from one to the other then

Uh, yeah, you've got me there -- but this is analogous to a Sudoku with NO solution, not one that is merely difficult.

The point is, either there is a path or there isn't. There is no inbetween. Either the puzzle is solvable (has a unique solution) or it isn't.

[Chessmaster]

Michael Mepham used to make puzzles that required guess work but he doesnt any more. as a rule it should only need logic

[tso]

Michael Mepham used to make puzzles that required guess work but he doesnt any more. as a rule it should only need logic

No he didn't.

He made puzzles that he *claimed* to require guess work or that he *thought* required guess work, most of which wouldn't even make it onto a list of hard puzzles in this forum. They generally could be solved with an xy-wing or two, maybe coloring or a short xy-type forcing chain. Some where harder -- none were anywhere near the level of the hardest posted in this forum.

This makes an important point -- even if it *were* possible to create a puzzle with a unique solution absolutely required guessing (read: magic) to solve (and it isn't) -- you would *never* know that the puzzle in front of you is one of them! Many solvers trusted Mempham's claim that these puzzles required trial and error -- and others (read: me) ignored his silly warnings and went ahead and solved the puzzles in a straightforward, logical fashion.

Read Mempham's article on the subject. Though he contradicts himself several times, one point is clear -- though some puzzles he created required *him* to guess, other people solved the same puzzles without guessing. Puzzles that were very hard when he created them aren't so tough after many new tactics were discovered. And new tactics are *still* being discovered.

It took many years, but the four color theorem was finally proved. We all *knew* it could not be cracked.

[WarrenGaebel]

Hi, swordfish7.

Would it be possible to get a copy of your Java program? In return I offer my JavaScript code. It is available at http://warren.gaebel.ca/misc/SudokuSolver.html

My program is pretty basic and it hasn't undergone any real testing, but it seems to solve all puzzles where there is only one solution. If there's more than one solution, it will also let you know what digits are acceptable in each empty cell. Just click on the cell for this information.

...Warren