The New Sudoku Players' Forum

[bennys]

R9C7 = 7 OR R4C8 = 6
But R9C7 = 7 -> R7C8 = 5 -> R4C8 = 6
So R4C8 = 6

[Jeff]

Hi Max,

The chain is correct, but the chain notation is not. Here is the diagram of this chain.


Chain notation should be:
[r5c2]-9-[r4c1]-1-[r2c1]-8-r5c1]=8=[r5c2] enforces r5c2<>9
Notice the bivalue links at r2c1

It would have been easier if the proof was started anywhere other than r5c2 where the enforcement takes place:
r4c1=9 => r5c2<>9
r4c1=1 => r2c1<>1 => r2c1=8 => r5c1<>8 => r5c2=8
Therefore r5c2<>9.

Max, you may like to reconcile this chain with the bilocation/bivalue rules. I am sure things will start falling into place.

[Jeff]

R9C7 = 7 OR R4C8 = 6
But R9C7 = 7 -> R7C8 = 5 -> R4C8 = 6
So R4C8 = 6

Just read your post in another thread and realised that this is not a forcing chain, but the application of unique solution rule combined with a forcing net. For a forcing net, the implication r9c8=2 should be included to imply that r4c8<>2.

[Max Beran]

Hi Max,

The chain is correct, but the chain notation is not. Here is the diagram of this chain.


Chain notation should be:
[r5c2]-9-[r4c1]-1-[r2c1]-8-r5c1]=8=[r5c2] enforces r5c2<>9

How come, Jeff? The "8" link from r2c1 to r5c1 is clearly a strong one (at least in the terminology that we've been applying to the sort of cycles that we drew based on the Eppstein cycles)?

What other differences are there between your "nice" loops and those others? From my own understanding it would appear that you can chain together 2, 4, 6 etc same-label links between bivalue nodes. You can't connect differently-labelled weak links other than at a bivalue node. Anything else?

I'm not suggesting that the logic of the loop here isn't watertight - it patently is. But what I was trying to get at was how to use pattern recognition in the more general case. And that means "rules"; or should I say "Rules rule!"?

[Jeff]

How come, Jeff? The "8" link from r2c1 to r5c1 is clearly a strong one (at least in the terminology that we've been applying to the sort of cycles that we drew based on the Eppstein cycles)?

Max, don't forget a strong link can be used as weak link, but not in reverse.

....From my own understanding it would appear that you can chain together 2, 4, 6 etc same-label links between bivalue nodes. You can't connect differently-labelled weak links other than at a bivalue node.

I think you meant "...chain together 2, 4, 6 etc same-label strong links between bilocation nodes."
What left is how to join a strong and a weak link together. The answer is same label but opposite signs with no restriction on the node in between.

I'm not suggesting that the logic of the loop here isn't watertight - it patently is.....

I can't see where the leakage is.

[rubylips]

Max,

Here are the cycles my solver used to solve the puzzle. The solver attempts to find strong-link only chains (no preference for bivalue over bilocation) first, regardless of their length, in an attempt to replicate human search strategies. I haven't attempted to couch the text in the vocabulary of Eppstein - as far as I'm concerned, it's sufficient to quote the chain and the logic:

Code: Select all

Consider the chain r5c2~9~r4c1~1~r2c1-8-r5c1-8-r5c2.
When the cell r5c2 contains the value 9, it likewise contains the value 8 - a contradiction.
Therefore, the cell r5c2 cannot contain the value 9.
- The move r5c2:=9 has been eliminated.
Consider the chain r8c1-3-r5c1-9-r5c4-2-r8c4.
When the cell r8c4 contains the value 3, some other value must occupy the cell r8c1, which means that the value 2 must occupy the cell r8c4 - a contradiction.
Therefore, the cell r8c4 cannot contain the value 3.
- The move r8c4:=3 has been eliminated.
Consider the chain r4c5-9-r1c5-2-r1c6-2-r5c6~5~r4c5.
When the cell r4c5 contains the value 5, it likewise contains the value 9 - a contradiction.
Therefore, the cell r4c5 cannot contain the value 5.
- The move r4c5:=5 has been eliminated.
The value 5 in Box 6 must lie in Row 4.
- The moves r5c8:=5 and r5c9:=5 have been eliminated.
The value 5 in Box 3 must lie in Column 9.
- The move r2c7:=5 has been eliminated.
Consider the chain r5c1-8-r5c2-8-r1c2-8-r1c6-2-r1c5-2-r1c6-2-r5c6-5-r5c4-9-r3c4-9-r1c5-9-r3c4-9-r5c4-9-r5c1.
The cell r5c1 must contain the value 9 if it doesn't contain the value 8.
Therefore, these two values are the only candidates for the cell r5c1.
- The move r5c1:=3 has been eliminated.
The cell r8c1 is the only candidate for the value 3 in Column 1.


[rubylips]

What I've posted is the literal output from the solver - however, the final chain could have been shortened because r1c5 turns up twice. Back to the debugger ...

[bennys]

Read the subject to my previous post

[Max Beran]

I haven't attempted to couch the text in the vocabulary of Eppstein - as far as I'm concerned, it's sufficient to quote the chain and the logic:

Dear Rubylips (spookily, my granddaughter's name is Ruby too)

Thanks for your input, as they say. I shall certainly study your chains though solving this puzzle wasn't the prime intention of resurrecting this thread.

One thing I've learned from Sudoku in general and this forum in particular is how differently different people's minds work. Me, I'm a top-down sort of a person that prefers the logical "atoms" to be translated into corresponding graphical objects that obey certain successional rules to form long chain "molecules". You're obviously a bottom-up sort of a person who is more at home with those logic atoms. I find it pleasurable and satisfying to chase round a pictorial representation of the bilocation and bivalue cells until I find a pattern that forces a conclusion.

Naively I thought that the three Eppstein patterns of repeating, non-repeating and conflicting pathways exhausted all possibilities of what you can get from this form of presentation so it was a surprise that such a short loop could (a) force a conclusion despite not following those rules, and (b) not be picked up somewhere along the line with one of the simpler operations such as an xy-chain or an xyz-chain.

I now see that those Eppstein rules and cycles are limited as are the possible conclusions. In particular they are not directional as they provide valid successions in both directions. And they all conclude with values forced into cells. These new (to me) pathways differ in that they are strictly directional and they conclude with an exclusion.

[rubylips]

Me, I'm a top-down sort of a person that prefers the logical "atoms" to be translated into corresponding graphical objects that obey certain successional rules to form long chain "molecules".

When I started with Sudoku, I preferred to concentrate on the molecules but I soon found it irritating to have terms such as 'X-Wings' and 'Swordfish' crop up in the solver log as they would mean nothing to a layman fresh to Sudoku, whereas an explicit explanation of the underlying logic would. Moreover, from a computational standpoint, it made little sense to search, say, first for an X-Wings then for a Swordfish when the common components shared by the patterns (single-valued strong and weak links) could be sought simultaneously. As you point out, a further advantage of the atomic approach is that sometimes it reveals a pattern not yet named by the general community. The disadvantage of the explicit listing of the logic is its verbosity.

More interestingly, the solver log makes it clear where the underlying logic relies upon reductio ad absurdum - the dreaded (by some) 'Trial and Error'. I think I'm correct when I say that X-Wing doesn't but XY-Wing does - perhaps the identification and naming of the XY-Wing pattern has obscured this fact from users who would otherwise eschew T&E? Tabling doesn't rely upon reductio ad absurdum - though many would swear that the method is blatant T&E.

The most recent version of the solver, 1.22 beta, has just been uploaded to http://act365.com/sudoku. As the version number suggests, there are some minor bugs still to be addressed, mainly associated with overlong chains. However, the major omission is that the chain-building methodology remains undocumented. I will address this before the next proper release.

[Max Beran]

terms such as 'X-Wings' and 'Swordfish' crop up in the solver log as they would mean nothing to a layman fresh to Sudoku, whereas an explicit explanation of the underlying logic would.

I know it's very non-PC, and I admire others such as em who display such patience, but my first reaction to newbies who ask what these terms mean is one of irritation. Why can't they look them up? There is a reasonable search facility for this board, and there's always Google. It's what I had to do at their stage; why can't they?

from a computational standpoint, it made little sense to search, say, first for an X-Wings then for a Swordfish when the common components shared by the patterns (single-valued strong and weak links) could be sought simultaneously.

It is clear that the innovators are those who are steeped in the basics. I'm like an engineer happy to exploit the efforts of the physicist's labour.

More interestingly, the solver log makes it clear where the underlying logic relies upon reductio ad absurdum - the dreaded (by some) 'Trial and Error'.

You might say "more interestingly" but to me this is a topic that is guaranteed to glaze eyes. I read the threads and admire from afar the capacity of tso and others to make arcane distinctions. My suspicion is that T&E is built into the even more fundamental "quark" level behind the logical atoms and that the touchstone of what feels like fun and what feels like cheating is whether you have to backtrack. I do have a sense for which techniques are "cricket" and which aren't and working the way that your solver does but by hand would not be fun to my way of thinking. When I am searching for loops etc I'm all the time storing away snippets of chain links and my eye and brain are darting ahead trying to anticipate likely pathways. I assume your solver isn't coded to work that way - every pathway is a brand new search exercise and success sooner or later is guaranteed. The point of human heuristics is to recognize patterns and solve sooner rather than later.