What methods do you use past forcing chains? (2nd try)

Advanced methods and approaches for solving Sudoku puzzles

What methods do you use past forcing chains? (2nd try)

Postby tso » Mon Feb 06, 2006 6:24 am

The puzzle I previously posted on this subject here was a bad example. Here are (what I hope are) three good examples of puzzles that cannot be solved by simple forcing chains -- whether bilocation, bivalue or mixed. Nishio will not help either.

(When I refer to "simple forcing chains", I refer to implication chains with no 'memory' in which each individual link directly implies the next, and each link is a connection between exactly two cells. "Beyond simple forcing chains" would include forcing nets and forcing chains in which one more more links is a connection between more than 2 cells -- as well as all the "almost locked whatsits and whosits.)

I was hoping to find another puzzle that left dead-ended with a higher number of solved and bivalue cells as in the previous post, but no luck so far. [EDIT -- I found three and added them to the bottom of this post.]


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


After easy tactics:
Code: Select all
+-------------------+-------------------+-------------------+
| 2679  789   3     | 26    1     4     | 679   2578  5789  |
| 269   189   4     | 7     69    5     | 1369  238   1389  |
| 2679  5     126   | 3     8     29    | 1679  247   1479  |
+-------------------+-------------------+-------------------+
| 8     2     5     | 1     34    6     | 37    9     347   |
| 1     6     7     | 9     34    8     | 5     34    2     |
| 4     3     9     | 5     2     7     | 8     1     6     |
+-------------------+-------------------+-------------------+
| 2359  149   128   | 24    7     129   | 139   6     13589 |
| 579   1479  18    | 46    69    3     | 2     578   15789 |
| 23679 179   126   | 8     5     129   | 4     37    1379  |
+-------------------+-------------------+-------------------+


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


After easy tactics:
Code: Select all
+-------------------+-------------------+-------------------+
| 2389  5     1     | 2689  248   3469  | 3489  248   7     |
| 4     3678  23679 | 25789 258   379   | 389   28    1     |
| 23789 378   2379  | 2789  1     3479  | 5     6     3489  |
+-------------------+-------------------+-------------------+
| 257   4     27    | 3     6     8     | 29    1     59    |
| 35    36    8     | 1     9     2     | 7     45    456   |
| 1     9     26    | 4     7     5     | 268   3     68    |
+-------------------+-------------------+-------------------+
| 789   2     5     | 6789  3     1     | 468   478   468   |
| 3789  1     3479  | 56789 458   4679  | 368   578   2     |
| 6     378   347   | 2578  2458  47    | 1     9     358   |
+-------------------+-------------------+-------------------+


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




After easy tactics:
Code: Select all
+-------------------+-------------------+-------------------+
| 239   6     1     | 3589  4589  3458  | 3459  248   7     |
| 4     5     239   | 7     6     38    | 1     28    239   |
| 7     39    8     | 1     459   2     | 3459  6     359   |
+-------------------+-------------------+-------------------+
| 2359  239   7     | 258   1     58    | 459   24    6     |
| 256   1     256   | 4     7     9     | 58    3     258   |
| 8     249   2459  | 25    3     6     | 7     1     259   |
+-------------------+-------------------+-------------------+
| 35    8     345   | 6     45    7     | 2     9     1     |
| 269   7     269   | 389   289   1     | 38    5     4     |
| 1     249   2459  | 3589  24589 3458  | 6     7     38    |
+-------------------+-------------------+-------------------+


[EDIT -- three more puzzles added]

These three puzzles dead-end in a "beyond forcing chains" position with more cells solved and more bivalue cells to work with than the previous three -- but all require advanced tactics (Mixed forcing chains, Nishio or both) to get there:

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


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


Code: Select all
+----------------+----------------+----------------+
| 4    12   13   | 38   5    6    | 28   9    7    |
| 6    29   5    | 1    89   7    | 238  23   4    |
| 8    7    39   | 239  239  4    | 5    1    6    |
+----------------+----------------+----------------+
| 19   3    4    | 5    1279 129  | 1279 6    8    |
| 7    5    169  | 2689 4    189  | 1239 23   39   |
| 2    8    169  | 69   1679 3    | 179  4    5    |
+----------------+----------------+----------------+
| 159  19   2    | 368  368  58   | 4    7    39   |
| 3    4    8    | 7    19   19   | 6    5    2    |
| 59   6    7    | 4    23   25   | 39   8    1    |
+----------------+----------------+----------------+



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


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



Code: Select all
+-------------------+-------------------+-------------------+
| 5     18    2     | 6     378   378   | 4     9     17    |
| 9     6     18    | 2     78    4     | 17    3     5     |
| 3     7     4     | 5     9     1     | 2     8     6     |
+-------------------+-------------------+-------------------+
| 4     5     378   | 178   6     9     | 1378  127   12378 |
| 1     9     6     | 78    2     378   | 5     4     378   |
| 2     38    378   | 147   3457  3578  | 1378  6     9     |
+-------------------+-------------------+-------------------+
| 7     4     5     | 9     18    6     | 38    12    1238  |
| 8     2     9     | 3     157   57    | 6     157   4     |
| 6     13    13    | 478   4578  2     | 9     57    78    |
+-------------------+-------------------+-------------------+




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

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


Code: Select all
+----------------+----------------+----------------+
| 123  9    138  | 4    12   7    | 15   6    58   |
| 7    28   4    | 12   6    5    | 139  38   29   |
| 6    12   5    | 8    9    3    | 17   47   24   |
+----------------+----------------+----------------+
| 8    3    2    | 9    7    1    | 6    45   45   |
| 9    4    6    | 5    3    8    | 2    1    7    |
| 15   157  17   | 6    4    2    | 8    9    3    |
+----------------+----------------+----------------+
| 1235 1578 137  | 13   125  9    | 4    78   6    |
| 4    257  379  | 23   8    6    | 3579 357  1    |
| 135  6    1389 | 7    15   4    | 359  2    589  |
+----------------+----------------+----------------+
tso
 
Posts: 798
Joined: 22 June 2005

Re: What methods do you use past forcing chains? (2nd try)

Postby Jeff » Mon Feb 06, 2006 9:49 am

Tso wrote:What methods do you use past forcing chains?

Hi Tso, 'Simple forcing chains', as defined in your post, are double implication forcing chains in which the chain nodes are single cells. Therefore, according to that definition and for the purposes of this thread, the following forcing chains/nets are not ‘simple forcing chains’:

Forcing chains that involve more than 2 implication streams
Forcing chains/nets that have nodes consisting of 2 or more cells
Forcing chains which have nodes that infer 2 or more nodes downstream

The method you are looking for are therefore include but not necessarily limited to the following:

  • Triple implication nice loops
  • Grouped nice loops
  • Multiple inference nice loops
  • Almost 'a-set-pattern' nice loops, eg. Almost uniqueness pattern nice loops
  • Family of almost locked set rules, eg, xz rules
  • POM
  • Fillet-O-fish
  • BUG and BUG-Lite
Together, I believe any grids can be solved and these can all be done without computer.:D
Jeff
 
Posts: 708
Joined: 01 August 2005

Re: What methods do you use past forcing chains? (2nd try)

Postby castalia » Mon Feb 06, 2006 10:39 am

Jeff wrote:Together, I believe any grids can be solved and these can all be done without computer.:D


That's an inspiring claim, Jeff. Perhaps you would care to try your hand at these:

http://home.comcast.net/~mshelor/files/impossible.db

The above were culled from Gordon Royle's minimum sudokus. Specifically, they are the 520 puzzles that stumped David Eppstein's solver.

Good luck!

Mark
castalia
 
Posts: 8
Joined: 22 January 2006

Postby Graeme » Mon Feb 06, 2006 11:03 am

Hi tso,

Here's my solver's output for puzzle #1. I'm not sure how this much monospaced text will come out, so I'll give the stats here as well:

Naked Single set 48 values and removed 98 candidates
Hidden Single set 5 values and removed 10 candidates
Naked Pair removed 1 candidate
Box/Line Reduction removed 4 candidates
Naked Triple/Quad removed 2 candidates
XY-Wing/XYZ-Wing removed 5 candidates

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


Naked Singles ...
   {2,6,7,9}      {6,7,8,9}          3            {2,6}            1              4          {6,7,8,9}      {2,5,7,8}      {5,7,8,9}   
    {2,6,9}       {1,6,8,9}          4              7          {2,3,6,9}       {2,5,9}      {1,3,6,8,9}     {2,3,5,8}     {1,3,5,8,9} 
   {2,6,7,9}          5          {1,2,6,9}       {2,3,6}           8            {2,9}       {1,3,6,7,9}     {2,3,4,7}     {1,3,4,7,9} 
       8              2             {5}          {1,3,4}         {3,4}            6            {3,7}            9           {3,4,7}   
       1            {4,6}            7              9            {3,4}            8              5            {3,4}            2       
     {4,9}            3             {9}             5            {2,4}          {2,7}          {7,8}            1              6       
  {2,3,4,5,9}     {1,4,8,9}     {1,2,5,8,9}      {1,2,4}           7           {1,2,9}       {1,3,8,9}          6         {1,3,5,8,9} 
  {4,5,6,7,9}   {1,4,6,7,8,9}   {1,5,6,8,9}      {1,4,6}        {4,6,9}           3              2           {5,7,8}      {1,5,7,8,9} 
  {2,3,6,7,9}     {1,6,7,9}      {1,2,6,9}          8              5           {1,2,9}           4            {3,7}        {1,3,7,9}   
Naked Single
  set value 5 in cell D3
  set value 9 in cell F3
Candidate removal left naked single
  set value 4 in cell F1
  set value 6 in cell E2
  set value 2 in cell F5
  set value 7 in cell F6
  set value 8 in cell F7

Hidden Singles ...
  {2,6,7,9}     {7,8,9}         3          {2,6}          1            4         {6,7,9}     {2,5,7,8}    {5,7,8,9} 
   {2,6,9}      {1,8,9}         4            7         {3,6,9}      {2,5,9}     {1,3,6,9}    {2,3,5,8}   {1,3,5,8,9}
  {2,6,7,9}        5         {1,2,6}      {2,3,6}         8          {2,9}     {1,3,6,7,9}   {2,3,4,7}   {1,3,4,7,9}
      8            2            5         {1,3,4}       {3,4}          6          {3,7}          9         {3,4,7}   
      1            6            7            9          {3,4}          8            5          {3,4}          2     
      4            3            9            5            2            7            8            1            6     
  {2,3,5,9}    {1,4,8,9}     {1,2,8}      {1,2,4}         7         {1,2,9}      {1,3,9}         6       {1,3,5,8,9}
  {5,6,7,9}   {1,4,7,8,9}    {1,6,8}      {1,4,6}      {4,6,9}         3            2         {5,7,8}    {1,5,7,8,9}
 {2,3,6,7,9}    {1,7,9}      {1,2,6}         8            5         {1,2,9}         4          {3,7}      {1,3,7,9} 
Hidden Single
  set value 5 in cell B6
  set value 1 in cell D4
  set value 3 in cell C4

Naked Pairs ...
  {2,6,7,9}     {7,8,9}         3          {2,6}          1            4         {6,7,9}     {2,5,7,8}    {5,7,8,9} 
   {2,6,9}      {1,8,9}         4            7          {6,9}          5        {1,3,6,9}     {2,3,8}     {1,3,8,9} 
  {2,6,7,9}        5         {1,2,6}         3            8          {2,9}      {1,6,7,9}     {2,4,7}     {1,4,7,9} 
      8            2            5            1          {3,4}          6          {3,7}          9         {3,4,7}   
      1            6            7            9          {3,4}          8            5          {3,4}          2     
      4            3            9            5            2            7            8            1            6     
  {2,3,5,9}    {1,4,8,9}     {1,2,8}       {2,4}          7         {1,2,9}      {1,3,9}         6       {1,3,5,8,9}
  {5,6,7,9}   {1,4,7,8,9}    {1,6,8}       {4,6}       {4,6,9}         3            2         {5,7,8}    {1,5,7,8,9}
 {2,3,6,7,9}    {1,7,9}      {1,2,6}         8            5         {1,2,9}         4          {3,7}      {1,3,7,9} 
Naked Pair removed candidate {4} from cell H5

Block/Line Reduction ...
  {2,6,7,9}     {7,8,9}         3          {2,6}          1            4         {6,7,9}     {2,5,7,8}    {5,7,8,9} 
   {2,6,9}      {1,8,9}         4            7          {6,9}          5        {1,3,6,9}     {2,3,8}     {1,3,8,9} 
  {2,6,7,9}        5         {1,2,6}         3            8          {2,9}      {1,6,7,9}     {2,4,7}     {1,4,7,9} 
      8            2            5            1          {3,4}          6          {3,7}          9         {3,4,7}   
      1            6            7            9          {3,4}          8            5          {3,4}          2     
      4            3            9            5            2            7            8            1            6     
  {2,3,5,9}    {1,4,8,9}     {1,2,8}       {2,4}          7         {1,2,9}      {1,3,9}         6       {1,3,5,8,9}
  {5,6,7,9}   {1,4,7,8,9}    {1,6,8}       {4,6}        {6,9}          3            2         {5,7,8}    {1,5,7,8,9}
 {2,3,6,7,9}    {1,7,9}      {1,2,6}         8            5         {1,2,9}         4          {3,7}      {1,3,7,9} 
Block/Line Reduction
  removed candidate {6} from cell H1
  removed candidate {6} from cell H3
  removed candidate {8} from cell G2
  removed candidate {8} from cell H2

XY-Wing & XYZ-Wing ...
  {2,6,7,9}     {7,8,9}         3          {2,6}          1            4         {6,7,9}     {2,5,7,8}    {5,7,8,9} 
   {2,6,9}      {1,8,9}         4            7          {6,9}          5        {1,3,6,9}     {2,3,8}     {1,3,8,9} 
  {2,6,7,9}        5         {1,2,6}         3            8          {2,9}      {1,6,7,9}     {2,4,7}     {1,4,7,9} 
      8            2            5            1          {3,4}          6          {3,7}          9         {3,4,7}   
      1            6            7            9          {3,4}          8            5          {3,4}          2     
      4            3            9            5            2            7            8            1            6     
  {2,3,5,9}     {1,4,9}      {1,2,8}       {2,4}          7         {1,2,9}      {1,3,9}         6       {1,3,5,8,9}
   {5,7,9}     {1,4,7,9}      {1,8}        {4,6}        {6,9}          3            2         {5,7,8}    {1,5,7,8,9}
 {2,3,6,7,9}    {1,7,9}      {1,2,6}         8            5         {1,2,9}         4          {3,7}      {1,3,7,9} 
XY-Wing (using cells A4, B5 & H4) removed candidate {6} from cell A4
Candidate removal left naked single
  set value 2 in cell A4
  set value 9 in cell C6
  set value 6 in cell B5
  set value 9 in cell H5
  set value 4 in cell G4
  set value 6 in cell H4
XY-Wing (using cells G2, G6 & H3) removed candidate {1} from cell G2
Candidate removal left naked single: set value 9 in cell G2
XY-Wing removed candidate {1} from cell G3

Hidden Singles ...
  {6,7,9}     {7,8}        3          2          1          4       {6,7,9}    {5,7,8}   {5,7,8,9}
   {2,9}      {1,8}        4          7          6          5       {1,3,9}    {2,3,8}   {1,3,8,9}
  {2,6,7}       5       {1,2,6}       3          8          9       {1,6,7}    {2,4,7}    {1,4,7} 
     8          2          5          1        {3,4}        6        {3,7}        9       {3,4,7} 
     1          6          7          9        {3,4}        8          5        {3,4}        2     
     4          3          9          5          2          7          8          1          6     
  {2,3,5}       9        {2,8}        4          7        {1,2}      {1,3}        6      {1,3,5,8}
   {5,7}     {1,4,7}     {1,8}        6          9          3          2       {5,7,8}   {1,5,7,8}
 {2,3,6,7}    {1,7}     {1,2,6}       8          5        {1,2}        4        {3,7}    {1,3,7,9}
Hidden Single
  set value 4 in cell H2
  set value 9 in cell J9

Searching for Naked Subsets ...
  {6,7,9}     {7,8}        3          2          1          4       {6,7,9}    {5,7,8}    {5,7,8} 
   {2,9}      {1,8}        4          7          6          5       {1,3,9}    {2,3,8}    {1,3,8} 
  {2,6,7}       5       {1,2,6}       3          8          9       {1,6,7}    {2,4,7}    {1,4,7} 
     8          2          5          1        {3,4}        6        {3,7}        9       {3,4,7} 
     1          6          7          9        {3,4}        8          5        {3,4}        2     
     4          3          9          5          2          7          8          1          6     
  {2,3,5}       9        {2,8}        4          7        {1,2}      {1,3}        6      {1,3,5,8}
   {5,7}        4        {1,8}        6          9          3          2       {5,7,8}   {1,5,7,8}
 {2,3,6,7}    {1,7}     {1,2,6}       8          5        {1,2}        4        {3,7}        9     
Naked Subset
  removed candidate {7} from cell A1
  removed candidate {7} from cell A7

Searching for XY-Wing & XYZ-Wing ...
   {6,9}      {7,8}        3          2          1          4        {6,9}     {5,7,8}    {5,7,8} 
   {2,9}      {1,8}        4          7          6          5       {1,3,9}    {2,3,8}    {1,3,8} 
  {2,6,7}       5       {1,2,6}       3          8          9       {1,6,7}    {2,4,7}    {1,4,7} 
     8          2          5          1        {3,4}        6        {3,7}        9       {3,4,7} 
     1          6          7          9        {3,4}        8          5        {3,4}        2     
     4          3          9          5          2          7          8          1          6     
  {2,3,5}       9        {2,8}        4          7        {1,2}      {1,3}        6      {1,3,5,8}
   {5,7}        4        {1,8}        6          9          3          2       {5,7,8}   {1,5,7,8}
 {2,3,6,7}    {1,7}     {1,2,6}       8          5        {1,2}        4        {3,7}        9     
XY-Wing (using cells D7, E8 & G7) removed candidate {3} from cell D7
Candidate removal left naked single: set value 7 in cell D7
XY-Wing removed candidate {3} from cell J8
Candidate removal left naked single:
  set value 7 in cell J8
  set value 1 in cell J2
  set value 8 in cell H3
  set value 2 in cell G3
  set value 1 in cell G6
  set value 2 in cell J6
  set value 3 in cell G7
  set value 5 in cell G1
  set value 7 in cell H1
  set value 8 in cell G9
  set value 5 in cell H8
  set value 1 in cell H9
  set value 3 in cell B9
  set value 4 in cell D9
  set value 3 in cell E8
  set value 4 in cell E5
  set value 3 in cell D5
  set value 7 in cell C9
  set value 8 in cell A8
  set value 2 in cell B8
  set value 9 in cell B1
  set value 6 in cell A1
  set value 2 in cell C1
  set value 1 in cell C3
  set value 8 in cell B2
  set value 7 in cell A2
  set value 5 in cell A9
  set value 6 in cell C7
  set value 9 in cell A7
  set value 1 in cell B7
  set value 6 in cell J3
  set value 3 in cell J1
  set value 4 in cell C8

PUZZLE SOLVED
~~~~~~~~~~~~~
6 7 3 | 2 1 4 | 9 8 5
9 8 4 | 7 6 5 | 1 2 3
2 5 1 | 3 8 9 | 6 4 7
------+-------+------
8 2 5 | 1 3 6 | 7 9 4
1 6 7 | 9 4 8 | 5 3 2
4 3 9 | 5 2 7 | 8 1 6
------+-------+------
5 9 2 | 4 7 1 | 3 6 8
7 4 8 | 6 9 3 | 2 5 1
3 1 6 | 8 5 2 | 4 7 9
Graeme
 
Posts: 18
Joined: 06 February 2006

Postby maria45 » Mon Feb 06, 2006 11:16 am

Hello tso,

well, I'm not quite sure about the meaning of your restriction regarding "no memory".
Without much effort, I could find a forcing chain in your first puzzle:

g9=5 or g1=5, k1=3, k3=6, k6=2, g6=1 > g9!=1

One could argue that there is a "memory" step involved in this, because you need both implications, k1=3 and k3=6 to get k6=2. Is this already ruled out in your restriction?

Anyhow, you asked, what human solvers would apply. Thats an example.

Greetings, Maria
maria45
 
Posts: 54
Joined: 23 October 2005

Re: What methods do you use past forcing chains? (2nd try)

Postby Jeff » Mon Feb 06, 2006 11:52 am

castalia wrote:
Jeff wrote:Together, I believe any grids can be solved and these can all be done without computer.:D


That's an inspiring claim, Jeff. Perhaps you would care to try your hand at these:

Hi Mark, I knew my statement would attract responses like yours.:D My statement was based on my belief that POM, since it considers all solution sets, can be used to solve every single puzzle. Unfortunately, since I am not an export of POM, this belief has still yet to be logically proven. Having said this, please do not rule out the fact that some very difficult puzzles can be solved by nice loops as Carcul has demonstrated from time to time.

BTW, I am interested to learn what solving techniques David Eppstein has implemented in his solver.
Jeff
 
Posts: 708
Joined: 01 August 2005

Postby Havard » Mon Feb 06, 2006 11:55 am

Hi Graeme.

I can't follow your solver, and it looks to me as it has a wrong xy-wing in your deduction.

XY-Wing (using cells D7, E8 & G7) removed candidate {3} from cell D7


As far as I can see, you are saing:

Code: Select all
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .
------+-------+------
. . . | . . . | D7. .
. . . | . . . | . E8.
. . . | . . . | . . .
------+-------+------
. . . | . . . | G7. .
. . . | . . . | . . .
. . . | . . . | . J8 .

which on the board is:
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .
------+-------+------
. . . | . . . | 37. .
. . . | . . . | . 34.
. . . | . . . | . . .
------+-------+------
. . . | . . . | 13. .
. . . | . . . | . . .
. . . | . . . | . 37 .


and then:
Candidate removal left naked single: set value 7 in cell D7


and:
XY-Wing removed candidate {3} from cell J8
Candidate removal left naked single:


But as far as I can see, this is not a proper xy-wing? And I can't understand how you can do those eliminations? (3 from J8 and D7)

can you explain what your solver is doing here?

havard
Havard
 
Posts: 378
Joined: 25 December 2005

Postby Graeme » Mon Feb 06, 2006 12:24 pm

Hi Havard,

Gotta head off to sleep now, then work tomorrow. I'll check it out and reply in about 20 hours ;-)
Graeme
 
Posts: 18
Joined: 06 February 2006

Postby Carcul » Mon Feb 06, 2006 1:00 pm

Hi Tso.

For puzzle #4 we have (and its not necessary to exclude previously "3" from r2c5):

[r3c4]=2=[r5c4]-2-[r5c8]-3-[r2c8]-2-[r2c2]-9-[r3c3]-3-[r3c4], => r3c4<>3;

[r1c4]-8-[r5c4]=8=[r5c6]-8-[r7c6]-5-[r9c6]-2-[r9c5](-3-[r2c5])-3-[r3c45]-9-[r2c5]-8-[r1c4], => r1c4<>8 and that solve the puzzle.

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

Postby tarek » Mon Feb 06, 2006 1:32 pm

Hi tso,

Thanx for the interesting puzzles. The puzzles do need (according to my solver) forcing chains & most of them can't be solved with the simple ones except 4,6:

Puzzle 4
Code: Select all
*--------------------------------------------------------*
| 4     12   *13   |*38    5     6    |-238  *9     7    |
| 6     29    5    | 1     389   7    | 238  #23    4    |
| 8     7    *39   |*239   239   4    | 5     1     6    |
|------------------+------------------+------------------|
| 19    3     4    | 5     1279  129  | 1279  6     8    |
| 7     5     169  | 2689  4     1289 | 1239 *23   *39   |
| 2     8     169  | 69    1679  3    | 179   4     5    |
|------------------+------------------+------------------|
| 159   19    2    |*368   368   58   | 4     7    *39   |
| 3     4     8    | 7     19    19   | 6     5     2    |
| 59    6     7    | 4     23    25   | 39    8     1    |
*--------------------------------------------------------*
Eliminating 3 From r1c7 (Almost finned Jellyfish in Columns 3489)
*--------------------------------------------------------*
| 4     12    13   | 38    5     6    | 28    9     7    |
| 6     29    5    | 1     389   7    | 238   23    4    |
| 8     7     39   | 239   239   4    | 5     1     6    |
|------------------+------------------+------------------|
| 19    3     4    | 5     1279  129  | 1279  6     8    |
| 7     5     169  | 2689  4     1289 | 1239  23    39   |
| 2     8     169  | 69    1679  3    | 179   4     5    |
|------------------+------------------+------------------|
| 159   19    2    | 368   368   58   | 4     7     39   |
| 3     4     8    | 7     19    19   | 6     5     2    |
| 59    6     7    | 4     23    25   | 39    8     1    |
*--------------------------------------------------------*
Eliminating 3 From r2c5 (Box 3 & Row 2 Box-Line interaction)
*--------------------------------------------------------*
| 4     12    13   | 38    5     6    | 28    9     7    |
| 6     29    5    | 1     89    7    | 238   23    4    |
| 8     7     39   | 239   239   4    | 5     1     6    |
|------------------+------------------+------------------|
| 19    3     4    | 5     1279  129  | 1279  6     8    |
| 7     5     169  | 2689  4     1289 | 1239  23    39   |
| 2     8     169  | 69    1679  3    | 179   4     5    |
|------------------+------------------+------------------|
| 159   19    2    | 368   368   58   | 4     7     39   |
| 3     4     8    | 7     19    19   | 6     5     2    |
| 59    6     7    | 4     23    25   | 39    8     1    |
*--------------------------------------------------------*
Candidates in r7c2 will force r7c4 to have only 68 as valid Candidates
r7c2=1: r7c2=1 => r1c2=2 => r1c7=8 => r1c4=3 => r7c4<>3 => r7c4=68
r7c2=9: r7c2=9 => r7c9=3 => r7c4<>3 => r7c4=68
Threfore r7c4=68
*--------------------------------------------------------*
| 4     12    13   | 38    5     6    | 28    9     7    |
| 6     29    5    | 1     89    7    | 238   23    4    |
| 8     7     39   | 239   239   4    | 5     1     6    |
|------------------+------------------+------------------|
| 19    3     4    | 5     1279  129  | 1279  6     8    |
| 7     5     169  | 2689  4     1289 | 1239  23    39   |
| 2     8     169  | 69    1679  3    | 179   4     5    |
|------------------+------------------+------------------|
| 159   19    2    | 68    368   58   | 4     7     39   |
| 3     4     8    | 7     19    19   | 6     5     2    |
| 59    6     7    | 4     23    25   | 39    8     1    |
*--------------------------------------------------------*
Eliminating 3 From r3c5 (Column 4 & Box 2 Box-line interaction)
*--------------------------------------------------------*
| 4     12    13   | 38    5     6    | 28    9     7    |
| 6     29    5    | 1     89    7    | 238   23    4    |
| 8     7     39   | 239   29    4    | 5     1     6    |
|------------------+------------------+------------------|
| 19    3     4    | 5     1279  129  | 1279  6     8    |
| 7     5     169  | 2689  4     1289 | 1239  23    39   |
| 2     8     169  | 69    1679  3    | 179   4     5    |
|------------------+------------------+------------------|
| 159   19    2    | 68    368   58   | 4     7     39   |
| 3     4     8    | 7     19    19   | 6     5     2    |
| 59    6     7    | 4     23    25   | 39    8     1    |
*--------------------------------------------------------*
Candidates in r5c4 will force r2c5 to have only 8 as valid Candidates
r5c4=2: r5c4=2 => r5c8=3 => r2c8=2 => r2c2=9 => r2c5=8
r5c4=6: r5c4=6 => r7c4=8 => r1c4=3 => r1c3=1 => r1c2=2 => r2c2=9 => r2c5=8
r5c4=8: r5c4=8 => r1c4=3 => r1c3=1 => r1c2=2 => r2c2=9 => r2c5=8
r5c4=9: r5c4=9 => r5c9=3 => r7c9=9 => r7c2=1 => r1c2=2 => r2c2=9 => r2c5=8
Threfore r2c5=8


Puzzle 6
Code: Select all
*--------------------------------------------------------*
| 123   9     138  | 4     12    7    | 15    6     58   |
| 7     128   4    | 12    6     5    | 139   38    29   |
| 6     12    5    | 8     9     3    | 17    47    24   |
|------------------+------------------+------------------|
| 8     3     2    | 9     7     1    | 6     45    45   |
| 9     4     6    | 5     3     8    | 2     1     7    |
| 15    157   17   | 6     4     2    | 8     9     3    |
|------------------+------------------+------------------|
| 1235  1578  137  | 13    125   9    | 4     3578  6    |
| 4     257   379  | 23    8     6    | 3579  357   1    |
| 135   6     1389 | 7     15    4    | 359   2     589  |
*--------------------------------------------------------*
Candidates in r9c9 will force r7c4 to have only 3 as valid Candidates
r9c9=5: r9c9=5 => r9c5=1 => r7c4=3
r9c9=8: r9c9=8 => r1c9=5 => r1c7=1 => r1c5=2 => r2c4=1 => r7c4=3
r9c9=9: r9c9=9 => r2c9=2 => r2c4=1 => r7c4=3
Threfore r7c4=3
*--------------------------------------------------------*
| 13    9     138  | 4     2     7    | 15    6     58   |
| 7     28    4    | 1     6     5    | 39    38    29   |
| 6     12    5    | 8     9     3    | 17    47    24   |
|------------------+------------------+------------------|
| 8     3     2    | 9     7     1    | 6     45    45   |
| 9     4     6    | 5     3     8    | 2     1     7    |
| 15    157   17   | 6     4     2    | 8     9     3    |
|------------------+------------------+------------------|
| 2     1578  17   | 3     15    9    | 4     578   6    |
| 4     57    379  | 2     8     6    | 3579  357   1    |
| 135   6     1389 | 7     15    4    | 359   2     589  |
*--------------------------------------------------------*
r1c3 Must only have 38 as valid Candidates (17 is a Naked Double in Column 3)
r8c3 Must only have 39 as valid Candidates (17 is a Naked Double in Column 3)
r9c3 Must only have 389 as valid Candidates (17 is a Naked Double in Column 3)
*--------------------------------------------------------*
| 13    9     38   | 4     2     7    | 15    6     58   |
| 7     28    4    | 1     6     5    | 39    38    29   |
| 6     12    5    | 8     9     3    | 17    47    24   |
|------------------+------------------+------------------|
| 8     3     2    | 9     7     1    | 6     45    45   |
| 9     4     6    | 5     3     8    | 2     1     7    |
| 15    157   17   | 6     4     2    | 8     9     3    |
|------------------+------------------+------------------|
| 2     1578  17   | 3     15    9    | 4     578   6    |
| 4     57    39   | 2     8     6    | 3579  357   1    |
| 135   6     389  | 7     15    4    | 359   2     589  |
*--------------------------------------------------------*
Eliminating 5 From r7c2 (1 & 7 in r7c3 form an XY wing with 5 in r7c5 & r8c2)
*--------------------------------------------------------*
| 13    9     38   | 4     2     7    | 15    6     58   |
| 7     28    4    | 1     6     5    | 39    38    29   |
| 6     12    5    | 8     9     3    | 17    47    24   |
|------------------+------------------+------------------|
| 8     3     2    | 9     7     1    | 6     45    45   |
| 9     4     6    | 5     3     8    | 2     1     7    |
| 15    157   17   | 6     4     2    | 8     9     3    |
|------------------+------------------+------------------|
| 2     178   17   | 3     15    9    | 4     578   6    |
| 4     57    39   | 2     8     6    | 3579  357   1    |
| 135   6     389  | 7     15    4    | 359   2     589  |
*--------------------------------------------------------*
Candidates in r2c7 will force r9c9 to have only 89 as valid Candidates
r2c7=3: r2c7=3 => r2c8=8 => r1c9=5 => r9c9<>5 => r9c9=89
r2c7=9: r2c7=9 => r2c9=2 => r3c9=4 => r4c9=5 => r9c9<>5 => r9c9=89
Threfore r9c9=89
*--------------------------------------------------------*
| 13    9     38   | 4     2     7    | 15    6     58   |
| 7     28    4    | 1     6     5    | 39    38    29   |
| 6     12    5    | 8     9     3    | 17    47    24   |
|------------------+------------------+------------------|
| 8     3     2    | 9     7     1    | 6     45    45   |
| 9     4     6    | 5     3     8    | 2     1     7    |
| 15    157   17   | 6     4     2    | 8     9     3    |
|------------------+------------------+------------------|
| 2     178   17   | 3     15    9    | 4     578   6    |
| 4     57    39   | 2     8     6    | 3579  357   1    |
| 135   6     389  | 7     15    4    | 359   2     89   |
*--------------------------------------------------------*
Candidates in r7c2 will force r8c8 to have only 37 as valid Candidates
r7c2=1: r7c2=1 => r7c3=7 => r8c2=5 => r8c8<>5 => r8c8=37
r7c2=7: r7c2=7 => r8c2=5 => r8c8<>5 => r8c8=37
r7c2=8: r7c2=8 => r2c2=2 => r3c2=1 => r3c7=7 => r3c8=4 => r4c8=5 => r8c8<>5 => r8c8=37
Threfore r8c8=37
*--------------------------------------------------------*
| 13    9     38   | 4     2     7    | 15    6     58   |
| 7     28    4    | 1     6     5    | 39    38    29   |
| 6     12    5    | 8     9     3    | 17    47    24   |
|------------------+------------------+------------------|
| 8     3     2    | 9     7     1    | 6     45    45   |
| 9     4     6    | 5     3     8    | 2     1     7    |
| 15    157   17   | 6     4     2    | 8     9     3    |
|------------------+------------------+------------------|
| 2     178   17   | 3     15    9    | 4     578   6    |
| 4     57    39   | 2     8     6    | 3579  37    1    |
| 135   6     389  | 7     15    4    | 359   2     89   |
*--------------------------------------------------------*
Candidates in r7c8 will force r8c3 to have only 9 as valid Candidates
r7c8=5: r7c8=5 => r4c8=4 => r4c9=5 => r1c9=8 => r1c3=3 => r8c3=9
r7c8=7: r7c8=7 => r8c8=3 => r8c3=9
r7c8=8: r7c8=8 => r9c9=9 => r2c9=2 => r3c9=4 => r4c9=5 => r1c9=8 => r1c3=3 => r8c3=9
Threfore r8c3=9
*-----------------------------------------------*
| 13   9    38  | 4    2    7   | 15   6    58  |
| 7    28   4   | 1    6    5   | 39   38   29  |
| 6    12   5   | 8    9    3   | 17   47   24  |
|---------------+---------------+---------------|
| 8    3    2   | 9    7    1   | 6    45   45  |
| 9    4    6   | 5    3    8   | 2    1    7   |
| 15   157  17  | 6    4    2   | 8    9    3   |
|---------------+---------------+---------------|
| 2    178  17  | 3    15   9   | 4    578  6   |
| 4    57   9   | 2    8    6   | 357  37   1   |
| 135  6    38  | 7    15   4   | 359  2    89  |
*-----------------------------------------------*
Eliminating 3 From r9c7 (Row 8 & Box 9 Box-line interaction)
*-----------------------------------------------*
| 13   9    38  | 4    2    7   | 15   6    58  |
| 7    28   4   | 1    6    5   | 39   38   29  |
| 6    12   5   | 8    9    3   | 17   47   24  |
|---------------+---------------+---------------|
| 8    3    2   | 9    7    1   | 6    45   45  |
| 9    4    6   | 5    3    8   | 2    1    7   |
| 15   157  17  | 6    4    2   | 8    9    3   |
|---------------+---------------+---------------|
| 2    178  17  | 3    15   9   | 4    578  6   |
| 4    57   9   | 2    8    6   | 357  37   1   |
| 135  6    38  | 7    15   4   | 59   2    89  |
*-----------------------------------------------*
Eliminating 5 From r1c7 (9 & 8 in r9c9 form an XY wing with 5 in r9c7 & r1c9)


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

Postby Carcul » Mon Feb 06, 2006 1:57 pm

Hi Tso.

For puzzle #5 we have (and is not necessary to eliminate “1” from r7c7):

1. [r4c9]=2=[r4c8]-2-[r7c8]-1-[r7c5]-8-[r2c5]-7-[r2c7]-1-[r1c9](-7-[r4c9|r5c9])-7-[r9c9](-8-[r4c9])-8-[r5c9]-3-[r4c9], => r4c9<>3,7,8.

2. [r6c456]-7-[r6c3]=7=[r4c3](-7-[r4c4])-7-[r4c89]-1-[r4c4]-8-[r5c4]-7-[r6c456] => r6c456<>7.

3. [r6c3]=7=[r4c3]-7-[r4c8]-1,2-[r7c9]=2=[r4c9]=1=[r1c9]-1-[r2c7]-7-[r6c7]=7=[r6c3], => r6c3=7.

4. [r2c7]=7=[r4c7]-7-[r4c8]-1,2-[r7c9]=2=[r4c9]=1=[r1c9]-1-[r2c7], => r2c7<>1 and that solve the puzzle.

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

Postby Carcul » Mon Feb 06, 2006 2:33 pm

Hi Tso.

For puzzle #6 we have (without eliminating “1” from r2c2):

1. [r9c3]=8=[r1c3]{=3=[r1c1]-3-[r9c1|r9c5](-5-[r9c7])-1-[r9c3]}-8-[r2c2|r2c4](-1-[r2c7])-2-[r2c9]-9-[r2c7]-3-[r9c7]-9-[r9c3], => r9c3<>1,9.

2. [r7c1]=2=[r1c1]-2-[r1c5]=2=[r2c4]{-2-[r8c4](-3-[r8c78]-5-[r9c9])-3-[r7c4]-1-[r7c1|r7c3]}-2-[r2c9]-9-[r9c9]-8-[r9c3](-3-[r7c1])-3-[r7c3]-7-[r6c3]-1-[r6c1]-5-[r7c1], => r7c1<>1,3,5 => r7c1=2.

3. [r9c7]=9=[r2c7]=3=[r2c8]=8=[r1c9]=5=[r1c7]-5-[r9c7], => r9c7<>5 => r9c7=9 and that solve the puzzle.

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

Re: What methods do you use past forcing chains? (2nd try)

Postby aeb » Mon Feb 06, 2006 5:01 pm

tso wrote:Puzzle 3 starting grid:
Code: Select all
+-------+-------+-------+
| . 6 1 | . . . | . . . |
| 4 5 . | 7 . . | . . . |
| 7 . 8 | . . 2 | . 6 . |
+-------+-------+-------+
| . . 7 | . 1 . | . . 6 |
| . 1 . | 4 . 9 | . 3 . |
| 8 . . | . 3 . | 7 . . |
+-------+-------+-------+
| . 8 . | 6 . . | 2 . 1 |
| . . . | . . 1 | . 5 4 |
| . . . | . . . | 6 7 . |
+-------+-------+-------+


After easy tactics:
Code: Select all
+-------------------+-------------------+-------------------+
| 239   6     1     | 3589  4589  3458  | 3459  248   7     |
| 4     5     239   | 7     6     38    | 1     28    239   |
| 7     39    8     | 1     459   2     | 3459  6     359   |
+-------------------+-------------------+-------------------+
| 2359  239   7     | 258   1     58    | 459   24    6     |
| 256   1     256   | 4     7     9     | 58    3     258   |
| 8     249   2459  | 25    3     6     | 7     1     259   |
+-------------------+-------------------+-------------------+
| 35    8     345   | 6     45    7     | 2     9     1     |
| 269   7     269   | 389   289   1     | 38    5     4     |
| 1     249   2459  | 3589  24589 3458  | 6     7     38    |
+-------------------+-------------------+-------------------+




(1,6)5 > (9,6)4 > (7,5)5 > (7,3)4 > (2,3)3 > (2,6)8 > (4,6)5 > (1,6)!5

eliminates 5 at (1,6).
aeb
 
Posts: 83
Joined: 29 January 2006

Re: What methods do you use past forcing chains? (2nd try)

Postby aeb » Mon Feb 06, 2006 5:10 pm

Jeff wrote:My statement was based on my belief that POM, since it considers all solution sets, can be used to solve every single puzzle.

Hmm. In my opinion POM is a technique for solving POM puzzles. One uses backtrack/recursion/trial-and-error to go from a given Sudoku puzzle to the start of the corresponding POM puzzle. Sometimes a difficult Sudoku puzzle is already solved by doing this backtrack that produces the possible number patterns, and no further POM work is required.
aeb
 
Posts: 83
Joined: 29 January 2006

Re: What methods do you use past forcing chains? (2nd try)

Postby aeb » Mon Feb 06, 2006 5:24 pm

tso wrote:After standard advanced stuff:

Code: Select all
+-------------------+-------------------+-------------------+
| 5     18    2     | 6     378   378   | 4     9     17    |
| 9     6     18    | 2     78    4     | 17    3     5     |
| 3     7     4     | 5     9     1     | 2     8     6     |
+-------------------+-------------------+-------------------+
| 4     5     378   | 178   6     9     | 1378  127   12378 |
| 1     9     6     | 78    2     378   | 5     4     378   |
| 2     38    378   | 147   3457  3578  | 1378  6     9     |
+-------------------+-------------------+-------------------+
| 7     4     5     | 9     18    6     | 38    12    1238  |
| 8     2     9     | 3     157   57    | 6     157   4     |
| 6     13    13    | 478   4578  2     | 9     57    78    |
+-------------------+-------------------+-------------------+

(9,5)8 > (2,5)7 > (2,7)1 > (1,9)7 > (9,9)8 > (9,5)!8 eliminates 8 at (9,5).
aeb
 
Posts: 83
Joined: 29 January 2006

Next

Return to Advanced solving techniques

cron