Using Continuous Loops to Solve Sudoku

The following is an illustrated proof for the Tough Sudoku of March 07, 2007. There are many ways to tackle this one. The primary focus of this page is to illustrate using Forbidding Chains, also called Alternating Inference Chains or AIC. This puzzle can extensively use a special type of such chains, that I call wrap around. These are also called continuous nice loops. In such a chain, the endpoints of the chain are in conflict with other, often allowing one to make multiple disparate eliminations.

You may need to refer to previous blog pages to understand this proof. Links to these pages are found to the right, under Sudoku Techniques.

At many times during this illustration, there are other steps available. It is not the goal of this page to show every possible step, but rather to illustrate steps that, taken together, unlock this puzzle

The information on the following blog pages is required to understand this page:

The illustrations of forbidding chains used on this blog page will share the same key:

  • black lines = strong links
  • red lines = weak links
  • candidates crossed out in red = candidates proven false
  • candidate groups will be circled together using black containers

Many steps that are possible will not be shown to keep the page as short as possible. However, every step that is shown can be justified by considering only the previous illustrated steps.

Puzzle at start


PUzzle start

A few Unique Possibilities are available here.

  • f5 = 8% cell
  • d9 = 6% box & row
  • b5 = 6% row
  • c1 = 5% box
  • b2 = 1% column
The puzzle is advanced to 27 cells solved. (UP 27)

Pair 37


Pair 37

Illustrated to the left is the Forbidding Chain representation of Naked Pair 37 at de5. As a Forbidding Chain:

  • d5=3 == d5=7 -- e5=7 == e5=3
  • => gh5≠3 & cg5,d6≠7
In the chain above, since e5=3 and d5=3 conflict with each other, all the weak links are proven strong, justifying all the eliminations.

Hidden Pair 37


Hidden Pair 37

Illustrated to the left is the Forbidding Chain representation of Hidden Pair 37 at d35. As a Forbidding Chain:

  • d3=3 == d5=3 -- d5=7 == d3=7
  • => d3≠15
In the chain above, since d3=3 and d3=7 conflict with each other, all the weak links are proven strong, justifying all the eliminations.

One can of course justify the last eliminations by alternatively finding the naked triple 159 at d689. Also, as noted many times in this blog, even though it is true that d5=3 == d5=7, it is also true that d5=3 -- d5=7. There is never any requirement that weak and strong be mutually exclusive properties.

Why bother with a forbidding chain representation of such simple ideas? Quite simply, all techniques are a subset of Forbidding Chains. Furthermore, understanding that techniques one uses all the time are actually Continuous Nice Loops, or Wrap Around Chains, is helpful in understanding other such Nice Loops.

Current Puzzle


Current Puzzle

The current puzzle state has revealed an Almost Unique Rectangle 37 at de35. One can immediately eliminate 37 from e3. This by itself leads to no cell solutions. Furthermore, once one uses this step, one can no longer prove that the solution one finds is the only solution. I try to avoid using AURs whenever possible. Nevertheless, one may think of the AUR 37 as a clue - e3=37 can likely be eliminated.

There are a few more steps one can take at this point (Some Locked Candidates and a short depth 2 coloring elimination with 5s). Since none of these steps further the puzzle significantly, to save time and space, they are not taken in this proof.

Puzzle Marks


Marked Puzzle

Illustrated above is my normal puzzle mark-up. All bivalue by location candidates are circled black. The underlined candidates are a special type of bivalue strength relative to a house. The black V's point towards cells that will be solved if an underlined candidate does not exist. The red circles are cells of interest due to remote pair-like potential, or because of 3 black circles in one cell.

There seems to be much potential action in the bottom third of the grid. I can assure you, that almost every indicated location to search will yield some sort of fruitful chain. This puzzle, unlike the Monsterously Diabolical Tough Puzzle of February 20, 2007, is easily solved using any of a great number of available Forbidding Chains.

Most of the Chains that I found end up proving that i3=6. One can easily see that if i3=6, the puzzle will have a whole cascade of Unique Possibilities, as then:

  • i4 = 2% column => i4≠35 => some cells will equal 3,5.
  • Also, b4≠2 => b4=8.
to name a few. The primary idea of the puzzle mark-up is twofold:
  1. Identify likely locations for Chains
  2. Identify likely Fruitful Chains - ones that will solve some cells

A Wrap Around or Continuous Nice Loop Chain considering 5 strong sets


Simple Chain

Consdering only 2/9s of the puzzle grid, one can find a very powerful wrap around forbidding chain. Illustrated above, the only thing a bit complex about this chain is the grouped consideration of candidate 9 at h2 versus ef2. Note that the puzzle marks underlined h2=9 with a V pointing towards cell e1=39.

One can start this chain at any strong set considered above. Here is one way:

d3=3 == d3=7 -- e2=7 == i2=7 -- i2=8 == h2=8 -- h2=9 == ef2=9 -- e1=9 == e1=3

Since d3=3 and e1=3 are in conflict with each other, this chain is a wrap around chain. Every weak link above is thus proven strong, giving us 5 new strong sets:

  1. d3=7 == e2=7 => e3≠7
  2. i2=7 == i2=8 => i2≠36
  3. h2=8 == h2=9 => h2≠3
  4. ef2=9 == e1=9 => f1≠9
  5. Chain endpoints: e1=3 == d3=3 => e23≠3
Since i2≠6, i3 = 6% column and box, yielding a cascade of Unique Possibilities to 59 cells filled.

Try a proof by contradiction with any of the forbidden candidates. It will show a contradiction within at least one of the 5 strong sets considered

  1. d3=37
  2. e1=39
  3. ef2,h2=9
  4. hi2=8
  5. ei2=7
The value, though, of understanding the forbidding chain is:
  • One gets all the eliminations listed at once!
Otherwise, one might require seven different proofs by contradiction to get the same result!

An alternate depth 5 continuous nice loop


Alternate Chain

The chain illustrated above is perhaps harder to see. It is very common that if there exists one continuous nice loop forbidding chain, there are other ones availabe using completely different sets, but forbidding some of the same items. This chain could be written as:

{Hidden pair 415 at ef3} ==1 a3=4 -- a3=2 == a1=2 -- a1=6 == f1=6 -- f1=1 == f3=1

Since f3=1 and ef3=Hidden Pair 45 are in conflict with each other, this is again a nice loop chain whereas all the weak links are proven strong:

  1. {Hidden pair 45 at ef3} == f3=1 => f3≠6 and e3≠37
    • Again, the potential AUR eliminations are made by the chain, without using Uniqueness!
  2. a3=2 == a3=4 => a3≠36
  3. a1=2 == a1=6 => a1≠3
  4. f1=6 == f1=1 => f1≠9
Note that some of the same eliminations are made by each of the two chains I choose to illustrate. After making the indicated eliminations, i3 = 6% row, and the cascade of Unique Possibilities occurs again leading to exactly the same puzzle with 59 cells solved.

The 5 strong sets considered by the graphic above are

  1. a3,ef3 = 4
  2. ef3 = 5
  3. a13 = 2
  4. af1 = 6
  5. f13 = 1
Although one may find the last chain illustrated above more difficult to see, I judge them to be about equivalent. The power of using Almost Locked Hidden Sets is quite interesting, and worth the trouble trying to understand.

I suppose it is interesting that both chains solve i3, and that both eliminate e3=37, and that both eliminate f1=9, and that both chains make exactly seven eliminations.

Again, one can do a proof by contradiction, but one can easily miss some of the eliminations by doing so. I highly recommend understanding forbidding chains for precisely this reason.

One of the main reasons that I have chosen using forbidding chains as my vehicle for proving and solving Sudoku Puzzles is precisely these types of chains, which can yield multiple eliminations that seem unrelated.

Puzzle at UP 59


Next stuck point at 59 cells solved

After only Unique Possibilities, the puzzle is advanced to the state shown above. Here we have an interesting configuration, whereas all but one cell, i6, is limited to exactly two possible values. This is called a BUG - meaning BiValue Universal Grave. In a BUG, one uses Uniqueness of Solution to attack the cell with 3 possible values left. It is very rare that using BUG is required to unlock a puzzle. In the case above, BUG implies that cell i6=8, and one can easily decide that by seeing that only 8's are not bilocation in column i, row 6, and box h5.

Instead of using BUG, there are dozens of other manners to attack this puzzle at this stage. There is at least one Y Wing, and many Y Wing Styles. Very common Y wing styles are indicated by the almost remote pair like 58 at i9h6 or 78 at i2g6. Both of these will eliminate one of the values from the cell i6 and solve the puzzle. I will only demonstrate one, as one is all one needs.

Very Common Y Wing Style


Very Common Y wing Style

Consider g69 = 8 as the vertex.

h6 = i9 = 58 as endpoints

Eliminates h8,i6=5.

As a chain:

  • i9=5 == i9=8 -- g9=8 == g6=8 -- h6=8 == h6=5
  • => i6,h8≠5
The puzzle now easily solves.

Find Naked Singles to the end.

Solved Puzzle


Solution

Proof

  1. Start at 22 filled - the given puzzle. Unique Possibilities to 27 filled. (UP 27).
    1. Naked pair 37 at de5 forbids gh5=3, cg5d6=7
    2. Hidden pair 37 at d35 forbids d3=15
    3. i2=8 == h2=8 -- h2=9 == ef2=9 -- e1=9 == e1=3 -- d3=3 == d3=7 -- e2=7 == i2=7
      • forbids i2=36, h2=3, f1=9, e23=3, e3=7. UP 59
  2. very common Y style i9=5 == i9=8 -- g9=8 == g6=8 -- h6=8 == h6=5 forbids i6,h8=5 UP 81
  • Sets: 2 +2 + 5 + 3 = 12
  • Max depth 5 at 2.3
  • Rating: 2(.03) + .31 + .07 = .44
Hopefully, this proof demonstrates well not only the power of forbidding chains, but also the power of understanding them well!

7 Comments
Indicate which comments you would like to be able to see

giblet  From victoria
Hi Steve, your Nice Loop (Alt depth 5) works fine from the pair 45 at e3f3, but what if you start at f1=6, and go clockwise? This would make a3=4 ==e3=4etc and hence eliminate both your 5s from e3f3 which you obviously can't do as then you'd be left with no 5s in that box. Can you legitimately go from a3=4 to e3 =45? Doesn't this make the whole idea of a Nice Loop inconsistent? Cheers.
Steve  From Ohio    Supporting Member
Check out my page
Good question giblet:
Considered the other way around:
f1=6 == a1=6 -- a1=2 == a3=2 -- a3=4 *==* {hidden pair 4*5 at ef3} -- f3=1 == f1=1

f1=1 -- f1=6, so still a continuous nice loop.

I sense, though, that your question is trying to look at a contradiction chain. Nevertheless, all is still well:
a1=6 => a1=2 => hidden pair 45 at ef3 => f1=6 =>
no contradictions in those strong sets.
The real question in a contradiction chain is:

Let f1<>16:
Then a1=6 and f3=6 => e3=5 and a1=1 => no 4's in row 3. That is the point, though, of the continuous nice loop, that f1 must be one of 1,6.
Similar arguments occur at each node, no matter which direction that one goes.

The only caveat when using something like a conditional hidden pair is start inside the hidden pair:

e3=5 == f3=5 -- f3=1 == f1=1 -- f1=6 == a1=6 -- a1=3 == a3=2 -- a3=4 == ef3=4.

Here, it is harder to see that one can also write the last argument as: Hidden pair 45.

For this reason people often call this type of configuration a net, as the bookkeeping can get
troublesome. In order to simplify the bookkeeping, it is generally more transparent to start or end the chain not within the hidden pair, but it is not required that one do so.

Another representation of the same idea:
a1=2 == a3=2 -- a3=4 *==* {Hidden pair 4*5 at ef3} -- f3=1 == f1=1 -- f1=6 == a1=6.
Once again, the endpoints are in conflict with each other, which is the point!

In all of these examples, I use asterisks as I have used the subscripts (subscripts are not available in the comments).
Steve  From Ohio    Supporting Member
Check out my page
Hi Giblet again!
Perhaps you meant counter-clockwise?

a1=6 == f1=6 -- f1=1 == f3=1 -- {ef3=hidden pair 4*5} == a3=4 -- a3=2 == a1=2

Going in this direction, it is perhaps less obvious that f3=1 -- hidden pair...

On could write, although I prefer not to:

a1=6 == f1=6 -- f1=1 == {f3=1 -- f3=5 == e3=5} -- ef3=4 == a3=4 -- a3=2 == a1=2

Here, the contained Boolean requires no subscripts, but is only a chain fragment. Whenever possible,I prefer not to use such fragments. Also, one would have to make some theoretical arguments to justify using such a fragment, which is possible.

I prefer, therefor, to write the chain using the idea which is actually occuring - the conditional hidden pair. Nevertheless, in some more complex chain types, going in the other direction can cause some headaches...

Andrei prefers that such a chain be written with a forbidding matrix, which really makes the whole idea more transparent. Unfortunately, writing such matrices is more difficult in the comment venue. Also, for me, I do not 'think' in matrices.

Matrix:

f1=1 f3=1 0000 0000 0000
0000 f3=5 e3=5 0000 0000
0000 f3=4 e3=4 a3=4 0000
0000 0000 0000 a3=2 a1=2
f1=6 0000 0000 0000 a1=6

Here, each row of the matrix is a native strong set. Each column is a weak set. The matrix has
at least 5 truths. It has no more than 5 truths.
Thus exactly 5 truths. One truth must exist in each row and each column. Thus each column is proven strong. This gives us the same proven strong sets as the chain, and makes the same eliminations.
Steve  From Ohio    Supporting Member
Check out my page
One more comment:
I do not like the form{A -- B == C} because it is not clear, once the larger chain is shown as wrap around, what is actually forbidden in each step.

Going counter clockwise, it may be more transparent to actually write the hidden pair chain as a chain:

a1=6 == f1=6 -- f1=1 == f3=1 -- {f3=5 == e3=5 -- e3=4 *==*f3=4} *==* a3=4 -- a3=2 == a1=2
The bracketed chain is also a wrap around chain, as f3=4 -- f3=5, so it's internal weak links are also proven strong, thus e3=5 == e3=4 is also proven. What is less obvious, perhaps, is that:
f3=1 == f3=45 is proven.
By theory, one can prove this also. Again, the forbidding matrix makes it all more transparent.
Nevertheless, the idea here, for me, is to build on knowledge we already have - so using the Almost Locked Hidden Pair 45 is the way that I think.
Dave  From Vernal, Ut    Supporting Member
Check out my page
I am working through the Blog and am slowly getting to understand the chains etc. When I wish to print the Sudoku to color or markup it is frustrating (to small, harder to see possibilities because the possibilities are not printed like your examples) I assume that you have a diferent program that you use for this purpose. What do you recommend?
Steve  From Ohio    Supporting Member
Check out my page
Hi Dave!
I use Simple Sudoku, available for free download from http://angusj.com/sudoku/

The program has many advantages, including saving
puzzles and puzzle states. My entire archive of puzzle proofs and puzzles is based on that format. Also, one can import/sxport puzzles from some forums using just copy and paste.

Unfortunately, from this site one must manually enter the puzzle. Generally, I print out the puzzle from Sudoku.com.au, then enter it into Siimple Sudoku, then save and work the puzzle. The interface is easier for me to use, and includes many helpful options.

The solving set provided with Simple Sudoku handles most 'easy' techniques, and is also helpful in learning those.
Dave  From Vernal, Ut    Supporting Member
Check out my page
Steve thanks so much
Please Log in to post a comment.

Not a member? Joining is quick and free. As a member you get heaps of benefits.

Join Now Login