Just a question...

Advanced methods and approaches for solving Sudoku puzzles

Just a question...

Postby noah » Mon Jan 09, 2006 11:32 pm

I am just trying to settle an argument a friend and I are having. Will a sudoku puzzle ALWAYS without fail have a logical deduction that can be made next? Or is it possible to come upon instances where you HAVE to guess? I can almost always find the next deduction(s) to be made, and I figure if you don't see the next move, that doesn't mean it isn't there. Even if you have to analyze 3 or even 4 moves ahead. My friend insists that sooner or later a leap of faith must be made. Which is it?:?:
noah
 
Posts: 4
Joined: 09 January 2006

none

Postby Chessmaster » Mon Jan 09, 2006 11:34 pm

it is all logic it can always be used you never need to guess. even on the hardest puzzles just think ahead and you can solve it. tell your friend that you never need to take a leap of faith.
Chessmaster
 
Posts: 191
Joined: 21 December 2005

Postby noah » Mon Jan 09, 2006 11:37 pm

please, as many people reply as possible, or my friend will just think one person is a 'crackpot' or something.:D
noah
 
Posts: 4
Joined: 09 January 2006

Postby tarek » Tue Jan 10, 2006 12:09 am

Today we have too many advanced deduction techniques that reduced the need for guessing (A year ago there were too many puzzles out there that required guessing, the same puzzles today don't need that), many logical deductions are made however at the machine level which humans can't grasp easily.
Last edited by tarek on Mon Jan 09, 2006 8:11 pm, edited 1 time in total.
User avatar
tarek
 
Posts: 2697
Joined: 05 January 2006

Re: Just a question...

Postby tso » Tue Jan 10, 2006 12:11 am

noah wrote:I am just trying to settle an argument a friend and I are having. Will a sudoku puzzle ALWAYS without fail have a logical deduction that can be made next? Or is it possible to come upon instances where you HAVE to guess? I can almost always find the next deduction(s) to be made, and I figure if you don't see the next move, that doesn't mean it isn't there. Even if you have to analyze 3 or even 4 moves ahead. My friend insists that sooner or later a leap of faith must be made. Which is it?:?:


Is there a weight so heavy that it cannot be lifted?

Is there a weight so heavy that *I* cannot lift it?

Are there two addresses so remote from each other than you cannot get from one to the other without Scotty's help?

Can you tangle up a wire so badly that electicity cannot find its way from one end to the other?

Is there a minimum number of unsolved cells that are needed to require a magical solution?

Has anyone ever asked this question in respect to any other puzzle ever to exist? A chess problem? A Crossword?


The roots of this question lay in the inexplicable claim some publishers have used -- "our puzzles can be solved by logic, no guessing required" -- implying that some that some other puzzles DO require guessing. What they *mean* is, "our puzzles aren't too hard".
tso
 
Posts: 798
Joined: 22 June 2005

Postby tso » Tue Jan 10, 2006 12:46 am

tarek wrote:Today we have too many advanced deduction techniques that reduced the need for guessing (A year ago there were too many puzzles out there that required guessing, the same puzzles today don't need that), many logical deductions are made however at the machine level which humans can't grasp easily.


Exactly.

Code: Select all
 1 9 3 | 8 5 2 | 7 4 6
 8 5 4 | 7 6 3 | 9 1 2
 6 7 2 | 4 1 9 | 8 5 3
-------+-------+------
 9 3 8 | 1 4 7 | 6 2 5
 2 4 6 | . . . | 3 7 1
 5 1 7 | 2 3 6 | 4 8 9
-------+-------+------
 7 8 . | 6 . . | . 3 4
 4 6 5 | 3 . . | . 9 7
 3 2 . | . 7 4 | . 6 8



Code: Select all
 *--------------------------------------------------*
 | 1    9    3    | 8    5    2    | 7    4    6    |
 | 8    5    4    | 7    6    3    | 9    1    2    |
 | 6    7    2    | 4    1    9    | 8    5    3    |
 |----------------+----------------+----------------|
 | 9    3    8    | 1    4    7    | 6    2    5    |
 | 2    4    6    | 59   89   58   | 3    7    1    |
 | 5    1    7    | 2    3    6    | 4    8    9    |
 |----------------+----------------+----------------|
 | 7    8    19   | 6    29   15   | 125  3    4    |
 | 4    6    5    | 3    28   18   | 12   9    7    |
 | 3    2    19   | 59   7    4    | 15   6    8    |
 *--------------------------------------------------*


When this puzzle was first posed on another Sudoku forum, under the title "Dead easy -- but beyond "logic" (it's the second puzzle in the thread) it was believed that it was "... obviously dead easy, yet ... can't be cracked without recourse to bifurcation." (Bifurcation is essentially placing each of the two remaining possible values in once cell into a copy of the puzzle and solving both puzzles from there. One will lead to a contradiction. The other is correct.)

We then learned to solve it by forcing chains or xy-wings:

r9c4=5 => r7c6=1 => r7c3=9 => r7c5=2
r9c4=9 => r7c5=2
therefore, r7c5=2

Then we learned BUG -- now the solution is trivial:

Row 7 column 7 is the only cell that has three candidates. On inspection, the candidate 1 appears three times in this cell's row, column and box. Therefore, r7c7=1.
tso
 
Posts: 798
Joined: 22 June 2005

Postby nj3h » Tue Jan 10, 2006 2:37 am

TSO, can you please provide additional explanation on the r7c7=1 from your post. I must be asleep or somthing here.

Thanks
nj3h
 
Posts: 47
Joined: 07 July 2005

Postby tso » Tue Jan 10, 2006 3:20 am

nj3h wrote:TSO, can you please provide additional explanation on the r7c7=1 from your post. I must be asleep or somthing here.

Thanks


Read The BUG (Bivalue Universal Grave) principle thread.

If you just want to apply it in the simplest cases without bothering to figure out why it works, just read here.
tso
 
Posts: 798
Joined: 22 June 2005


Return to Advanced solving techniques

cron