Bifurcating Implication Chains == Trebor's Tables

AMcK · Posted: Thu Oct 20, 2005 2:55 pm Post subject:

I'm also quite inspired by Nick70's discovery and am getting similar results having programmed the algorithm in my solver. The reverse "pencilling" is unnecessary because the implication matrix has all the information necessary. Here's the trace for the Nick70's example puzzle which finds r4c1 to be a "magic cell".

Nick70 · Posted: Thu Oct 20, 2005 6:14 pm Post subject:

Lummox JR · Posted: Thu Oct 20, 2005 7:39 pm Post subject:

Of course it's worth adding that those two rules apply only when you have a unit filled with colors. This is the case for methods which apply colors to every placement. Some forms of supercoloring do that; others don't. I think it's helpful to do so if you use these rules, but of course that makes it brutal to solve by hand.

AMcK · Posted: Sat Oct 22, 2005 6:51 pm Post subject:

rkral

On Oct 9

Nick70

rkral · Last edited by rkral on Mon Oct 24, 2005 7:19 pm; edited 2 times in total

Nick70

rkral

Bob Hanson · Posted: Mon Oct 24, 2005 10:47 pm Post subject:

I'm learning a lot reading about your implication chains. Very slick. Basically what Medusa analysis does is carry your "bifurcation" idea to the ultimate -- checking all possibilities at once by grouping strong chains and then linking them. (But you are definitely doing more than I am here.)

About magic cells -- the presence or absence of magic cells simply depends upon the logical capabilities of the solver, I think. Do you agree? So, for example, that 54-magic cell example at
http://www.research.att.com/~gsf/sudoku/

Bob Hanson · Posted: Tue Oct 25, 2005 5:05 am Post subject:

Fascinating! Here is the Medusa chain analysis for your system.

Strong Chains: 9 total, only 3 of interest here:

Chain 3
5 r1c3#3 chain 3(1)
6 r1c6#3 chain 3(0)
7 r3c1#3 chain 3(0)
8 r4c1#3 chain 3(1)
9 r3c5#3 chain 3(1)
10 r5c3#3 chain 3(0)
15 r4c9#3 chain 3(0)
21 r5c7#3 chain 3(1)
22 r7c5#3 chain 3(0)
25 r9c6#3 chain 3(1)
28 r7c9#3 chain 3(1)
29 r9c7#3 chain 3(0)

Chain 5
13 r4c3#1 chain 5(1)
14 r4c5#1 chain 5(0)
18 r5c6#1 chain 5(1)
23 r7c6#1 chain 5(0)

Chain 8
26 r8c7#1 chain 8(1)
27 r9c7#1 chain 8(0)
32 r9c2#1 chain 8(1)

Weak links and corners:

[r5c3#3 chain 3(0)]0--r5c3#1--1[r4c3#1 chain 5(1)] corner
[r4c3#1 chain 5(1)]1--r8c3#1--1[r8c7#1 chain 8(1)] corner
[r9c7#3 chain 3(0)]0--r9c7#6--0[r9c7#1 chain 8(0)] link

Bob Hanson · Posted: Wed Oct 26, 2005 7:57 pm Post subject:

Thanks to all here.

The Sudoku Assistant

http://www.stolaf.edu/people/hansonr/sudoku

now solves 59 of the puzzles on the top95 list.

Provided that the "implication chains" follow simple rules of strong and weak chains, the 3D Medusa analysis takes care of most "bifurcations" -- at least those starting with strong chains. (If chain "X" is in state "0/1"....)

In implementing this I see my logic above was incorrect. I said:

From:

a) [r5c3#3 chain 3(0)]--r5c3#1--[r4c3#1 chain 5(1)] corner
b) [r4c3#1 chain 5(1)]--r8c3#1--[r8c7#1 chain 8(1)] corner
c) [r9c7#3 chain 3(0)]--r9c7#6--[r9c7#1 chain 8(0)] link

We have, assuming +3(0):

+3(0) =(c)=> -8(0) == +8(1) =(b)=> r8c3<>1

and

+3(0) =(a)=> r5c3<>1

and

+3(0) =(a)=> r4c3<>1

But since (a) and (b) are corners, we can't use them in this way.
Hmm... In any case, thanks. I will implement the forward-directed proof provided by Nik70 shortly.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Bob Hanson · Posted: Thu Oct 27, 2005 2:59 pm Post subject:

Nick70's analysis is brilliant! Here is a way of thinking about it without any ifurcation. We use Medusa chains

(http://www.stolaf.edu/people/hansonr/sudoku)

A "the hypothesis that r5c7 is 3"

Medusa: really what this says is that Chain 3, of which r5c7#3 is a +(1) member, must be in state (1). But I'll leave it at just this cell for now:

A: r5c7#3

a "all nodes that, when false, make A true"

Medusa: All 3(0) nodes

a: r1c6#3, r3c1#3, r4c9#3, r5c3#3, r7c5#3, r9c7#3

B "all nodes that, when true, make (a) false"

Medusa: All additional 3(1) nodes and all 3(0)-associated weak nodes

B: r1c3#3, r3c5#3, r4c1#3, r7c9#3, r9c6#3*, and

r1c6#2, r1c6#6, r1c6#7, r1c6#8, r3c1#6, r3c1#9, r4c9#6, r4c9#7, r5c3#1, r5c3#7, r5c3#9, r7c5#1, r7c5#4, r7c5#7, r7c5#8, r9c7#1, r9c7#6, r9c7#8

(*Nick70's table has r9c6#3 eliminated, but that is not crucial to the analysis.)

The essential associated node is r9c7#1, which is a +(0) node of Chain 8 and allows progress to (b)

b "all nodes that, when false, make B true"

Medusa: All 8(1) nodes

b: r8c7#1

C: "All nodes that, when true, make b false"

Medusa: All weak 8(1) nodes:

C: r8c3#1, r8c5#1, r8c7#6, r8c7#7, r8c7#8, r8c7#9

of these, the crucial ones are the first two, r8c3#1 and r8c5#1.

[insert Nick70 brilliant idea here]

c: "All nodes that, when false force A, B, or C"

Look for columns, rows, blocks, and cells for which there are N possibilities and N-1 already assigned A, B, or C. Then the Nth can be assigned c. These include:

r4c3#1 and r4c5#1

Medusa: This is the end! r4c3#1 is chain 5 +(1), and r4c5#1 is chain 5 +(0). Thus, any state of chain 5 forces A, and chain 3 must be +(1).
This instantly sets all the following 3(1) nodes true:

r7c5#3, r1c3#3, r3c5#3, r4c1#3, r7c9#3, r9c6#3

What is interesting, I think, is that this entire analysis can be initiated simply with the question, "Is Chain N +(1)?"

There are only 12 chains in this Sudoku. How long can it take?

I believe this is the missing link that I needed to make the Sudoku Assistant take the next step. Right now it solve 60/95 top95 puzzles, but that is just considering 3D strong chains and their associated weak links and corners. The critical missing pieces for me is the forcing of "false" nodes by (N-1) completion of row/column/block/cell sets.

In this case, the false nodes that are set are r4c3#1 and r4c5#1, with opposite parity. This then forces the final step of the proof.

Alternatively, only one could be recognized. This would force "D" to the other one, and then we would have another untenable situation: all possibilites for #1 in either column 3 or 5 leading to A. Either way, A must be true.

I guess what I don't understand here is where the "bifurcation" comes in. Or, perhaps what I mean is --- using Medusa chains, the bifurcation business drops out. You can just follow the logic directly.

Thanks VERY much for this, Nick70!
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Bob Hanson · Posted: Sun Oct 30, 2005 6:35 am Post subject:

I have implemented Nick70's "reverse logic" in the Sudoku Assistant:

http://www.stolaf.edu/people/hansonr/sudoku

with explanation at

http://www.stolaf.edu/people/hansonr/sudoku/explain.htm

the specific parts of the code relating to this logic can be found in

http://www.stolaf.edu/people/hansonr/sudoku/logic.js

Mind you, Javascript is not particulary speedy. But it is fun to see the logic laid out like this. In particular, the code recognizes a couple of other forcing conditions not mentioned by Nick70:

1. Maybe it's obvious, but single cells are just as valid as rows, columns, and blocks for this logic -- if N-1 of N marks in a cell have been labeled with capitals to indicate "If TRUE, then A is TRUE", then that last remaining mark in that cell can be set "If FALSE, then A is TRUE."

2. A corrolary condition is that if for any subset two marks have been labeled with lower case letters (If FALSE then A is TRUE), then A is TRUE, because at least ONE of those two must be FALSE.

For reference, here is a puzzle from top95 that the Sudoku Assistant required "reverse logic" to solve:

Bob Hanson · Posted: Mon Oct 31, 2005 9:49 pm Post subject:

whoah!

Sure enough, adding Nick70s reverse logic does in fact phenomonally improve the Sudoku Assistant solving of top95. Now it's up to 86/95. The big jump occurred when I allowed it to use reverse logic to answer the question, "Can Node X be eliminated?" where Node X is a weak node that is not itself part of a strong chain. (Strong chain nodes have been taken care of already with the question, "Can Chain N have parity {0 or 1}?")

For reference,

"node" in my parlance is a specific (cell row, column, and candidate value) -- a "mark" on a marked-up Sudoku.

"strong chain" is a linked set of nodes that force each other TRUE/FALSE/TRUE/FALSE....

"weak node", then, is a node that is in the same row, column, block, or cell as a strong node but not itself in that chain. Weak nodes (a) if TRUE set the parity of their associated strong chains, and (b) get set FALSE if their assocated strong chain is set specifically to one of its two possible parities.

see

http://www.stolaf.edu/people/hansonr/sudoku?6.2.5.........4.3..........43...8....1....2........7..5..27...........81...6.....
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr