Help with BUG

Advanced methods and approaches for solving Sudoku puzzles

Postby EnderGT » Thu Feb 21, 2008 11:07 pm

eleven wrote:Would you solve this with an xy-chain ? http://forum.enjoysudoku.com/viewtopic.php?p=52686#p52686


So, there's a contest to find the hardest puzzle that fits the specified pattern? How would one interpret the "ED=9.0/9.0/2.6" part of the submission?

Specific to the puzzle you linked (the one submitted by TTHsieh, right?): I pretty easily reduced that to what looked like a BUG+3 situation. Everything seemed to match the description of a BUG, so I proceeded with the assumption that one of R6C3, R4C8, or R4C9 had to be a 1. Of course, making R4C8 or R4C9 a one forced R6C3 to be a one, and that solved the puzzle no chains required. This is the state I reduced it to:

Code: Select all
 *--------------------------------------------------*
 | 1    9    7    | 5    2    8    | 6    4    3    |
 | 8    4    3    | 7    6    1    | 9    2    5    |
 | 9    2    5    | 8    3    6    | 1    7    4    |
 |----------------+----------------+----------------|
 | 39   13   14   | 6    5    7    | 2    189  148  |
 | 5    2    8    | 1    9    4    | 7    3    6    |
 | 69   7    146  | 2    8    3    | 5    19   14   |
 |----------------+----------------+----------------|
 | 36   35   9    | 4    1    26   | 8    57   27   |
 | 4    8    12   | 9    7    5    | 3    6    12   |
 | 7    15   26   | 8    3    26   | 4    15   9    |
 *--------------------------------------------------*


Is there some other way of solving this that I missed?
EnderGT
 
Posts: 69
Joined: 19 February 2008

re: assuming Uniqueness-Of-Answer

Postby Pat » Fri Feb 22, 2008 9:03 am

EnderGT wrote:
eleven wrote:
EnderGT wrote:
ab wrote:if I use uniqueness tests as part of my solving arsenal I may never find out that a puzzle has more than one solution


it seems to me that applying an assumption of uniqueness to a puzzle that isn't, in fact, unique, would actually end up resulting in a no-solution state.

If this happens, then you have identified a puzzle that has more than one solution!


Or you would not even notice it,
because you find one of say 3 or 5 solutions.


I suppose this is true, but yet... if the application of one single assumption of uniqueness leads me to a single solution, then I'd argue that that is the only valid solution.


no, EnderGT, sorry, it would not be the only answer

if the puzzle has 3 answers, it has 3 answers
    and if you find only one of them, you remain unaware of the existence of the other 2 answers

eleven is right
User avatar
Pat
 
Posts: 3440
Joined: 18 July 2005

re: the patterns game

Postby Pat » Fri Feb 22, 2008 9:12 am

EnderGT wrote:
eleven wrote:Would you solve this with an xy-chain ?

http://forum.enjoysudoku.com/viewtopic.php?p=52686#p52686



So, there's a contest to find the hardest puzzle that fits the specified pattern?
How would one interpret the ED=5.7/1.5/1.5 part of the submission?


not necessarily the hardest puzzle -- rather, the hardest puzzle within each level of difficulty --
the patterns game wrote: Ratings

ratings are based on Sudoku Explainer 1.2.1

Patterns Game ratings are the tuple ER/EP/ED:
  • ER (explainer rating): the higest Sudoku Explainer rating of the methods leading to the puzzle solution
  • EP (pearl rating): the higest Sudoku Explainer rating of the methods leading to the first cell placement
  • ED (diamond rating): the higest Sudoku Explainer rating of the methods leading to the first candidate elimination
A modified Sudoku Explainer 1.2.1 determines these ratings.

User avatar
Pat
 
Posts: 3440
Joined: 18 July 2005

Re: re: assuming Uniqueness-Of-Answer

Postby EnderGT » Fri Feb 22, 2008 4:25 pm

Pat wrote:
EnderGT wrote:
eleven wrote:
EnderGT wrote:
ab wrote:if I use uniqueness tests as part of my solving arsenal I may never find out that a puzzle has more than one solution


it seems to me that applying an assumption of uniqueness to a puzzle that isn't, in fact, unique, would actually end up resulting in a no-solution state.

If this happens, then you have identified a puzzle that has more than one solution!


Or you would not even notice it,
because you find one of say 3 or 5 solutions.


I suppose this is true, but yet... if the application of one single assumption of uniqueness leads me to a single solution, then I'd argue that that is the only valid solution.


no, EnderGT, sorry, it would not be the only answer


As I said - not the only answer, but the only valid answer.

If a puzzle would has 2 solutions, then applying a uniqueness test would result in no solution. If it has 3, then a uniqueness test would result in 1 solution. Multiple applications of uniqueness tests bring it down to this even-odd pattern.

Either way, this dispute is pointless as it has no bearing on whether or not any of is going to use uniqueness tests to solve puzzles, nor whether any of us will accept non-unique puzzles as valid. I will continue to use them, as I view non-unique puzzles as invalid.

Thanks for the info on the ratings.
EnderGT
 
Posts: 69
Joined: 19 February 2008

Re: re: assuming Uniqueness-Of-Answer

Postby daj95376 » Fri Feb 22, 2008 5:26 pm

EnderGT wrote:As I said - not the only answer, but the only valid answer.

If a puzzle would has 2 solutions, then applying a uniqueness test would result in no solution. If it has 3, then a uniqueness test would result in 1 solution. Multiple applications of uniqueness tests bring it down to this even-odd pattern.

Either way, this dispute is pointless as it has no bearing on whether or not any of is going to use uniqueness tests to solve puzzles, nor whether any of us will accept non-unique puzzles as valid. I will continue to use them, as I view non-unique puzzles as invalid.

Thanks for the info on the ratings.

If you're happy with your results based on your use of uniqueness tests, then enjoy yourself.

Please note: In this forum, if a puzzle has multiple solutions, then none of them are considered valid because reductions based on uniqueness tests are not accepted for puzzles with multiple solutions.
Last edited by daj95376 on Fri Feb 22, 2008 3:31 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: re: assuming Uniqueness-Of-Answer

Postby EnderGT » Fri Feb 22, 2008 6:02 pm

daj95376 wrote:Please note: In this forum, if a puzzle has multiple solutions, then none of them are considered valid


That part I can agree with completely

daj95376 wrote:because reductions based on uniqueness tests are not accepted.


This part I can't. If reductions based on uniqueness tests aren't accepted, why are they published as part of the "how to solve sudoku" suite of rules? I'm not referring to any specific publisher here - non-unique rectangles and BUG removal are mentioned in many online sources.

Re-hijacking my own thread, I came across a puzzle today where a forcing chain was the appropriate step required to solve the puzzle. The end result of this chain was a determination of the last cell's value, without determining any of the other values in the chain - i.e. no guessing. I'm not sure what type of chain this was (xy-, something else? are there others?), but I do know that it solved the puzzle.
EnderGT
 
Posts: 69
Joined: 19 February 2008

Re: re: assuming Uniqueness-Of-Answer

Postby daj95376 » Fri Feb 22, 2008 7:35 pm

EnderGT wrote:
daj95376 wrote:because reductions based on uniqueness tests are not accepted.

This part I can't.

I updated my previous message to actively reflect that I was still talking about puzzles with multiple solutions. I'm sorry about any misunderstanding on this point.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ab » Fri Feb 22, 2008 7:38 pm

I think xy chains are not forcing chains. If they are considered forcing chains, then there are certainly other kinds. I think forcing chains have a bit of a bad press and some of this is to do with the way they are presented. In Sudoku Explainer for instance you get things like if this candidate is a 6 then this candidate (same candidate) can't be a six. It leaves you thinking, well how did he choose that candidate to look at in the first place? However if you look at the lines and colours that usually accompany the explanation you will see that the forcing chain is actually pattern based, in a similar way to xy chains, it's just that it seems easier to explain it by taking the candidate that gets deleted as your starting point. it's a lazy explanation in other words. The forcing chains themselves are actaully pattern based, it's just a lot more difficult to explain them in those terms, and what's more a lot more difficult to program a computer to generate explanations in thise terms.

As for uniqueness tests, they assume uniquess, and find the solution on that basis. If the puzzle comes from a good source, it's a safe assumption and you will reach the unique solution to the puzzle. As Mike Barker said in many cases applying them is a lot easier than alternative solving strategies that might be required for some puzzles. I just don't like to make that assumption in the first place, even though it's often a safe one to make. If you apply these tests on a pseudo puzzle (with multiple solutions) you may reach a solution to the puzzle but be unaware that there are others. To my mind you will not have solved the puzzle, because a real solution will be to show that it has more than one solution.

If you think of sudoku as a mathematical problem, you can ask what are the axioms. For sudoku they are that the digits 1-9 appear once in each row, column and 3x3 box. Some people like to add that there is a unique solution as one of their axioms, others do not.
ab
 
Posts: 451
Joined: 06 September 2005

Postby hobiwan » Fri Feb 22, 2008 7:59 pm

EnderGT wrote:
eleven wrote:Would you solve this with an xy-chain ? http://forum.enjoysudoku.com/viewtopic.php?p=52686#p52686


So, there's a contest to find the hardest puzzle that fits the specified pattern? How would one interpret the "ED=9.0/9.0/2.6" part of the submission?

Specific to the puzzle you linked (the one submitted by TTHsieh, right?): I pretty easily reduced that to what looked like a BUG+3 situation. Everything seemed to match the description of a BUG, so I proceeded with the assumption that one of R6C3, R4C8, or R4C9 had to be a 1. Of course, making R4C8 or R4C9 a one forced R6C3 to be a one, and that solved the puzzle no chains required. This is the state I reduced it to:

Code: Select all
 *--------------------------------------------------*
 | 1    9    7    | 5    2    8    | 6    4    3    |
 | 8    4    3    | 7    6    1    | 9    2    5    |
 | 9    2    5    | 8    3    6    | 1    7    4    |
 |----------------+----------------+----------------|
 | 39   13   14   | 6    5    7    | 2    189  148  |
 | 5    2    8    | 1    9    4    | 7    3    6    |
 | 69   7    146  | 2    8    3    | 5    19   14   |
 |----------------+----------------+----------------|
 | 36   35   9    | 4    1    26   | 8    57   27   |
 | 4    8    12   | 9    7    5    | 3    6    12   |
 | 7    15   26   | 8    3    26   | 4    15   9    |
 *--------------------------------------------------*


Is there some other way of solving this that I missed?

EnderGT, your grid doesn't seem to be valid: In your grid r6c9 has to be 1, which leads to [r4c9]=8 and [r4c8]=9. This leaves [r6c8] without candidate.

With one Naked Pair (15 in [r9c28] => [r9c3]<>1) I arrive at:
Code: Select all
.---------------.---------------.---------------.
| 1    9    7   | 5    2    8   | 6    4    3   |
| 8    4    3   | 7    6    1   | 9    2    5   |
| 2    6    5   | 3    4    9   | 1    78   78  |
:---------------+---------------+---------------:
| 39   13   14  | 6    5    7   | 2    189  148 |
| 5    2    8   | 1    9    4   | 7    3    6   |
| 69   7    146 | 2    8    3   | 5    19   14  |
:---------------+---------------+---------------:
| 36   35   9   | 4    1    26  | 8    57   27  |
| 4    8    12  | 9    7    5   | 3    6    12  |
| 7    15   26  | 8    3    26  | 4    15   9   |
'---------------'---------------'---------------'

r46c3/r46c9 form a Uniqueness Test 6: Since none of the other cells in r4, r6, c3, c9, b4 and b6 contain a 4, 4 can be removed from the cells containing the extra candidates: [r4c9]<>4, [r6c3]<>4, which means [r6c9]=4, [r4c3]=4. This leaves a BUG+1.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby EnderGT » Fri Feb 22, 2008 8:03 pm

hobiwan wrote:EnderGT, your grid doesn't seem to be valid: In your grid r6c9 has to be 1, which leads to [r4c9]=8 and [r4c8]=9. This leaves [r6c8] without candidate.


You're absolutely right, I messed up when transcribing the grid. Let me revisit to see if I can provide the correct values.

Edit: I believe the grid you posted

Code: Select all
.---------------.---------------.---------------.
| 1    9    7   | 5    2    8   | 6    4    3   |
| 8    4    3   | 7    6    1   | 9    2    5   |
| 2    6    5   | 3    4    9   | 1    78   78  |
:---------------+---------------+---------------:
| 39   13   14  | 6    5    7   | 2    189  148 |
| 5    2    8   | 1    9    4   | 7    3    6   |
| 69   7    146 | 2    8    3   | 5    19   14  |
:---------------+---------------+---------------:
| 36   35   9   | 4    1    26  | 8    57   27  |
| 4    8    12  | 9    7    5   | 3    6    12  |
| 7    15   26  | 8    3    26  | 4    15   9   |
'---------------'---------------'---------------'


is the same as where I ended up. not sure how I missed row 3 so badly...

Edit 2: Looking at your answer... I knew there was something there, but I wasn't sure how to state it formally and thus be able to do the correct reductions. Fortunately for me, my approach worked, whether it was strictly correct or not...
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby EnderGT » Fri Feb 22, 2008 8:23 pm

ab wrote:I think xy chains are not forcing chains.

This may be true - I am sufficiently inexperienced as to not know the strict definition of a forcing chain. Here's the puzzle and what I did:

Code: Select all
*--------------------------------------------------*
 | 4    79   57   | 6   1589  138  | 137  2    58   |
 | 1    279  8    | 4    59   23   | 37   36   56   |
 | 3    6    25   | 7    158  128  | 14   9    458  |
 |----------------+----------------+----------------|
 | 9    1     4   | 3    6    5    | 2    8    7    |
 | 5    37   67   | 2    18   18   | 39   4    69   |
 | 8    23   26   | 9    7    4    | 5    36   1    |
 |----------------+----------------+----------------|
 | 7    4    9    | 1    3    6    | 8    5    2    |
 | 2    5    1    | 8    4    9    | 6    7    3    |
 | 6    8    3    | 5    2    7    | 49   1    49   |
 *--------------------------------------------------*


I noticed that no matter what value R5C2 had, R2C9 == 5. I'm not sure how to denote this, but here's the logic: if R5C2 is 7, then R1C2 is 9, then R2C5 is 9, then R2C9 is 5. if R5C2 is 3, then R5C7 is 9, then R5C9 is 6, then R2C9 is 5.

ab wrote:If you think of sudoku as a mathematical problem, you can ask what are the axioms. For sudoku they are that the digits 1-9 appear once in each row, column and 3x3 box. Some people like to add that there is a unique solution as one of their axioms, others do not.


I've always heard that, to be valid, sudoku puzzles must have a unique solution. I wasn't aware that there were people who considered puzzles with non-unique solutions to be acceptable.

A somewhat relevant anecdote: a friend gave me one of those hand-held electronic sudoku puzzles, and within 3 games I had encountered a multiple-solution puzzle. I haven't touched the thing since.
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby ronk » Fri Feb 22, 2008 8:35 pm

I believe eleven was hinting that EnderGT should find this BUG+2.
Code: Select all
.---------------.---------------.---------------.
| 1    9    7   | 5    2    8   | 6    4    3   |
| 8    4    3   | 7    6    1   | 9    2    5   |
| 2    6    5   | 3    4    9   | 1    78   78  |
:---------------+---------------+---------------:
| 39   3-1  4-1 | 6    5    7   | 2    89+1 48  |
| 5    2    8   | 1    9    4   | 7    3    6   |
| 69   7    46+1| 2    8    3   | 5    9-1  4-1 |
:---------------+---------------+---------------:
| 36   35   9   | 4    1    26  | 8    57   27  |
| 4    8    12  | 9    7    5   | 3    6    12  |
| 7    15   26  | 8    3    26  | 4    15   9   |
'---------------'---------------'---------------'

Because of the BUG+2, at least one of r4c8=1 and r6c3=1 must be true. Any 1s candidate that "sees" both r4c8 and r6c3 may be eliminated, i.e., r4c23<>1 and r6c89<>1. This step and singles solves the puzzle.

[edit: The coloring step by Simple Sudoku immediately prior to the above pencilmarks was for r4c9<>1. Without that step, the BUG+3 eliminates exactly the same candidates as the BUG+2 shown.]
Last edited by ronk on Fri Feb 22, 2008 5:47 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby EnderGT » Fri Feb 22, 2008 8:42 pm

ronk wrote:I believe eleven was hinting that EnderGT should find this BUG+2.
Code: Select all
.---------------.---------------.---------------.
| 1    9    7   | 5    2    8   | 6    4    3   |
| 8    4    3   | 7    6    1   | 9    2    5   |
| 2    6    5   | 3    4    9   | 1    78   78  |
:---------------+---------------+---------------:
| 39   3-1  4-1 | 6    5    7   | 2    89+1 48  |
| 5    2    8   | 1    9    4   | 7    3    6   |
| 69   7    46+1| 2    8    3   | 5    9-1  4-1 |
:---------------+---------------+---------------:
| 36   35   9   | 4    1    26  | 8    57   27  |
| 4    8    12  | 9    7    5   | 3    6    12  |
| 7    15   26  | 8    3    26  | 4    15   9   |
'---------------'---------------'---------------'

Because of the BUG+2, at least one of r4c8=1 and r6c3=1 must be true. Any 1s candidate that "sees" both r4c8 and r6c3 may be eliminated, i.e., r4c23<>1 and r6c89<>1. This step and singles solves the puzzle.


And THAT is the definitive answer as to how to solve the BUG+2 that I originally posted! Thank you so much. This answer also validates my approach on the BUG+3 found in the puzzle eleven linked.
EnderGT
 
Posts: 69
Joined: 19 February 2008

Postby ab » Sat Feb 23, 2008 1:05 am

EnderGT wrote:
ab wrote:If you think of sudoku as a mathematical problem, you can ask what are the axioms. For sudoku they are that the digits 1-9 appear once in each row, column and 3x3 box. Some people like to add that there is a unique solution as one of their axioms, others do not.


I've always heard that, to be valid, sudoku puzzles must have a unique solution. I wasn't aware that there were people who considered puzzles with non-unique solutions to be acceptable.

A somewhat relevant anecdote: a friend gave me one of those hand-held electronic sudoku puzzles, and within 3 games I had encountered a multiple-solution puzzle. I haven't touched the thing since.


You misunderstand me. I'm not suggesting that puzzles with multiple solutions are valid. I'm suggesting that some people approach their solution with the assumption that it's unique, whereas others choose not to make that assumption.
ab
 
Posts: 451
Joined: 06 September 2005

re: assuming Uniqueness-Of-Answer

Postby Pat » Sun Feb 24, 2008 9:54 am

EnderGT wrote:
As I said - not the only answer, but the only valid answer.



the puzzle has 3 answers; all of them are equally valid

i can find them all ; you find only one of them -- and you wish to claim it as the only valid answer, just because you chose a method which blinds you to the existence of the other answers

lovely! and if you cover your eyes, you can claim i don't exist
User avatar
Pat
 
Posts: 3440
Joined: 18 July 2005

PreviousNext

Return to Advanced solving techniques