Unsolvable 23 Page 2

Welcome back!

This proof is a total of three pages. Hopefully, you have already digested the First Page.

This page is perhaps the most complex page that I have ever placed onto the blog. None of the steps illustrated below are easy. All of them, however, spring from the general concept of merely appending bivalue/bilocation chains.

A strong link with 7 appended to AIC with 6s appended to Y Wing style with 47

Extended Appendages with 467

There are many ways to view this one. Candidate 7 is proven strong at {def3,i2,f8}, all of which bear down upon f2. In attempt to keep the strong inference sets clear, each is subscripted below. Also, the notation is somewhat Eureka'd.

  • {YWingStyle:(7)def3=1(7-4)c3=2(4)gh3-(4=37)i2}
  • =3(6)i2-{(6):ghi1=4a1-a4
  • =5{XWing at hi4956}}
  • =6(6-7)e9=7(7)f8
    • =>f2≠7
Hopefully, the following triangular matrix clearly illustrates that one can view the appendages in many ways!
def3=7 c3=7
c3=4 gh3=4
i2=7 i2=4 i2=6
ghi1=6 a1=6
i4=6 a4=6 h4=6
i9=6 h9=6 e9=6
f8=7 e9=7

Please note that above we do not have a pigeonhole matrix, as i2=6 forbids in two dimensions

  1. along column i
  2. within box h2
For this reason, I view an elimination such as this one as being more complex than a typical pigeonhole matrix.

For review, with a pigeonhole matrix, each matrix row is a strong inference set, and each matrix column, except the first one, are members of a weak inference set. Merely counting truths proves the first column is a strong set.

With a triangular matrix, the top member of each column, except the first column, is in conflict with each item below it. Each row is still a strong inference set. Some items must be unfilled: Each row i is not filled beyond column i+1. If the item in row 1 column 1 is false, then truths must either cascade down the slope of the triangle or revert back to column 1. Since the triangle ends bluntly, the last row must revert back to column 1 if no other row has already done so.

Typically, one can find an elimination that requires a triangular matrix representation by appending combined almost chains. In this case, the intersection of the almost Y wing style with the 6 almost forbidden by the almost chain on 6s is the key. This intersection occurs at cell i2. If one could resolve this cell, i2, to one fewer canidate, this puzzle would be significantly simpler to solve. Unfortunately, I could not find an efficient way to do so.

Also, there is almost always an alternative coloring chain available, which generally makes almost chains with a single candidate easier to locate. In this case, one could also find:

  • (7)f8=(7-6)e9=(6)hi9-(6)g7={(6):g13=g5-hi4=a4-a1=ghi1}-(6)i2={YWS{(47)i2,(4)cgh3,(7)cdef3}}=>f2≠7
Although this elimination uses one more strong inference set, its existence certainly makes finding the elimination less daunting. Moreover, this alternative can be represented by a pigeonhole matrix, not the more complex reasoning required for a triangular matrix. I am very curious as to whether or not this alternative would be viewed as being more simple.

Below, find the alternative chain represented as a pigeonhole matrix:

def3=7 c3=7
c3=4 gh3=4
i2=7 i2=4 i2=6
ghi1=6 a1=6
a4=6 hi4=6
g13=6 g5=6 g7=6
f8=7 e9=7

I believe such redundancy on single candidate chains to be axiomatic. Similar redundancies abound with all types of chains, and also with all types of almost chains. I think searching for such redundancies is very instructive, as it gives one a feel for where chains must exist. Certainly, it has served that purpose for me. Perhaps someday I will treat the concept of redundancy in the proving of sudoku proofs more formally. However, some redundancies exist only because of uniqueness of solution.

Perhaps I have beat the elimination illustrated above to death. However, I find it to be a very instructive example. The next elimination has been the subject of some discussion at some sudoku forums. I do not find it to be any more complex than the previous one. Nevertheless, it introduces, conceptually, another way to append chains.

Tri-location 7s and 2s chained together with a few appendages

Extended Appendages with 2578

Above, but for the 2 at b6, a chain exists forbidding 5 from f2. Merely appending two strong inferences to the ends of these chains completes the justification for eliminating 8 from a2. The two inferences are: (8)b6=a6 and (5=8)f2. Here is one way to write the chain:not the only one, nor perhaps the best one

  • (8)a6=1(8-2)b6
  • =2{(5=32)e1-(2)e4=4(2)d5-(2)b5=2(2-7)b4
  • =5{(7):e4=5a4-a8=6f8}
  • -(7=75)f5}-(5=88)f2
    • =>a2≠8
To help find such an elimination, I find it helpful to employ GEM-like logic. Basically, any chain snippet that one may find proves something. That something may not lead to an elimination, but it has effectively reduced the set of possible solutions to the puzzle. Simply remember the chain snippets, and perhaps connect some of them later. Fortunately, any information one uncovers is true, and this truth must prevail throughout the puzzle solution. I must credit the idea to Bruno Greco, who introduced it in conjunction to his solution of a tough puzzle at sudoku.com.au in February of 2006.

Moving Strong Sets

This idea, as used below, basically says that one can prove a new set of strong inferences, and then use that knowledge as if the proven strong inferences are actually native strong inferences. As such, it is relatively simple. There are more complex ways to use this concept, but I am not certain that I have successfully unraveled puzzles that require them.

First, one can establish (7)b4=(8)f2 with either a triangular matrix, or the more concise:

  • (7)b4=1{(7):e4=1a4-a8=f8}-(7=5)f5-(5=8)f2
Then one simply applies this proven strong set in either a chain, or the following pigeonhole matrix:
f2=8 f2=5
f2=8 b4=7
a6=8 b6=8

Always, such complex chains can be viewed as accumulated appendages of simple bivalue/bilocation chains. Please note: I am not advocating that one should employ matrices to find chains or eliminations. Instead, the study of the matrix representation of any elimination lets one infer what appendages could have existed without interfering with the validity of the elimination. Then, one can apply that knowledge to see through seemingly complex groups of inferences with greater clarity.

After a2≠8, finally another cell solves: a6 = 8 %column. The puzzle is seemingly only advanced trivially, but in fact, almost all the information for the next elimination has been considered previously! To illustrate this fact, I have broken the next step down into small pieces.

Almost AIC with candidate 7

Almost AIC with candidate 7

Above, three weak links have been added in anticipation of the eventual deduction. One way to write the chain snippet derived above is:

  • (7):i2-i1={{Column XWing at ab14}=e4-f9=e8}-a8
The strong set that is proven is:(7)i1={XWing ab14=e8}

Although it is not my preferred style, without any loss of generality, it has also been proven that:(7):a8-i2. Previously, I would have called this a remote weak link. There is no logical reason not to also store for future use such proven weak inferences.

Note that the 7s in row 4 are used again in a fashion very similar to the previous step. It is difficult to not see this chain snippet once one has found the previous step.

Previous chain snippet with candidates 6 & 7

Previous information

Earlier on this page, we established the information graphed above. I have merely not graphed the Almost Chain on 6s. There is no need for one to find the relationship again, as it must still exist! Putting this together with the previous illustration, but for the 4 at i2, clearly a8≠7. However, something has happened in column a that allows one to easily now connect the dots. This new relationship is clearly indicated by the standard puzzle mark-up that I advocate.

The chain with built upon deductions noted in shorthand

Easy accumulated elimination of 7

Adding to the previous information only the strong cell i2 and two strong by location links in column a, 7 is forbidden from a8. One could write:

  • (3)a8=(3-4)a5=(4)a2-(4)i2
  • =3{{(7):f8=e9-e4=5ab14}
  • =6(7)i1-(7=36)i2-{(6):ghi1=a1-a4=8hi49}
  • =9(6-7)e9=(7)f8}
    • =>(3)a8={(7):f8=a14} => a8≠7
But, one does not have to think it all at once. In fact, one only needs to think as graphed above:
  • (3)a8=(3-4)a5=(4)a2-(4)i2={(~7)a8=(7)i1-(7=6)i2-(7)e9=(7)f8}=>a8≠7
There are of course many equivalent ways to think about this elimination.

Fortunately, after making the elimination graphed above, one can solve column f %cells and i4=5 %box,column & row.

This concludes the second page of this puzzle proof. The hardest and most interesting parts of this proof are finished. What remains is the clean up! The beginning of that process can be viewed on the final page.

Feedback requests

The use of subscripts in an attempt to clarify strong inferences that are partioned and then considered in pieces seems to obfuscate rather than help. If this is your experience in reading this page, kindly let me know. Perhaps also suggest a better alternative! Thanks!

Also, if I am abusing Eureka notation, it is still too new for me. Any pointers on its correct usage would be helpful. Of course, I may well be a hopeless case in this regard!

Indicate which comments you would like to be able to see

gcklzneb tdqwy druz yuvs qulavzxd ilguwnbax nxpgbq
10/Jul/07 4:53 AM
ktldh ovazrh ytqphe ucfasg fxbndtpa tvejs zdtfb http://www.hotbie.gundz.com
10/Jul/07 4:53 AM
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