Forcing Chains implementation

Ruud · Site Admin

I implemented forcing chains in my solver, but I'm not sure I've covered all situations, so please tell me when I missed something.

1. For each cell with more than 1 candidate, for each of it's candidates, create a Forcing-Chain-Node that contains a list of all eliminations that would occur when that candidate were true. Add to this list the candidates for other cells that are forced to be true, either because one of the 2 candidates is eliminated (naked single), or because it is left as the last vacancy within a house (hidden single). I'm not sure whether this is called a 1-lookahead or a 2-lookahead list.

2. For each Forcing-Chain-Node created in step 1, append to it's effect list all the effects from the candidates it forces to be true. In this step it is possible to detect inconsistencies. When a candidate is set to true and false within an accumulated list, the candidate that owns the list can never be true, and can be eliminated. Two candidates for the same digit within a single house set to true is also an inconsistency.

3. For each cell with more than 1 candidate, compare the accumulated effect lists (created in step 2) of all it's candidates. When an effect appears in all lists, that effect (which could be either an elimination or a forced selection of a candidate) is always true and can be reported.

4. For each unbound digit within each house, compare the accumulated effect lists of all available cells for that digit. This is similar to step 3 and may also reveal "always true" effects.

With this technique added to my solver, I am now able to solve 72 of the Top95.

I could probably up this rate by improving step 2, combining eliminations from various paths, to make new forced selections, but I'm not sure if that would be allowed in 'formal' forcing chains. It would be very difficult to explain to the user. It could be an optional feature for a higher difficulty level.

I would like to know if I made a fundamental mistake, or missed anything, before I put this in my next release.

Thanks, Ruud

gaby · Posted: Sat Oct 29, 2005 8:22 pm Post subject:

What I think you're looking at is more tabling, I was under the impression that forcing chains only followed chains of cells that have two candidates in, although you can start from any cell you like. Also, I find it's better to apply all the negative asssertions of a chain before looking for pinned squares.
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/

xyzzy · Posted: Sat Oct 29, 2005 8:22 pm Post subject:

How is this any different than using the abhorrent "trial and error" with a breadth first search?

I seems to me, that the quest to find "logic" techniques to solve all sudokus is really a quest to find ways to disguise searching so that one can pretend it isn't being used.

Ruud · Site Admin

Bob Hanson · Posted: Sun Oct 30, 2005 7:02 am Post subject:

I would just suggest that if you think in terms of linked strong chains, you can "gang" huge numbers of nodes together without ever having to consider them separately. Surely this is more efficient than going through every single node like that.

The Sudoku Assistant only solves 65/top95, and you are doing better than that, so I defer to your technique here. But consider that strong chains with weakly associated nodes greatly simplifies the analysis. When any one node of a strong chain is set TRUE, all are set. I suspect the top95 ones that you are solving that I'm not are due to my not testing EVERY node, just EVERY chain.

As for is this anything more than trial and error, or is this looking ahead, I really don't see how any of this is different from simple crosschecking. "A 3 must go here because if it didn't, it would have to go THERE, and then there would be two 3s in this column" is little different from "A 3 must go here because otherwise there would be a conflict over there." That's all forcing chains are doing, I think. And the reverse logic that Nick70 introduced, that equates to "multifurcating" is trickier, but still of the same nature -- "A 3 MUST go here because no matter what you put over HERE, that is the result you will get." The fact that this can be done "backward" in one straight, logical stream with simplel human marking and without the "bifurcation" seems proof enough to me that it is simple, direct logic.

No?

The Medusa chain analysis I'm using [/quote]
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Ruud · Site Admin

I've spent some time on the Sudoku Players forum, and found lots of heated discussions on "pure logic" vs "guessing" vs "Trial & Error". Interestingly, Lummox JR made one of the best remarks there.

My free interpretation of it:

T&E is logic, because you use it to prove something. A guess is no more than just that. If you're lucky, it helps you on your way, but to call it logic, you must prove that the alternatives for that choice are not valid.

Encouraged by this, I have improved the merging routine, so all the cascading effects of an assumed candidate are taken into account.

The result: Now solving 90 of the Top95. Very Happy

I'm currently manually checking these last 5 puzzles to see what makes them so special.

Ruud

Ruud · Site Admin

Short update:

Changed the way to find verities. Improved both score and performance.

The new score: 92 of the Top95 solved without backtracking.

Found out that puzzle #60 in Top95 is the famous "Toughest Known" in a slightly different minimal form, the other 2 toughies are #9 and #69.

A point of interest: #7 was in the list of 5, but now breaks with the improved verity search. The difference between #7 and #9 is a single pair of clues:

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

funny you should mention that about "toughest known"

6.2.5.........4.3..........43...8....1....2........7..5..27...........81...6.....

I've been hoping this would fall for a couple of days now.

Adding full chain/node reverse logic to Sudoku Assistant just took care of this one! Gosh, that's a powerful technique! Thank you Nick70!!!

http://www.stolaf.edu/people/hansonr/sudoku/?6.2.5.........4.3..........43...8....1....2........7..5..27...........81...6.....

But, yes, this one is REALLY involved. Here are some highlights (in reverse solving order). Several of these are simple forcing chain issues, but some are more interesting.

Detail
Done! (35 steps)
OK! 682 153 479 951 764 832 374 892 165 437 528 916 816 947 253 295 316 748 568 271 394 729 435 681 143 689 527

Step 19 Strong Chains: 21
36 weak links
178 weak corners
r6c2 ISN'T 6: would leave no 7 in column 2 if Chain 6 has +(1) parity

(just forcing chains)

Step 17 Strong Chains: 21
39 weak links
164 weak corners
r2c7 ISN'T 6: would leave no 7 in column 2 if Chain 6 has +(0) parity
r3c5 ISN'T 6: would leave no 7 in column 2 if Chain 6 has +(0) parity

(more forcing chains)

Step 16 Strong Chains: 21
40 weak links
169 weak corners
r3c8 ISN'T 9: weak 0/0 corner between linked 1/1 strong chains 9 and 18

(a bit trickier, but still just a forcing issue)

Step 15 Strong Chains: 19
19 weak links
137 weak corners
r8c2 ISN'T 6: Reverse logic test: Node r8c2#6 must be FALSE

(OK! that step required the latest addition -- reverse logic applied to weak nodes)

Step 14 Strong Chains: 19
19 weak links
133 weak corners
r8c1 ISN'T 9: Reverse logic test: Node r8c1#9 must be FALSE

(here again)

Step 13 Strong Chains: 19
19 weak links
128 weak corners
r8c1 ISN'T 3: Reverse logic test: Node r8c1#3 must be FALSE

(and again!)

Step 12 Strong Chains: 19
19 weak links
131 weak corners
r3c3 ISN'T 7: weak 0/1 corner between linked 1/0 strong chains 8 and 9

(just another forcing chain)

Wow!!!
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Bob Hanson · Posted: Mon Oct 31, 2005 10:13 pm Post subject:

Ruud, I think you and I are quickly converging on a common solution to top95.

Ruud · Site Admin

Bob Hanson · Posted: Mon Oct 31, 2005 11:28 pm Post subject:

Guess what? I just stumbled on a bug in the weak-link code for Sudoku Assistant. When fixed, It's solving 9 of top95. Here's my "can't solve" list:

14.5....28..49..3..76.21....146..3..6....9..7.....36....1..4.5.46......3..71..2..

53..2.9...24.3..5...9...3.2....1.827...7...9.....981............564....9172.5.43.

..7..8.....6.2.3...3......9.1..5..6.....1.....7.9..1.27.......4.83..4...264...51.

5....9.4.9.2..45.1.7..5..9..83.97....4..6....69.1..8..32....1..85.9...6.....8..53

92.3....8..64.8.9.83.5........2...8.7.9..5.....2..6..4..8....1...1...4.22..7..8.9

Top95#60 is NOT among them, by the way. If what you mean by that is

... ... 94.
... .9. ..5
3.. ..5 .7.
.8. 4.. 1..
463 ... ...
... ..7 .8.
8.. 7.. ...
7.. ... .28
.5. 26. ...

more later....
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Ruud · Site Admin

Well Bob,
if we would be able to converge, we would solve the whole bunch. My 3 (even the former 5) unsolvables have no puzzle in common with yours.

To speed thing up a little, I've added to my tabling routine a check for "Magic Cells". When all cells are forced to a single digit in a node's implication tree, and we know that the puzzle has a single solution, the solver simply selects this candidate and leaves it to the basic functions (singles) to complete it.

This is what my solver does with your last 5:

Bob Hanson · Posted: Tue Nov 01, 2005 4:55 am Post subject:

Fascinating!

Well, I'm coming up to speed here fairly quickly, but I'm not quite there with all the lingo.

I'm delighted if Nick's strategy solves the "toughest known". Is that right? This one?

... ... 94.
... .9. ..5
3.. ..5 .7.
.8. 4.. 1..
463 ... ...
... ..7 .8.
8.. 7.. ...
7.. ... .28
.5. 26. ...

I have a hunch that the forward and reverse logic techniques are ALMOST but not QUITE the same. I had to ammend Nick's technique to be a bit more general in the reverse sense, and then I think I see how to solve his presented puzzle in a forward sense, but I'm out of energy now to implement a forward strategy in Sudoku Assistant. Maybe next week....

But here's the gist of it:

1) The reason the reverse technique is working is that it transends what people usually consider in terms of "forcing". Thus, instead of just considering that a node has to be true or not (BE or NOT BE eliminated), Nick considers the implications of "almost completed sets". This I think is the key, because in a reverse sense, what you do is suggest that a node is FALSE, and work back the implications via:

1. A will be TRUE if any of (a) are FALSE (strong chains here)
2. (a) will be FALSE if any one of B were to be TRUE (strong chains + weakly associated nodes)
3. B would be TRUE if any one of (b) were FALSE (strong chains again)
4. (b) would be FALSE if .....

BUT you can only go so far with that. The real breakthrough was in his seeing that there is an alternative method of (2). That is:

5. (a) will be FALSE in the case where there are N possibilities, and N-1 are already of the "If TRUE, then A is true" variety (from 3). In that special -- but not so rare with top95 -- case, we have:

[ ? A B C D ... ]

Here we can say that "A will be true (that is, ONE OF A, B, C, or D will be TRUE) iff ? is FALSE. So we assign FALSE to that node and continue. It's SO clever!

In addition, I submit that if we have:

[ a b .........]

then A is TRUE as well, because two values in a set cannot BOTH be "not false".

OK, so I SUSPECT that the same can be implemented in a forward fashion, and that is why you, too, are coming so close. I'll bet forward is NOT the same as backward, but the strategies are extremely similar:

1. If a is FALSE then all of B are TRUE (strong chains here)
2. If B is TRUE then all of b are FALSE (strong chains + weakly associated nodes)
3. b is FALSE then all of (C) are TRUE (strong chains again)
4. If (C) is TRUE...

AND

5. (A) will be TRUE in the case where there are N possibilities, and N-1 are already of the "if A is true, then this will be FALSE" variety (from 2). We have:

[ ? a b c d ... ]

Here we can say that "if A is true, then all of a, b, c, and d will be FALSE, and therefor ? will be TRUE.

This starts another cycle at step 2.

I'm supposing that you are doing this latter strategy and I the former, thus not quite solving the same set.

Is that possible?

Also, I guess I still don't get what a Magic cell is. What do you mean by

"knock-out by a Magic Cell r2c9 value 5"?

Sudoku Assistant isn't doing anything about Magic Cells, I don't think. It just solves the puzzles.

1) How does your solver identify a magic cell?

2) What does it then do with that information?

3) Doesn't the solver have to have the solution to "know" that a cell is a magic cell?

Thanks. This is getting very interesting, I think.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Ruud · Site Admin

Regarding your questions about Magic Cells:

The forward logic in my tabling function considers all effects of each candidate in the unbound cells. This is done by simply checking the 4 constraints of the puzzle (1 digit per cell, alldifferent in each row, column and box).

When the implication tree of a particular cell+digit causes all remaining cells to be bound to a single digit (with no inconsistencies), placing this digit will automatically lead to a valid solution, without the need to revisit any of the advanced techniques, like subsets, coloring, tabling, or Medusa.

The implication trees are normally used to detect inconsistencies or verities as I explained earlier. However, since I have them now, I can also check which implication trees would completely solve the puzzle.

The term Magic Cell is not completely correct. It is not the cell that is doing the magic, but the placement of a particular candidate. It could be that others use the term Magic Cell for a cell that, no matter which candidate you choose, always solves the puzzle. But a cell that performs magic with a single candidate is good enough for me.

I use the Magic Cell simply as a shortcut. In some very complex puzzles, the solver has to revisit the tables again and again, eliminating one candidate at a time, until it finally breaks. When you are able to find a Magic Cell, you have a One-Hit-KO for the puzzle. I've checked the puzzles that were solved with Magic Cells, and each of them could also be solved with detection of inconsistencies and verities.

The solver does not have to "know" the solution in order to find a Magic Cell. The only restriction, same as with uniqueness tests, is that it assumes that the puzzle has only one solution.

If you find a solution, and you know there is only one solution, you have found the solution.

Congratulations on solving all 95. I'm still at 92... Have you tried the list of 795 fiendish 17-clue puzzles that Mark posted yet? I was able to solve all of them, so I guess you must be able to turn that list into mincemeat.

Ruud.

Bob Hanson · Posted: Tue Nov 01, 2005 9:11 pm Post subject:

Thanks, Ruud.

I have now confirmed that the Medusa+reverse logic ALONE solves all top95 puzzles. That is, no block-exclusion analysis, no n-tuples, no X-wings, grids, just strong chains and weak links.

This surprises me, and I don't really believe it is general. But it does show that block row/col exclusion, subset elimination, x-wings, and such are all pretty much the same thing.

But there could definitely be a puzzle with no strong chains, in which case I would argue this is THE most difficult puzzle -- no duplets anywhere, no rows, columns, or blocks with only two occurances of any candidate. Were this puzzle to be found, Medusa alone would not work. (Although maybe just relaxation of the restriction that only weak nodes be investigated would do the job, but I doubt it.)

I think it's safe to say that your logical implication chains are identical to Medusa. Thus, an "effect" amounts to identifying the strong chans and weak associated chains. You just aren't classifying them as such.

I had been making a mistake with what I was calling "forcing corners" that was actually producing unsolvable situations. That gone, all fell in line.

So I'm hoping that you can get all 95 to crack with forward-directed logic. I'm pretty sure both forward and reverse are the same thing, just seen from two different perspectives. Well, OK, not exactly the same thing, but I mean, covering the same bases. The key for you, if that is true, is to identify:

a) all cases where options for a candidate have been eliminated
[F F F F F...]

b) all cases where all except ONE option for a candidate has been eliminated
[? F F F F ...]

c) all cases for which two candidate possibilities are forced:
[T T ? ? ...]

Of course, I'm sure that is exactly what you are doing. So why those last three? The only other thing I can think of is if the forward also needs to check somehow for block row/cell exclusion. But the reverse doesn't seem to need to do that, so maybe that just falls out of the analysis.

You shouldn't have to check for whether a candidate is ELIMINATED, only if that candidate is TRUE. Right? Or do you have to check both possibilties? The reverse method only has to check for ELIMINATION, it turns out.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr