Snakes and Loops

Everything about Sudoku that doesn't fit in one of the other sections

Snakes and Loops

Postby Condor » Sun Apr 29, 2007 2:31 am

While using Simple Sudoku, I have had some observations that are interesting to me and thought worth commenting on. These patterns are made when filtering on numbers. I will assume people reading this will know how to use Simple Sudoku or some program like it which does filtering on numbers.

To make this discussion easier, I will give some definitions first. In the grids following, some candidate positions will be shown, marked with an 'X'. All the Xs refer to the same number, and it does not matter which number is refered to. (It would be like the program highlighting the cells without showing the number)

Connection.

2 boxes are connected if 1 or more candidates in that box is in the same row or column as the other box. Here are 2 examples.
Code: Select all
 *-----------------------*
 | . X . | . . X | . . . |
 | . X . | . . X | . . . |
 | . . . | . . . | . . . |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 *-----------------------*

 *-----------------------*
 | . X . | . . X | . . . |
 | . . . | . . X | . X . |
 | . X . | . . . | . X . |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 *-----------------------*


In the second example, box 1 is connected to box 2 which is then connected to box 3, even though each box has only 1 candidate on the same row as the other box.

In the following grid, boxes 2 and 3 are not connected.
Code: Select all
 *-----------------------*
 | . X . | . X . | . . . |
 | . . . | . . . | X . X |
 | . X X | . X . | . . . |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 |-------+-------+-------|
 | . X . | . . . | X . . |
 | . . X | . . . | . . X |
 | . . . | . . . | . . . |
 *-----------------------*


End.

An End occurs when the candidates are in only one row or column and the box is connected to only 1 other box. In the second example above, boxes 1 and 3 are Ends, but 2 is not because it is connected to both 1 and 3.

In the following grid, boxes 1 and 9 are ENDs.
Code: Select all
 *-----------------------*
 | . X . | . . . | . . X |
 | . . . | . . . | . . . |
 | . X . | . . . | . X X |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 |-------+-------+-------|
 | . . . | . . . | . X X |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 *-----------------------*


Snake.

A Snake is 2 or more boxes connected together in a chain. The above example is a Snake that goes 1-3-9.

Here is a more complex example. Starting at box 4, it follows this order 4-5-6-3-2-8-7.
Code: Select all
 *-----------------------*
 | . . . | . . . | . . . |
 | . . . | X . X | X . X |
 | . . . | . . X | X . . |
 |-------+-------+-------|
 | . X . | . X . | X . X |
 | . X . | . . . | . . X |
 | . X . | . X . | . . . |
 |-------+-------+-------|
 | . . X | X . . | . . . |
 | . . X | . . X | . . . |
 | . . . | . . . | . . . |
 *-----------------------*

Sometime a Snake has a side chain. In the following grid, the snake is boxes 7-8-2-3-6, with box 1 connected to box 2.
Code: Select all
 *-----------------------*
 | . . X | X . . | . X X |
 | . . X | . . X | . X . |
 | . . . | . . X | . X . |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . X X |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | X . . | X . . | . . . |
 | X . . | . . X | . . . |
 *-----------------------*


Loop.

A Loop is as its name suggests; some boxes connected in a circle. They can be 4, 6 or possibly 8 boxes. The following is 4 boxes connected in a Loop: 1-3-6-4.
Code: Select all
 *-----------------------*
 | . X X | . . . | . X . |
 | . . X | . . . | . X X |
 | . . . | . . . | . . . |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | . . X | . . . | . X . |
 | . X . | . . . | . . X |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 *-----------------------*

This is a Loop of 6 boxes connected in a figure 8. 1-2-8-9-6-4.
Code: Select all
 *-----------------------*
 | . X X | . X X | . . . |
 | . . X | . X . | . . . |
 | . . . | . . . | . . . |
 |-------+-------+-------|
 | . X . | . . . | . X . |
 | . X X | . . . | . X X |
 | . . . | . . . | . . . |
 |-------+-------+-------|
 | . . . | . X X | . X X |
 | . . . | . . X | . X . |
 | . . . | . . . | . . . |
 *-----------------------*

Sometime a Loop has a side chain. The Loop is boxes 4-6-9-7, and the side chain is box 1.
Code: Select all
 *-----------------------*
 | X . X | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 |-------+-------+-------|
 | X . . | . . . | X . . |
 | . X . | . . . | . X . |
 | . . . | . . . | . . . |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | . X X | . . . | X . . |
 | . X . | . . . | X X . |
 *-----------------------*


A few of other minor terms I use are:

Stable.

A candidate pattern is stable if no candidate can be eliminated using a logical technique.

Group.

All the boxes that are connected to each other. Any change to 1 group has no effect on any other group. The following has 3 groups.
Code: Select all
 *-----------------------*
 | . X . | . . . | . X . |
 | . X . | . . . | . X . |
 | . . . | . . . | . . . |
 |-------+-------+-------|
 | X . X | . . . | . . . |
 | . . . | . X . | X . X |
 | . . . | . X . | . . X |
 |-------+-------+-------|
 | . . . | . . . | X . X |
 | . . . | . . . | . . . |
 | X . X | . . . | . . . |
 *-----------------------*


Separation.

Sometimes eliminating candidates results in the pattern breaking into 2 or 3 smaller groups.

Now to start using this. First, a simple observation.

In the following grid the cadidates in each box are in opposite corners of a smaller rectangle. I will indicate this with a '\'.
Code: Select all
 *-----------------------*
 | . . . | . . . | . . . |
 | . . . | . X . | . X . |
 | . . . | . . X | . . X |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | . . . | . X . | . X . |
 | . . . | . . X | . . X |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 *-----------------------*

Equally they could all be this way which I will indicate with '/'
Code: Select all
 *-----------------------*
 | . . . | . . . | . . . |
 | . . . | . . X | . . X |
 | . . . | . X . | . X . |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | . . . | . . X | . . X |
 | . . . | . X . | . X . |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 *-----------------------*


I have observed that there must be 4 of '/' (or '\') or 2 of each, as the following grid shows:

Code: Select all
 *-----------------------*
 | . . . | . . . | . . . |
 | . . . | . . X | . X . |
 | . . . | . X . | . . X |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | . . . | . . X | . X . |
 | . . . | . X . | . . X |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 *-----------------------*

The 2 boxes that are the same can be in the same row, column (as above) or opposite each other. This gives me a shortcut when checking candidates.

In the following grid, boxes 1 and 2 have candidates placed '/'. Box 4 is '\'. So box 5 must also be '\'. This means the candidates at r4c6 and r5c5 can be eliminated.
Code: Select all
 *-----------------------*
 | . . X | . . X | . . . |
 | . . . | . . . | . . . |
 | X . . | . X . | . . . |
 |-------+-------+-------|
 | X . . | . X X | . . . |
 | . . X | . X X | . . . |
 | . . . | . . . | . . . |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 *-----------------------*

In the following grid, boxes 2, 4, and 5 are all '\'. Checking box 1, we see that only 1 candidate (r3c3) is possible, that candidate must therefore be true. (Could we call this technique 'Slash and Burn')
Code: Select all
 *-----------------------*
 | . . . | . . . | . . . |
 | . . X | X . . | . . . |
 | . X X | . X . | . . . |
 |-------+-------+-------|
 | . X . | X . . | . . . |
 | . . . | . . . | . . . |
 | . . X | . X . | . . . |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 *-----------------------*


This time the 2 boxes the same (1&5) are opposite each other. So box 2 must match box 4. The true candidate is r3c5.

Code: Select all
 *-----------------------*
 | . X . | . X . | . . . |
 | . . . | . . . | . . . |
 | . . X | . X X | . . . |
 |-------+-------+-------|
 | . . X | . X . | . . . |
 | . X . | . . X | . . . |
 | . . . | . . . | . . . |
 |-------+-------+-------|
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 | . . . | . . . | . . . |
 *-----------------------*

And now for the main reason for this posting - what you have been waiting for.

I have made a couple of observations in line with this discussion. I haven't worked out a proof for them, but have never seen them fail.

Observation 1.

Solving by Colours can only occur in a Loop.

Observation 2.

X-Wings (and Swordfish) can only occur in a Loop.

In line with the first observation, as soon as I see the candidates reduced to a snake, I've stopped using Solving by Colours as a method.

I think that the reason for the first observation is that the effect of 1 colour goes around the loop in 1 direction while the effect of the other colour goes in the opposite direction. In a snake the effect comes to an END. (I tend to only use two colours when Solving by Colours)

I have not seen that many Turbot Fish but they also appear to only occur in a loop.

Because there are a lot of postings I haven't read, I am not sure if something like this has already been posted. Please let me know if it has.

I hope that these patterns help make things a little easier. If you know of others, please post them. If anyone has noticed anything else, I would be interested as well.

Comments welcome.
Condor
 
Posts: 62
Joined: 19 June 2005

Return to General