Next step

Post the puzzle or solving technique that's causing you trouble and someone will help

Next step

Postby Neunmalneun » Wed Feb 22, 2006 11:26 am

I need the next step. Can anybody help? Thanks in advance.

Code: Select all
 *-----------*
 |6..|4..|...|
 |.4.|891|..5|
 |..9|.36|.4.|
 |---+---+---|
 |9..|..3|...|
 |..2|...|7..|
 |...|9..|..1|
 |---+---+---|
 |.7.|16.|5..|
 |5..|372|.6.|
 |...|..9|..7|
 *-----------*


 *-----------*
 |6.8|4..|9.3|
 |.43|891|6.5|
 |.59|.36|.48|
 |---+---+---|
 |9..|..3|4.6|
 |.32|6.4|7.9|
 |46.|98.|..1|
 |---+---+---|
 |374|168|592|
 |591|372|864|
 |..6|549|..7|
 *-----------*

 
 *--------------------------------------------------*
 | 6    12   8    | 4    25   57   | 9    127  3    |
 | 27   4    3    | 8    9    1    | 6    27   5    |
 | 127  5    9    | 27   3    6    | 12   4    8    |
 |----------------+----------------+----------------|
 | 9    18   57   | 27   125  3    | 4    58   6    |
 | 18   3    2    | 6    15   4    | 7    58   9    |
 | 4    6    57   | 9    8    57   | 23   23   1    |
 |----------------+----------------+----------------|
 | 3    7    4    | 1    6    8    | 5    9    2    |
 | 5    9    1    | 3    7    2    | 8    6    4    |
 | 28   28   6    | 5    4    9    | 13   13   7    |
 *--------------------------------------------------*
Neunmalneun
 
Posts: 52
Joined: 22 December 2005

Postby emm » Wed Feb 22, 2006 12:03 pm

Here's a chain that solves it

r5c1=8 => r4c2=1 => r1c2=2 => r2c1=7 => r2c8=2
r5c1=1 => r5c5=5 => r1c5=2 => r1c2=1 => r1c8=7 => r2c8=2
emm
 
Posts: 987
Joined: 02 July 2005

Postby Neunmalneun » Wed Feb 22, 2006 12:22 pm

Thanks a lot, em. I see the logic in your deduction and the 2 in R2C8 solves the rest in a couple of seconds.

But how did you know that you had to start in the cell R5C1 and to observe the impacts on cell R2C8 (of all cells)? Is there a pattern, a logic principle, intuition or just some random trials with a few bivalual cells?
Neunmalneun
 
Posts: 52
Joined: 22 December 2005

Postby emm » Wed Feb 22, 2006 12:30 pm

I had no reason to choose r5c1 except that it looked promising i.e. it was a lucky guess:D

I checked Sudoku Susser - it did something completely different!
r1c8=1 => r1c2=2 => r2c1=7 => r2c8=2 => r1c8=7
Since this is a contradiction r1c8 <> 1 => r1c2=1 => solution

PS : Actually now I can't see where that came from - here's another one.

A nice loop = r1c5-2-r1c2-1-r4c2-8-r5c1-1-r5c5-5-r1c5-2
Allowing elimination of 2 from r1c8 and 5 from r4c5

Followed by an XY wing r1c2, r1c8, r2c1 = 12, 17, 27
Allowing elimination of 7 from r2c8 (or alternatively 2 from r2c1)

All roads lead to Rome!
emm
 
Posts: 987
Joined: 02 July 2005

Re: Next step

Postby ronk » Wed Feb 22, 2006 2:49 pm

Neunmalneun wrote:I need the next step. Can anybody help?
Code: Select all
 *--------------------------------------------------*
 | 6    12   8    | 4    25   57   | 9    17+2 3    |
 | 27   4    3    | 8    9    1    | 6    27   5    |
 | 17+2 5    9    | 27   3    6    | 12   4    8    |
 |----------------+----------------+----------------|
 | 9    18   57   | 27   12+5 3    | 4    58   6    |
 | 18   3    2    | 6    15   4    | 7    58   9    |
 | 4    6    57   | 9    8    57   | 23   23   1    |
 |----------------+----------------+----------------|
 | 3    7    4    | 1    6    8    | 5    9    2    |
 | 5    9    1    | 3    7    2    | 8    6    4    |
 | 28   28   6    | 5    4    9    | 13   13   7    |
 *--------------------------------------------------*

If you're interested in advanced techniques, this grid presents a near perfect opportunity to apply The BUG (Bivalue Universal Grave) principle. Briefly, the BUG principle says [edit: at least one of r1c8=2, r3c1=2 and r4c5=5 must be true.] It is relatively easy to see:

If r1c8=2 then r1c2<>2, and
if r3c1=2 then r1c2<>2, and
if r4c5=5 then r1c5=2 and r1c2<>2.

In all three cases, r1c2<>2 which "solves" the puzzle. If you're interested, I'll be glad to explain further.

Ron
Last edited by ronk on Wed Feb 22, 2006 10:07 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Neunmalneun » Wed Feb 22, 2006 4:29 pm

Thank you very much, Ron. This is a very elegant solution. Actually I know the BUG principle and I tried to use it. But I was not bright enough to see the unambigious effects of the BUG candidates on the cell R1C2.

(When you know it it looks obvious, but that applies for the invention of the bicycle too).
Neunmalneun
 
Posts: 52
Joined: 22 December 2005

Re: Next step

Postby QBasicMac » Wed Feb 22, 2006 7:40 pm

ronk wrote:If you're interested in advanced techniques, this grid presents a near perfect opportunity to apply The BUG (Bivalue Universal Grave) principle


Question: Does the BUG technique depend on the assumption that the puzzle has a unique solution?

If so, I don't like it. I feel that you must use techniques that assume the puzzle might have multiple solutions or even no solution.

To make the uniqueness assumption is like a person using T&E who finds a value that works and stops, claiming the solution has been found. One must test every possible number to ensure the other values lead to invalid puzzles.

IMHO

If, on the other hand, it works for all puzzles, valid or not, let me know and I will add it to my list (x-wing, swordfish, etc.) of good things to look for.

Thanks,

Mac
QBasicMac
 
Posts: 441
Joined: 13 July 2005

Re: Next step

Postby ronk » Wed Feb 22, 2006 8:21 pm

QBasicMac wrote:Question: Does the BUG technique depend on the assumption that the puzzle has a unique solution?

Yes.

If so, I don't like it. I feel that you must use techniques that assume the puzzle might have multiple solutions or even no solution.

Since you profess to use bifurcation, rather than learn and apply advanced techniques, I think that's quite disingenuous. IOW when you guess, you don't know whether or not a puzzle has mutiple solutions either.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby bennys » Wed Feb 22, 2006 8:31 pm

(r2c1=7 or r3c1=7)=> (r2c8=2 or r3c4=2)=>r3c7<>2
bennys
 
Posts: 156
Joined: 28 September 2005

Postby tarek » Thu Feb 23, 2006 12:01 am

Another simple triple implication chains pops out after ALS-XZ

Code: Select all
*-----------------------------------------------*
| 6    12   8   | 4    25   57  | 9    127  3   |
| 27   4    3   | 8    9    1   | 6    27   5   |
| 127  5    9   | 27   3    6   | 12   4    8   |
|---------------+---------------+---------------|
| 9    18   57  | 27   125  3   | 4    58   6   |
| 18   3    2   | 6    15   4   | 7    58   9   |
| 4    6    57  | 9    8    57  | 23   23   1   |
|---------------+---------------+---------------|
| 3    7    4   | 1    6    8   | 5    9    2   |
| 5    9    1   | 3    7    2   | 8    6    4   |
| 28   28   6   | 5    4    9   | 13   13   7   |
*-----------------------------------------------*
Eliminating 5 from r4c5(ALS-XZ A=125 in r1c5, r1c2 B=158 in r4c8, r4c2  x=1 z=5)
*-----------------------------------------------*
| 6    12   8   | 4    25   57  | 9    127  3   |
| 27   4    3   | 8    9    1   | 6    27   5   |
| 127  5    9   | 27   3    6   | 12   4    8   |
|---------------+---------------+---------------|
| 9    18   57  | 27   12   3   | 4    58   6   |
| 18   3    2   | 6    15   4   | 7    58   9   |
| 4    6    57  | 9    8    57  | 23   23   1   |
|---------------+---------------+---------------|
| 3    7    4   | 1    6    8   | 5    9    2   |
| 5    9    1   | 3    7    2   | 8    6    4   |
| 28   28   6   | 5    4    9   | 13   13   7   |
*-----------------------------------------------*
Candidates in r1c8 will force r4c8 to have only 5 as valid Candidates
r1c8=1: r1c8=1 => r3c7=2 => r3c4=7 => r4c4=2 => r4c5=1 => r4c2=8 => r4c8=5
r1c8=2: r1c8=2 => r1c2=1 => r4c2=8 => r4c8=5
r1c8=7: r1c8=7 => r1c6=5 => r1c5=2 => r4c5=1 => r5c5=5 => r5c8=8 => r4c8=5
Threfore r4c8=5


Tarek
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby suzette » Thu Feb 23, 2006 2:12 am

em wrote:I had no reason to choose r5c1 except that it looked promising i.e. it was a lucky guess:D


Ha! I just asked the same question on another thread. I think I got the answer now.:) So, it is back to 'guessing', when you choose a cell to look for the chain, right?

But based on what do you think it 'looked promissing'?
suzette
 
Posts: 5
Joined: 20 February 2006

Re: Next step

Postby QBasicMac » Thu Feb 23, 2006 2:35 am

ronk wrote:when you guess, you don't know whether or not a puzzle has mutiple solutions either.


Hunhh? I certainly do. You must have missed something I thought I made plain in my post, Ron.

After getting stuck after applying what you call non-advanced techniques such as X-Wings and Swordfish and simple coloring, true, I use bifurcation (if that means T&E).

T&E: I pick a cell with values 5,6,9 for example. Make three copies of current status with 5 in one copy, 6 in another and 9 in the last.

I then proceed to use the non-advanced techniques again for each, if necessary, making even more puzzles.

The result: when I am finished, I have absolute proof that the puzzle had one and only one solution (if indeed that was the case).

Mac
QBasicMac
 
Posts: 441
Joined: 13 July 2005

Re: Next step

Postby ronk » Thu Feb 23, 2006 3:09 am

QBasicMac wrote:T&E: I pick a cell with values 5,6,9 for example. Make three copies of current status with 5 in one copy, 6 in another and 9 in the last.

I then proceed to use the non-advanced techniques again for each, if necessary, making even more puzzles.

The result: when I am finished, I have absolute proof that the puzzle had one and only one solution (if indeed that was the case).

That's only true if you try to achieve a solution with ALL the bifurcation copies. If there's only three possibilities and your first two possibilities fail to reach a solution but the last possibility does, then your claim is correct.

But if your first or second possibility reaches a solution, I simply don't believe you usually try the remaining possibilities just to discover whether or not that solution is unique.

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby tso » Thu Feb 23, 2006 5:01 am

suzette wrote:
em wrote:I had no reason to choose r5c1 except that it looked promising i.e. it was a lucky guess:D


Ha! I just asked the same question on another thread. I think I got the answer now.:) So, it is back to 'guessing', when you choose a cell to look for the chain, right?

But based on what do you think it 'looked promissing'?


NO! Though you CAN guess -- you do not have to. There are many other techniques that have been examined in these forums. Chains that are purely bivalue (xy-type chains) or single value bilocation (coloring type chains) are probably easier to find. One way to find an xy-type chain: connect all bivalue cells with an 'edge', label that edge with the digit the two cells share. Look for a closed loop in which the labels repeat exactly once -- for example 334534. That loop is a forcing chain that will eliminate the repeated digit from the cell it repeats from. No guessing required. Also, if you label all the edges and no loop is found (or no loop with a single repetition -- then you've proved that no simple xy-type chain exists -- also without guessing.

Also, though you would certainly agree that a hidden single doesn't require guessing to find -- how *do* you find one? I look first where it looks promising -- and so do you. I look in cells that have many filled cells in the same row, column and box, hoping that all but one digit will be accounted for. This only differs by degree from the search method one might use nailing down a forcing chain.

The underlying patterns -- naked pairs, forcing chains, BUGs -- are just that, patterns. They can ALL be found by searching, guessing, trial and error, a strict algorithm -- or looking in spot that seems most promising.
tso
 
Posts: 798
Joined: 22 June 2005

Re: Next step

Postby tso » Thu Feb 23, 2006 5:17 am

QBasicMac wrote:
ronk wrote:If you're interested in advanced techniques, this grid presents a near perfect opportunity to apply The BUG (Bivalue Universal Grave) principle


Question: Does the BUG technique depend on the assumption that the puzzle has a unique solution?

If so, I don't like it. I feel that you must use techniques that assume the puzzle might have multiple solutions or even no solution.


It isn't relevant that you "don't like it". Your "feelings" are not based in logic or mathematics. The fact that a default Sudoku has a unique solution is no more or less part of the game than that it has one of each digit in each row, column and box.

We do not *assume* that the puzzle has a unique solution. It is a *given* -- no more or less set in stone than the other *givens* within the grid -- that the puzzle has a unique solution.

Yes, you can create Sudokus that have muliple solutions -- and you can create one in which the digits 1-7 appear once while the digit 8 appears twice in each group, or in which the groups are irregularly shaped, or in which diagonals are used, etc. In these cases, many tactics would have to be modified or thrown out -- not just the ones that depend on uniqueness.

One assumes that the words are spelled correctly to solve a crossword -- and no one ever argues otherwise.
tso
 
Posts: 798
Joined: 22 June 2005

Next

Return to Help with puzzles and solving techniques