7/15/07 Nightmare...0 grams ALS

Discuss the <a href="http://www.sudocue.net/daily.php">Daily Sudoku Nightmare</a> here
Post Reply
Sudtyro
Hooked
Hooked
Posts: 49
Joined: Tue Jan 16, 2007 8:17 pm

7/15/07 Nightmare...0 grams ALS

Post by Sudtyro »

This exercise was undertaken to see if, in addition to the standard “basics” toolbox of solving methods, it might be possible to manually solve a difficult puzzle using only simple Alternating Inference Chains (AIC). And, just for the sake of argument, allowing no other solving techniques, such as patterns (like wings and fish), ALS’s, Nice loops, coloring, uniqueness arguments, APE, subset counting, etc.

The procedure to develop the AIC’s works mainly with the puzzle’s individual single-digit grids, using only the strong internal links in bivalue cells to allow for transfers among the grids. The technique may be of some interest to manual solvers who wish to broaden their AIC search skills and strategies.

The detailed solution procedure follows:
1. Apply the “basics” to the puzzle’s current grid position.
2. Separately construct the puzzle’s unresolved single-digit grids. In each grid, form X-chains (groups allowed) to look for eliminations. Process all grids and update as needed.
3. The trick at this point is to slightly modify the single-digit grids by including both digits of all of the puzzle’s bivalue cells. In other words, for a bivalue cell containing digits A and B, simply add digit A to digit B’s grid, and vice versa. The bivalue cells are then used to form both visual and actual links among the single-digit grids, as described below.
4. Select an initial “target” digit for possible eliminations.
5. Examine the target’s single-digit grid for two bivalue cells having different digits. If a multi-digit AIC can be formed that provides a strong-inference link between the target digits in those two bivalue cells, then eliminations may follow.
6. Repeat step 5 until no further eliminations are found.
7. Select a new target digit and return to step 5, until all of the grids have been processed.
8. Adjust the puzzle’s grid position and return to step 1.

With a little practice, it becomes quite straightforward (and almost fun) to form the AIC in step 5 by using other intermediate bivalue cells to move among the single-digit grids. There are also some interesting shortcuts available to help construct the AIC.

The Sudocue Nightmare for July 15, 2007, will be used to illustrate the solution procedure.

Code: Select all

  
000208000000000040905006010010009000200040830308600091100005087700000000036000000
---------------------
. . . | 2 . 8 | . . .
. . . | . . . | . 4 .
9 . 5 | . . 6 | . 1 .   
------+-------+------
. 1 . | . . 9 | . . .
2 . . | . 4 . | 8 3 .
3 . 8 | 6 . . | . 9 1
------+-------+------
1 . . | . . 5 | . 8 7
7 . . | . . . | . . .
. 3 6 | . . . | . . . 
---------------------
The grid position below results after an initial application of the “basics,” defined here as the first seven steps of Andrew Stuart’s on-line “Sudoku Solver.”

Code: Select all

------------------------------------------------------
46  467  13  | 2     13579  8    | 35679   567  3569   
68  2678 13  | 13579 13579  137  | 235679  4    235689  
9   278  5   | 4     37     6    | 237     1    238    
-------------+-------------------+--------------------
456 1    47  | 38    38     9    | 24567   2567 2456   
2   569  79  | 157   4      17   | 8       3    56     
3   45   8   | 6     257    27   | 457     9    1      
-------------+-------------------+--------------------
1   49   249 | 39    2369   5    | 23469   8    7     
7   58   249 | 1389  123689 1234 | 1234569 256  234569 
58  3    6   | 1789  12789  1247 | 12459   25   2459      
------------------------------------------------------
We note right off that the XYZ-wing, (137)r2c36|r3c5, would neatly provide for two quick eliminations, r2c45 <> 3. However, in keeping with the rules of this exercise, wings are not allowed. Per step 2, we look instead at the 3’s unresolved single-digit grid, as shown below, with the strong links indicated between the grid’s three conjugate pairs.

Code: Select all

----------------------
. . 3 | . 3 . | *3 . 3
    | |       |
. . 3 | 3 3 3 | *3 . 3
. . . | . 3 | |  3 . 3
------+-----|-+-------
. . . | 3-3 | |  . . .
. . . | . . | |  . . .
. . . | . . | |  . . .
------+-----|-+-------
. . . | 3 3 | |  3 . .
. . . | 3 3 3 |  3 . 3
. . . | . . . |  . . .
----------------------
Two grouped X-chains provide for the (starred) eliminations:
(3): r1c3 = r2c3 – r2c6 = r8c6 – r8c9 = r78c7 => r1c7 <> 3.
(3): r2c6 = r8c6 – r8c9 = r78c7 => r2c7 <> 3.

An observant reader may have also noticed the grid’s finned Swordfish, in columns 3,6,9 (or rows 3,4,7), where r3c9 is the fin. This (disallowed) fish pattern also implies r12c7 <> 3.

No other eliminations are found in the 3’s grid. And, in fact, no X-chain-based eliminations were found in any of the eight additional single-digit grids (admittedly, I may have missed some). So, we move next to step 3 of the solution procedure to include the bivalue cells in all nine grids. Strong links in the grids (shown below) are again indicated between conjugate pairs.

Code: Select all

. . 13----1 . | . . .      . . . | . . . | . .  .      . . 31| .  3  . | . . 3
    | |       |                  |       |                 | |         |      
. . 13| 1 1 1 | . . .      . 2 . | . . . | 2 .  2      . . 31| 3  3  3 | . . 3
      |       |              |   |       |                   |       | |      
. . . | . . . | . . .      . 2 . | . . . | 2 .  2      . . . | .  37 | | 3 . 3
------+-------+------      ------+-------+-------      ------+-------|-+------
. . . | . . . | . . .      . . . | . . . | 2 2  2      . . . | 38-38 | | . . .
      |       |                  |       |                   |       | |      
. . . | 1---17| . . .      . . . | . . . | . .  .      . . . | .  .  | | . . .
      |       |                  |       |                   |       | |       
. . . | . . . | . . .      . . . | . 2-27| . .  .      . . . | .  .  | | . . .
------+-------+------      ------+-------+-------      ------+-------|-+------
. . . | . . . | . . .      . . 2 | . 2 . | 2 .  .      . . . | 39 3  | | 3 . .
      |       |                | |       |                   |       | |      
. . . | 1 1 1 | 1 . .      . . 2 | . 2 2 | 2 2  2      . . . | 3  3  3 | 3 . 3
      |       | |                |       |                   |         |      
. . . | 1 1 1 | 1 . .      . . . | . 2 2 | 2 25 2      . . . | .  .  . | . . .

Code: Select all

46-4  . | . . . | . . .     . .  . | . 5 . | 5 5  5      64 6 . | .  .  . | 6 6 6
|       |       |                  |       |                    |         |      
|  .  . | . . . | . . .     . .  . | 5 5 . | 5 .  5      68 6 . | .  .  . | 6 . 6
|       |       |                  | |     |                    |         |      
|  .  . | . . . | . . .     . .  . | | . . | . .  .      .  . . | .  .  . | . . .
|-------+-------+------     -------+-|-----+-------      -------+---------+------
4  .  47| . . . | 4 . 4     5 .  . | | . . | 5 5  5      6  . . | .  .  . | 6 6 6
        |       |           |      | |     |               \    |         |      
.  .  . | . . . | . . .     | 5  . | 5 . . | . .  56     .  6-------------------65
        |       |           |      |  \    |                    |         |       
.  45-------------4 . .     | 54 . | . 5 . | 5 .  .      .  . . | .  .  . | . . .
--------+-------+------     |------+-------+-------      -------+---------+------
.  49 4 | . . . | 4 . .     | .  . | . . . | . .  .      .  . . | .  6  . | 6 . .
        |       |           |      |       |                    |    |    |      
.  .  4 | . . 4 | 4 . 4     | 58 . | . . . | 5 5  5      .  . . | .  6  . | 6 6 6
        |     | |           |/     |       |                    |         |      
.  .  . | . . 4 | 4 . 4     58 . . | . . . | 5 52 5      .  . . | .  .  . | . . . 

Code: Select all

. 7 . | . 7  . | 7 7 .     .  . . | . .   . | . . .      . .  . | .  9 . | 9 . 9
      |        |   |              |         |                   |        |      
. 7 . | 7 7  7 | 7 | .     86 8 . | . .   . | . . 8      . .  . | 9  9 . | 9 . 9
      |        |   |       |      |         |     |             |        |      
. 7 . | . 73 . | 7 | .     |  8-------------------8      . .  . | .  . . | . . .
------+--------+---|--     |------+---------+------      -------+--------+------
. . 74| . .  . | 7 7 .     |  . . | 83-83 . | . . .      . .  . | .  . . | . . .
    | |        |           |      |         |                   |        |      
. . 79| 7 .  71| . . .     |  . . | . .   . | . . .      . 9--97| .  . . | . . .
      |        |           |      |         |              |    |        |       
. . . | . 7  72| 7 . .     |  . . | . .   . | . . .      . |  . | .  . . | . . .
------+--------+------     |------+---------+-------     --|----+--------+------
. . . | . .  . | . . .     |  . . | . .   . | . . .      . 94 9 | 93 9 . | 9 . .
      |        |           |      |         |                   |        |      
. . . | . .  . | . . .     | 85 . | 8 8   . | . . .      . .  9 | 9  9 . | 9 . 9
      |        |           |/     |         |                   |        |      
. . . | 7 7  7 | . . .     85 . . | 8 8   . | . . .      . .  . | 9  9 . | 9 . 9
We move on to step 4 and choose the 1-digit as the first “target.” Applying step 5 to the 1’s grid, only two bivalue cells could lead to an elimination. If we can show a derived strong inference (DSI) between the 1’s in cells (13)r2c3 and (17)r5c6, then (1)r2c6 can be eliminated.

Starting with cell r2c3, we first use the strong link, (1=3)r2c3, to move to the 3’s grid, where we need to connect to another bivalue cell. The only suitable chain available is
(1=3)r2c3 – (3)r2c6 = (3)r8c6 – (3=9)r7c4.
Moving next to the 9’s grid, we can now form the chain,
(3=9)r7c4 – (9)r7c2 = (9)r5c2 – (9=7)r5c3.
Moving finally to the 7’s grid, we can immediately spot the short chain,
(9=7)r5c3 – (7=1)r5c6,
and we’re done! Simply combine the three chains for the full AIC:
(1=3)r2c3 – (3)r2c6 = (3)r8c6 – (3=9)r7c4 – (9)r7c2 = (9)r5c2 – (9=7)r5c3 – (7=1)r5c6 => r2c6 <> 1.

To recap, a “grid path” was developed as 1 -> 3 -> 9 -> 7 -> 1 by forming three intermediate AIC’s. The first and last digits of each chain correspond to every other digit in the grid path, with the intervening digit identifying the host grid. Each sequential pair of digits in the grid path represents a bivalue-cell transfer point between grids. The grid path is bi-directional, so one can search in either direction or even search simultaneously from each end and try to “meet in the middle.”

We next choose the 2-digit as the target. Applying step 5 to the 2’s grid, we again see only two bivalue cells that could lead to an elimination. As before, if we can show a DSI between the 2’s in bivalue cells (27)r6c6 and (25)r9c8, then (2)r9c6 can be eliminated.

Starting this time with cell r9c8, we first use the strong link, (2=5)r9c8, to move to the 5’s grid, where we need to connect to another bivalue cell and move along to the next grid. The grid path develops as 2 -> 5 -> 4 -> 7 -> 2, and the reader can easily verify that the full AIC is
(2=5)r9c8 – (5)r9c1 = (5)r8c2 – (5=4)r6c2 – (4=7)r4c3 – (7)r3c78 = (7)r6c7 – (7=2)r6c6 => r9c6 <> 2.

We next choose the 3-digit as the target. Applying step 5 to the 3’s grid, we now see that multiple bivalue-cell pairings could potentially lead to eliminations. Surprisingly, however, no suitable grid paths are found.

We move on to digit 4 as the next target. Multiple bivalue-cell pairings are again possible, and cells (46)r1c1 and (45)r6c2 could provide a very productive double elimination. The short grid path, 4 -> 5 -> 6 -> 4, can be developed beginning with cell (45)r6c2. The full AIC is
(4=5)r6c2 – (5)r6c5 = (5)r5c4 – (5=6)r5c9 –(6)r5c2 = (6)r4c1 – (6=4)r1c1 => r1c2,r4c1 <> 4.

Of the remaining grids (5 to 9), suitable paths were found only for the 5’s and the 8’s.
For the 5-digit as the target, the short grid path, 5 -> 6 -> 8 -> 5, leads to the AIC,
(5=6)r5c9 – (6)r5c2 = (6)r4c1 –(6=8)r2c1 – (8=5)r9c1 => r9c9 <> 5.

For the 8-digit as the target, the grid path, 8 -> 3 -> 9 -> 4 -> 5 -> 8, leads to the AIC (also an XY-chain),
(8=3)r4c4 – (3=9)r7c4 – (9=4)r7c2 – (4=5)r6c2 – (5=8)r8c2 => r8c4 <> 8.

Having now completed the first pass through all nine single-digit grids, we pause at this point (step 8) to adjust the grid positions. The newly formed (37) naked pair removes all other 3’s and 7’s in b2. The adjusted 6’s grid (r1c1 <> 6) now provides a new X-chain,
(6): r5c9 = r5c2 – r4c1 = r2c1 => r2c9 <> 6.

After follow-up (updated single-digit grids are not shown):

Code: Select all

------------------------------------------------------- 
4    67   13  | 2     159    8    | 5679    567  3569    
-68  2678 13  | 159   159    37   | 25679   4    23589
9    278  5   | 4     37     6    | 237     1    238    
--------------+-------------------+--------------------
56   1    47  | 38    38     9    | 24567   2567 2456   
2    5-69 79  | 157   4      17   | 8      3    56     
3    45   8   | 6     257    27   | 457     9    1     
--------------+-------------------+--------------------
1    49   249 | 39    2369   5    | 23469   8    7     
7    58   249 | 139   123869 1234 | 1234569 256  234569
58   3    6   | 1789  12789  147  | 12459   25   2459  
-------------------------------------------------------
New bivalue cells, (67)r1c2 and (56)r4c1, provide a new grid path,
6 -> 7 -> 4 -> 5 -> 6.
The AIC is given by
(6=7)r1c2 – (7)r1c8 = (7)r4c8 - (7=4)r4c3 – (4=5)r6c2 – (5=6)r4c1 => r2c1,r5c2 <> 6.

After follow-up:

Code: Select all

------------------------------------------------------ 
4   67   13  | 2      159     8    | 5679    567  359 
8   267  13  | -159   159     37   | 25679   4    2359
9   27   5   | 4      37      6    | 237     1    8    
-------------+---------------------+------------------
6   1    47  | 38     38      9    | 2457    57   245 
2   59   79  | 157    4       17   | 8       3    6   
3   45   8   | 6      257     27   | 47      9    1   
-------------+---------------------+------------------
1   49   249 | 39     2369    5    | 3469    8    7   
7   8    249 | 1-39   -12-369 1234 | 1-34569  56  3459
5   3    6   | 1789   -1789   147  | 149     2    49  
------------------------------------------------------
The updated 3’s grid next yields the X-chain,
(3): r8c6 = r2c6 – r3c5 = r3c7 => r8c7 <> 3,
followed by
(3): r8c6 = r2c6 – r3c5 = r3c7 – r7c7 = r8c9 => r8c45 <> 3.

Then, newly formed bivalue cell, (19)r8c4, quickly provides the new grid path,
1 -> 3 -> 9 -> 1. The AIC is
(1=3)r2c3 – (3)r2c6 = (3)r8c6 – (3=9)r7c4 – (9=1)r8c4 => r2c4 <> 1,
which further implies r89c5 <> 1 via the new pointing pair in b2.

After follow-up:

Code: Select all

-------------------------------------------------- 
4   67   13  | 2     159   8    | 5679   567  359 
8   267  13  | 59    159   37   | 25679  4    2359
9   27   5   | 4     37    6    | 237    1    8    
-------------+------------------+-----------------
6   1    47  | 38    3-8    9   | 2457   57   245 
2   59   79  | 157   4     17   | 8      3    6   
3   45   8   | 6     257   27   | 47     9    1   
-------------+------------------+-----------------
1   49   249 | 39    2369  5    | 3469   8    7   
7   8    249 | 19    269   1234 | 14569  56   3459
5   3    6   | 17-89 -789  147  | 149    2    49  
--------------------------------------------------
At this point, the rote solution procedure begins to run low on suitable grid paths. One new path, 7 -> 3 -> 9 -> 7, moves from bivalue cell (37)r3c5 to (79)r5c3, but no direct eliminations are available. However, one can simply add two more of the 7-grid’s cells to the end of the path to form the AIC,
(7=3)r3c5 – (3)r4c5 =(3)r4c4 – (3=9)r7c4 – (9)r7c2 = (9)r5c2 – (9=7)r5c3 – (7)r5c4 = (7)r9c4 => r9c5 <> 7.

Then, newly formed bivalue cell, (89)r9c5, provides for the short grid path, 8 –> 9 –> 3 -> 8, and the corresponding very productive AIC (also an XY-chain),
(8=9)r9c5 – (9=3)r7c4 – (3=8)r4c4 => r4c5,r9c4 <> 8.

After follow-up:

Code: Select all

--------------------------------------------------  
4   67   3   | 2     1      8    | 5679    567  59   
8   67   1   | 59    59     3    | 67      4    2 
9   2    5   | 4     7      6    | 3       1    8 
-------------+-------------------+----------------
6   1    47  | 8     3      9    | 2       57   45
2   59   79  | 157   4      17   | 8       3    6 
3   45   8   | 6     25     27   | 47      9    1 
-------------+-------------------+----------------
1   49   249 | 3     269    5    | 469     8    7
7   8    249 | 19    269    124  | 14569   56   3 
5   3    6   | 179   8      147  | 149     2    -49
--------------------------------------------------
Once again, no suitable grid paths are to be found. However, the non-procedure AIC,
(4)r9c6 = (4-2)r8c6 = (2-7)r6c6 = (7-4)r6c7 = (4)r4c9 => r9c9 <> 4,
now breaks the puzzle and allows one to move quickly to the solution with cascading singles.

Summary:
This exercise has shown (for one sample puzzle, at least) that it is indeed possible to solve a difficult puzzle using only simple AIC’s. The idea for the “grid-path” approach stems from my own solution strategy of routinely constructing a puzzle’s single-digit grids in order to more easily apply the standard suite of single-digit solving methods. However, once those methods have been exhausted, one must then move on to the multi-digit techniques. By simply appending the puzzle’s bivalue cells to the single-digit grids, it becomes relatively easy to see and exploit some of the available multi-digit (strong) links, without the need for any additional plots or graphs.

With a little practice the grid-path approach is readily implemented as a simple visual search procedure. The intermediate chains that connect the bivalue cells in each single-digit grid can be developed ahead of time and jotted down for later use. There are initially only two or three of these chains per grid (some grids may have none). They are easily spotted, and in actual use it is necessary to remember only the first and last digit in each chain.

Eventually, when the supply of suitable grid paths runs out (as it did late in this exercise), one must move on to different solution methods. In practice, of course, the grid-path approach should never be used as a stand-alone technique, but rather simply as another choice available from the “beyond-the-basics” toolbox.

Questions, comments and suggestions are always welcome!
[Edited 11/10/07 to correct XYZ-wing name]
Post Reply