A Study in Continuous Loops


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 Previous Entries.

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

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.
 |  |
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. More...
 |  |
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 == More...
 |  |
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 == More...
 |  |
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?
 |  |
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 More...
 |  |
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.
Click Here to join.
You can also try the Chatroom (No one chatting right now - why not start something? )
Check out the Sudoku Blog     Subscribe
Members Get Goodies!
Become a member and get heaps of stuff, including: stand-alone sudoku game, online solving tools, save your times, smilies and more!
Previous Entries

07/Jan/07 Ywing Styles
06/Jan/07 Definitions
31/Dec/06 Y wings
27/Dec/06 Coloring
11/Dec/06 Beginner Tips
Check out all the Daily Horoscopes
Welcome our latest Members
PeeBee from Perth WA
Serban_L from Cluj
Grandmavickie from NJ
Member's Birthdays Today
None Today.
Friends currently online
Want to see when your friends are online? Become a member for free.

Network Sites

Melbourne Bars Find the Hidden Bars of Melbourne
Free Crossword Puzzles Play online or print them out. 2 new crosswords daily.
Jigsaw Puzzles Play online jigsaw puzzles for free, with new pictures everyday
Sliding Puzzle Play online with your own photos
Flickr Sudoku Play sudoku with pictures from Flickr
Kakuro Play Kakuro online!
Wordoku Free Wordoku puzzles everyday.
Purely Facts Test your General Knowledge.
Pumpkin Carving Pattern Free halloween pumpkin carving patterns.