i got stuck here-any clue is welcome

Advanced methods and approaches for solving Sudoku puzzles

i got stuck here-any clue is welcome

Postby rmadhusudanan » Mon Dec 12, 2005 5:14 am

- - - - - 8 - - 6
- 4 - 3 - 98 - -
8 - - 5 - - 7 - -
- - 1 - - - 2 - -
7 - 428 - - - 5
2 - 6 - - - 3 - -
4 - 38 - 1 - - 9
- - - 4 - 2 - 8 -
5 - 8 - - - - - -

Madhusudanan
rmadhusudanan
 
Posts: 5
Joined: 28 November 2005

Postby Shazbot » Mon Dec 12, 2005 8:18 am

You didn't give your candidate list so I don't know what you've already eliminated.
Code: Select all
 *-----------*
 |...|..8|..6|
 |.4.|3.9|8..|
 |8..|5..|7..|
 |---+---+---|
 |..1|...|2..|
 |7.4|28.|..5|
 |2.6|...|3..|
 |---+---+---|
 |4.3|8.1|..9|
 |...|4.2|.8.|
 |5.8|...|...|
 *-----------*

 
 *----------------------------------------------------------------------*
 | 139   123579  2579  | 17    1247    8      | 1459    123459  6       |
 | 16    4       257   | 3     1267    9      | 8       125     12      |
 | 8     12369   29    | 5     1246    46     | 7       12349   1234    |
 |---------------------+----------------------+-------------------------|
 | 39    3589    1     | 679   345679  34567  | 2       4679    478     |
 | 7     39      4     | 2     8       36     | 169     169     5       |
 | 2     589     6     | 179   14579   457    | 3       1479    1478    |
 |---------------------+----------------------+-------------------------|
 | 4     267     3     | 8     567     1      | 56      2567    9       |
 | 169   1679    79    | 4     35679   2      | 156     8       137     |
 | 5     12679   8     | 679   3679    367    | 146     123467  12347   |
 *----------------------------------------------------------------------*


Locked Candidates:
1s in box 5
2s in box 7
5s in boxes 4 and 8

Naked Pair:
3/9 in box 4

Next step given by Simple Sudoku (sorry - running short on time so have to resort to that step immediately) is multiple colours for a further elimination.
Shazbot
 
Posts: 220
Joined: 24 September 2005

Postby bennys » Mon Dec 12, 2005 8:35 am

If A have degrees of freedom of 2
and B and C are ALS
with
x restricted common to A and B
y restricted common to A and C
and z common to A B C
then you cant have z in a cell that can see all the z candidates in A B C.
Code: Select all
+----------------------+----------------------+----------------------+
| 139   *1379   2579   |$17     1247   8      | 1459   123459 6      |
|#16     4      257    | 3      1267   9      | 8      125    12     |
| 8     *1369   29     | 5      1246   46     | 7      12349  1234   |
+----------------------+----------------------+----------------------+
| 39     58     1      | 679    34679  34567  | 2      4679   478    |
| 7     *39     4      | 2      8      36     | 169    169    5      |
| 2      58     6      | 179    1479   457    | 3      479    478    |
+----------------------+----------------------+----------------------+
| 4      267    3      | 8      567    1      | 56     2567   9      |
| 169    1679   79     | 4      35679  2      | 156    8      137    |
| 5      12679  8      | 679    3679   367    | 146    123467 12347  |
+----------------------+----------------------+----------------------+
a={r1c2,r3c2,r5c}
b={r2c1}
c={r1c4}
x=6
y=7
z=1
bennys
 
Posts: 156
Joined: 28 September 2005

Postby rubylips » Mon Dec 12, 2005 11:50 am

Before anything complicated is attempted, note it's possible to remove 9 from r1c1:

Code: Select all
Consider the chain r1c1~9~r1c7-9-r5c7~9~r5c2-9-r4c1.
When the cell r1c1 contains the value 9, so does the cell r4c1 - a contradiction.
Therefore, the cell r1c1 cannot contain the value 9.

Back to the main problem.
bennys wrote:you cant have z in a cell that can see all the z candidates in A B C.

I think this means 1 has been eliminated from r1c1. That elimination is clearly more powerful once the 9 has been eliminated from the cell - however, it still doesn't solve the puzzle.

First, here's an alternative solution to the original problem (after the 9 has been eliminated from r1c1):

Code: Select all
Consider the chain r4c1-<9|1>-r1c1~1~r1c4~7~r1c2=<7|9>=r5c2-9-r4c1.
When the cell r4c1 doesn't contain the value 9, the chain is self-contradicting.
Therefore, the cell r4c1 must contain the value 9.

The subtle link here is r1c2=<7|9>=r5c2. When r1c2 doesn't contain a 7, {r1c1,r1c2,r2c1,r3c2} contain {1,3,6,9} in such a way that the 9 in Column 2 must lie in r1c2 or r3c2 - therefore, r5c2 cannot contain a 9.

After that elimination, progress is straightforward to here:

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

   3    79  2579 |  1   27  8 |  49  2459     6
  16     4   257 |  3  267  9 |   8   125    12
   8    16    29 |  5   26  4 |   7  1239   123
-----------------+------------+----------------
   9     5     1 |  7    4  3 |   2     6     8
   7     3     4 |  2    8  6 |  19    19     5
   2     8     6 |  9    1  5 |   3    47    47
-----------------+------------+----------------
   4    27     3 |  8    5  1 |   6    27     9
  16  1679    79 |  4   39  2 |   5     8   137
   5   129     8 |  6   39  7 |  14  1234  1234

Here, when r3c5 contains 2, r1c5 contains 7, r1c2 contains 9 so r3c3 contains 2 - a contradiction, which forces r3c5 to take the 6.

It's now straightforward to here:

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

  3  79  2579 |  1  27  8 |  49  2459     6
  6   4   257 |  3  27  9 |   8   125    12
  8   1    29 |  5   6  4 |   7   239    23
--------------+-----------+----------------
  9   5     1 |  7   4  3 |   2     6     8
  7   3     4 |  2   8  6 |  19    19     5
  2   8     6 |  9   1  5 |   3    47    47
--------------+-----------+----------------
  4  27     3 |  8   5  1 |   6    27     9
  1   6    79 |  4  39  2 |   5     8    37
  5  29     8 |  6  39  7 |  14  1234  1234

whereupon we have:

Code: Select all
Consider the cell r1c2.
When it contains the value 7, the value 2 in Row 1 must occupy the cell r1c5.
When it contains the value 9, the value 2 in Box 1 must occupy the cell r3c3.
Whichever value it contains, the cells r1c1 and r1c3 cannot contain the value 2.
- The move r1c3:=2 has been eliminated.
Consider the cell r8c9.
When it contains the value 3, the values 1 and 2 in Column 9 must occupy the cells r2c9 and r3c9 in some order.
When it contains the value 7, the value 2 in Box 9 must occupy the cell r7c8.
Whichever value it contains, the cells r7c9 and r9c9 cannot contain the value 2.
- The move r9c9:=2 has been eliminated.
The value 2 in Box 3 must lie in Column 9.
- The moves r1c8:=2, r2c8:=2 and r3c8:=2 have been eliminated.
The cell r1c5 is the only candidate for the value 2 in Row 1.
---
The value 7 is the only candidate for the cell r2c5.
---
Consider the cell r1c8.
When it contains the value 5, the values 1 and 9 in Column 8 must occupy the cells r2c8 and r5c8 in some order.
When it contains the value 4, the value 9 in Box 3 must occupy the cell r1c7.
Whichever value it contains, the cell r3c8 cannot contain the value 9.
- The move r3c8:=9 has been eliminated.
The value 3 is the only candidate for the cell r3c8.
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby Carcul » Mon Dec 12, 2005 1:47 pm

Hi Rubylips.

In the last step of your solution, when you consider the cell r1c8, we can also apply the BUG principle to say that r1c8 = 9.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby rubylips » Mon Dec 12, 2005 3:07 pm

Thanks Carcul. I'll have to read all those BUG posts again as the idea didn't sink in first time.
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby ronk » Mon Dec 12, 2005 8:14 pm

rubylips wrote:First, here's an alternative solution to the original problem (after the 9 has been eliminated from r1c1):

Code: Select all
Consider the chain r4c1-<9|1>-r1c1~1~r1c4~7~r1c2=<7|9>=r5c2-9-r4c1.
When the cell r4c1 doesn't contain the value 9, the chain is self-contradicting.
Therefore, the cell r4c1 must contain the value 9.

The subtle link here is r1c2=<7|9>=r5c2. When r1c2 doesn't contain a 7, {r1c1,r1c2,r2c1,r3c2} contain {1,3,6,9} in such a way that the 9 in Column 2 must lie in r1c2 or r3c2 - therefore, r5c2 cannot contain a 9.

That seems like *such* a non-elegant alternative, I'm surprised you would even propose it. Why not just use bennys' elimination of candidate 1 in r1c1? It's elegant and eminently easier to understand IMO.

[edit: OK, OK, I see now that "r4c1-<9|1>-r1c1" is a re-syntaxed "r4c1+<9|1>+r1c1". But "r1c2=<7|9>=r5c2" meaning, if I've got this right, ... if r1c2<>7, then r5c2<>9 ... well, that's the epitome of obfuscation.]
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ronk » Tue Dec 13, 2005 2:21 am

Carcul wrote:when you consider the cell r1c8, we can also apply the BUG principle to say that r1c8 = 9.

Doesn't that imply that for each of the alternate candidates, r1c8=4 and r1c8=5, we would end up with a grid of only filled cells and bivalued cells? That doesn't happen for either of the alternates. Rather ... contradictions are the result.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Carcul » Tue Dec 13, 2005 11:15 am

Hi Ronk.

Ronk wrote:Doesn't that imply that for each of the alternate candidates, r1c8=4 and r1c8=5, we would end up with a grid of only filled cells and bivalued cells?


No. That imply that if r1c8<>9, then r1c8=4,5 and we would have a grid with only filled cells and bivalue cells with no elimination possible. This would mean that the grid could have more than one solution, which, in principle, is not what we want. So, r1c8 must be 9 in order for the grid have only one solution.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby ronk » Tue Dec 13, 2005 3:45 pm

Carcul wrote:
Ronk wrote:Doesn't that imply that for each of the alternate candidates, r1c8=4 and r1c8=5, we would end up with a grid of only filled cells and bivalued cells?

No. That imply that if r1c8<>9, then r1c8=4,5 and we would have a grid with only filled cells and bivalue cells with no elimination possible.

You're right, of course. That's why trivalues are presented by some as "45+9", for example.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA


Return to Advanced solving techniques