Stuck again - or I was

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

Stuck again - or I was

Postby wychwood » Thu Jan 24, 2008 8:36 pm

Hi folks, me back again.

Here's an interesting little puzzle.

Starts here:
Code: Select all
*-----------*
 |.4.|...|...|
 |9..|3..|.6.|
 |...|2.1|5..|
 |---+---+---|
 |7..|...|..8|
 |.3.|.6.|.9.|
 |2..|...|..4|
 |---+---+---|
 |..6|5.7|...|
 |.1.|..8|..2|
 |...|...|.3.|
 *-----------*


I get to this point fairly easily, but then get stuck (and so does Simple Soduku):
Code: Select all
 
 *-----------------------------------------------------------------------------*
 | 1358    4       123578  | 89      5789    6       | 1289    28      1379    |
 | 9       2578    12578   | 3       4578    45      | 1248    6       17      |
 | 6       78      378     | 2       4789    1       | 5       48      379     |
 |-------------------------+-------------------------+-------------------------|
 | 7       569     1459    | 149     12459   23459   | 36      12      8       |
 | 148     3       148     | 7       6       24      | 12      9       5       |
 | 2       569     159     | 189     1589    359     | 36      7       4       |
 |-------------------------+-------------------------+-------------------------|
 | 348     289     6       | 5       12349   7       | 1489    148     19      |
 | 34      1       3479    | 6       349     8       | 479     5       2       |
 | 458     25789   245789  | 149     1249    249     | 14789   3       6       |
 *-----------------------------------------------------------------------------*


I then put it into Sudocue and that got through to a solution. Trouble is I cannot remember exactly how, although I remember that there were definitely some ALSs (which I had given up trying to spot) and a couple of XY wings (which I did spot). At some point, it got to this position:

Code: Select all
*--------------------------------------------------------------------*
 | 135    4      12357  | 8      79     6      | 19     2      1379   |
 | 9      278    1278   | 3      47     5      | 148    6      17     |
 | 6      78     378    | 2      479    1      | 5      48     379    |
 |----------------------+----------------------+----------------------|
 | 7      56     4      | 9      25     23     | 36     1      8      |
 | 18     3      18     | 7      6      4      | 2      9      5      |
 | 2      569    59     | 1      58     3      | 36     7      4      |
 |----------------------+----------------------+----------------------|
 | 348    289    6      | 5      1239   7      | 1489   48     19     |
 | 34     1      379    | 6      39     8      | 479    5      2      |
 | 58     25789  25789  | 4      129    29     | 1789   3      6      |
 *--------------------------------------------------------------------*


At some point after that (or it may even be here), Sudocue came up with a "BUG 1". Now I had never even heard of that, although I have since looked it up via this board.

Trouble is, I just cannot understand what that explanation is all about, mainly I suspect because I just do not understand most of the shorthand that is used by you guys on these forums.

So can someone explain BUG to me in simple terms, in plain English?
Oh, and then can someone explain how on earth the above puzzle is solved?

Many thanks
Wychwood :( :?: :(
Code: Select all
Code: Select all
wychwood
 
Posts: 28
Joined: 08 February 2007

Re: Stuck again - or I was

Postby daj95376 » Thu Jan 24, 2008 11:37 pm

wychwood wrote:I get to this point fairly easily, but then get stuck (and so does Simple Soduku):
Code: Select all
 
 *-----------------------------------------------------------------------------*
 | 1358    4       123578  | 89      5789    6       | 1289    28      1379    |
 | 9       2578    12578   | 3       4578    45      | 1248    6       17      |
 | 6       78      378     | 2       4789    1       | 5       48      379     |
 |-------------------------+-------------------------+-------------------------|
 | 7       569     1459    | 149     12459   23459   | 36      12      8       |
 | 148     3       148     | 7       6       24      | 12      9       5       |
 | 2       569     159     | 189     1589    359     | 36      7       4       |
 |-------------------------+-------------------------+-------------------------|
 | 348     289     6       | 5       12349   7       | 1489    148     19      |
 | 34      1       3479    | 6       349     8       | 479     5       2       |
 | 458     25789   245789  | 149     1249    249     | 14789   3       6       |
 *-----------------------------------------------------------------------------*


I don't know ALS, but my solver pointed out a simple contradiction forcing net that might also be the ALS elimination.

Code: Select all
[r1c8]=8 => [r1c4]=9,[r3c8]=4 => [r125c7]=12 contradiction => [r1c8]<>8

After this, my solver found: a Naked Quad, two XY-Wings, and an XY-Chain -- besides Singles. No BUG+1.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby hobiwan » Fri Jan 25, 2008 10:29 am

Code: Select all
.---------------.---------------.---------------.
| 15   4    135 | 8    7    6   | 19   2    39  |
| 9    27   12  | 3    4    5   | 8    6    17  |
| 6    78   38  | 2    9    1   | 5    4    37  |
:---------------+---------------+---------------:
| 7    6    4   | 9    5    2   | 3    1    8   |
| 18   3    18  | 7    6    4   | 2    9    5   |
| 2    59   59  | 1    8    3   | 6    7    4   |
:---------------+---------------+---------------:
| 3    29   6   | 5    12   7   | 4    8    19  |
| 4    1    79  | 6    3    8   | 79   5    2   |
| 58   58   27  | 4    12   9   | 17   3    6   |
'---------------'---------------'---------------'


That's the BUG wychwood was talking about. You should read the explanation in http://www.sudopedia.org/wiki/Bivalue_Universal_Grave, which is very clear.

For this example:

Suppose, candidate 1 in r1c3 was not present, then you would have a puzzle with exactly two candidates in every unsolved cell. In every possible constraint (row, col block) every candidat would appear exactly twice. This, according to sudopedia, leaves two possibilities:

    If putting 3 in r1c3 gives a valid solution, then putting 5 in r1c3 would give a valid solution too, which makes the puzzle invalid
    If putting 3 in r1c3 gives no solution, then putting 5 in r1c3 gives no solution too, puzzle invalid
This means that 3 and 5 can be eliminated from r1c3, which solves the puzzle.
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby daj95376 » Fri Jan 25, 2008 6:26 pm

hobiwan wrote:
Code: Select all
.---------------.---------------.---------------.
| 15   4    135 | 8    7    6   | 19   2    39  |
| 9    27   12  | 3    4    5   | 8    6    17  |
| 6    78   38  | 2    9    1   | 5    4    37  |
:---------------+---------------+---------------:
| 7    6    4   | 9    5    2   | 3    1    8   |
| 18   3    18  | 7    6    4   | 2    9    5   |
| 2    59   59  | 1    8    3   | 6    7    4   |
:---------------+---------------+---------------:
| 3    29   6   | 5    12   7   | 4    8    19  |
| 4    1    79  | 6    3    8   | 79   5    2   |
| 58   58   27  | 4    12   9   | 17   3    6   |
'---------------'---------------'---------------'

That's the BUG wychwood was talking about. You should read the explanation in ...

I understand how a BUG+1 works. You presumed that I reached the BUG+1 position after performing [r1c8]<>8. As it turns out, I only reached this position before my solver chose an XY-Chain between [r1c1] and [r2c9] to crack the puzzle.

Code: Select all
 *------------------------------------------------------------*
 |  15    4     135   | 8     7     6     | 19    2     139   |
 |  9     27    12    | 3     4     5     | 8     6     17    |
 |  6     78    38    | 2     9     1     | 5     4     37    |
 |--------------------+-------------------+-------------------|
 |  7     6     4     | 9     5     2     | 3     1     8     |
 |  18    3     18    | 7     6     4     | 2     9     5     |
 |  2     59    59    | 1     8     3     | 6     7     4     |
 |--------------------+-------------------+-------------------|
 |  3     29    6     | 5     12    7     | 4     8     19    |
 |  4     1     79    | 6     3     8     | 79    5     2     |
 |  58    258   2578  | 4     12    9     | 17    3     6     |
 *------------------------------------------------------------*
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby wychwood » Fri Jan 25, 2008 6:42 pm

Thanks for the help guys.

hobiwan: thanks for the link to sudopedia . Yes, a very clear explanation there of BUG and BUG + 1. Must remember that place for future reference. But why do they not include a "Naked Quintuple" in the solving techniques? I had one of those in a puzzle only yesterday. The "naked" techniques stop at quads, I notice.

daj: sorry mate, I have no idea what a "simple contradiction forcing net" might be (and I am not sure that I even want to know!!).

Both: call me old-fashioned, but I do like trying to solve these things 'manually', wihtout recourse to solving software (unless I get really stuck). So my references to the software was as a last resort, after hours of looking at the stuck state of the puzzle.

Cheers and thanks again
wychwood
 
Posts: 28
Joined: 08 February 2007

Postby hobiwan » Fri Jan 25, 2008 7:06 pm

wychwood wrote:But why do they not include a "Naked Quintuple" in the solving techniques? I had one of those in a puzzle only yesterday. The "naked" techniques stop at quads, I notice.


This is what ruud posted to me only a few days ago:

ruud wrote:In a 9x9 Sudoku, the largest naked/hidden subset you need to look for is of size 4. In a unit of N unsolved cells, each naked subset of size M has a complementary hidden subset of size N-M. The smaller of these 2 sets is always 4 or less.


daj95376: My reply was meant for wychwood, not for you. I have read enough of your posts to be pretty sure that you know what a BUG+1 is. It seems like I have to become more precise in my posts:D
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Stuck again - or I was

Postby Cec » Sat Jan 26, 2008 3:54 pm

hobiwan wrote:"....You should read the explanation in http://www.sudopedia.org/wiki/Bivalue_Universal_Grave, which is very clear ...."

In an attempt to understand the BUG + 1 principle I've read through the above link which used the following grid to explain this pattern:
Code: Select all
 
 *--------------------------------------------------*
 | 3    2    19   | 59   579  6    | 4    8    17   |
 | 79   6    8    | 4    79   1    | 2    3    5    |
 | 17   4    5    | 8    2    3    | 6    9    17   |
 |----------------+----------------+----------------|
 | 8    5    4    | 2    6    7    | 9    1    3    |
 | 69   3    69   | 1    8    5    | 7    4    2    |
 | 2    1    7    | 39   39   4    | 5    6    8    |
 |----------------+----------------+----------------|
 | 4    7    16   | 36   13   2    | 8    5    9    |
 | 16   8    2    | 56   15   9    | 3    7    4    |
 | 5    9    3    | 7    4    8    | 1    2    6    |
 *--------------------------------------------------*

The above link states that "this example shows a BUG+1, where the extra candidate is the digit 9 in r1c5. If r1c5 is not 9, then we obtain the BUG pattern. Therefore, 9 can be placed in that cell, and the Sudoku can be solved easily using singles. "

Because there are three candidates [579] in cell r1c5 I can't understand why candidate 9 is specifically chosen as the extra candidate in this cell..... why not chose candidate 5 or candidate 7?

Any help to clear my confusion would be appreciated. No rush.. I'm off to bed now (1.40am is past my bedtime):)

Cec
Cec
 
Posts: 1039
Joined: 16 June 2005

Postby Mike Barker » Sat Jan 26, 2008 7:34 pm

A BUG occurs when every unit contains only one or two candidates for each digit. In row 1 there are two 1's, 5's, and 7's, but three 9's. Similarly for column 5 and box 2. Every other unit contains only one or two candidates. Thus if r1c5<>9 a BUG occurs.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Stuck again - or I was

Postby Cec » Sun Jan 27, 2008 2:19 am

Thanks Mike for your explanation. Yes, it quickly becomes apparent that if you place either of the candidates 5 or 7 in cell r1c5, a contradiction occurs which confirms that candidate 9 is the correct placement in cell r1c5.

Cec
Cec
 
Posts: 1039
Joined: 16 June 2005

Postby wychwood » Tue Feb 05, 2008 4:17 pm

Obiwan said:
This is what ruud posted to me only a few days ago:

ruud wrote:
In a 9x9 Sudoku, the largest naked/hidden subset you need to look for is of size 4. In a unit of N unsolved cells, each naked subset of size M has a complementary hidden subset of size N-M. The smaller of these 2 sets is always 4 or less.




Interesting hypothesis and I can understand/see the validity of the maths.

BUT: say you had 8 unsolved cells in a column, and three of them had 7 or 8 candidates in them. Then, if the other 5 cells made up a naked quintuple, you would have to use that first to eliminate those 5 candidates from the other 3 cells. This is a naked quintuple in operation, because I feel pretty confident that you would see the naked quin first (if those 5 cells had 2, 3 4 or 5 candidates only in them) before you would see the naked triplet that was 'hidden' in the other 3 cells.

Cheers
wychwood
 
Posts: 28
Joined: 08 February 2007

Postby Pat » Tue Feb 05, 2008 4:31 pm

wychwood wrote:Interesting hypothesis and I can understand/see the validity of the maths.

BUT: say you had 8 unsolved cells in a column, and three of them had 7 or 8 candidates in them. Then, if the other 5 cells made up a naked quintuple, you would have to use that first to eliminate those 5 candidates from the other 3 cells. This is a naked quintuple in operation, because I feel pretty confident that you would see the naked quin first (if those 5 cells had 2, 3 4 or 5 candidates only in them) before you would see the naked triplet that was 'hidden' in the other 3 cells.


where you said
    I feel pretty confident that you would see the naked quin first
    before you would see the [ hidden ] triplet
i suggest the pronoun "you" should be "I" -- speak for yourself as to which is easier to find
User avatar
Pat
 
Posts: 3448
Joined: 18 July 2005

Postby hobiwan » Tue Feb 05, 2008 8:30 pm

wychwood wrote:BUT: say you had 8 unsolved cells in a column, and three of them had 7 or 8 candidates in them. Then, if the other 5 cells made up a naked quintuple, you would have to use that first to eliminate those 5 candidates from the other 3 cells. This is a naked quintuple in operation, because I feel pretty confident that you would see the naked quin first (if those 5 cells had 2, 3 4 or 5 candidates only in them) before you would see the naked triplet that was 'hidden' in the other 3 cells.

Personally I agree, because I suck with hidden subsets, but as Pat said, this is a matter of personal preference. Besides I would very much prefer not to have to look for quintuples when doing a puzzle with pencil and paper:D
hobiwan
2012 Supporter
 
Posts: 321
Joined: 16 January 2008
Location: Klagenfurt

Postby Pat » Thu Feb 07, 2008 4:04 pm

    it would be good for any SuDoku software to
    allow subsets of any size ( yes even 8 )
      with the ability to enable/disable each size
      separately for "hidden" and for "naked"
User avatar
Pat
 
Posts: 3448
Joined: 18 July 2005


Return to Help with puzzles and solving techniques