|
View previous topic :: View next topic |
Author |
Message |
| Bob Hanson
| Joined: 05 Oct 2005 | Posts: 187 | : | Location: St. Olaf College | Items |
|
Posted: Tue Nov 01, 2005 7:24 pm Post subject: |
|
|
Nick70 --
Quote: |
r4c3 and r4c5 are in the same row, so at least one of them has to be <>1. If r4c3<>1, then we still don't know where 1 is, but we know that it must be either in r5c3 or in r8c3. Both possibilities generate a forcing chain that ends in r5c7=3. THe same thing happens if r4c5<>1. In the end, we have proven that r5c7=3.
|
just in case my flurry of messages swamped you, the lesson of the Sudoku Assistant implementation of this is that:
a) It provides the essential technique that application needed to solve all 95 of top95.
b) In order to do this fully, one needs to prove not that a cell IS a value, but that a cell is NOT a value. You lucked out because you chose a node, r5c7#3, that is part of a strong chain, so there is an adjacent node that, in effect, is being proven FALSE.
c) My recent testing indicates that it is unnecessary to check nodes that are members of strong chains. What one needs to do is check nodes that are "weakly linked" to strong chains. It is they, that if proven FALSE, provide the necessary information to solve all of top95.
Thanks again for the excellent observation. _________________ Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr |
|
Back to top |
|
|
| Bob Hanson
| Joined: 05 Oct 2005 | Posts: 187 | : | Location: St. Olaf College | Items |
|
Posted: Mon Nov 14, 2005 9:13 pm Post subject: |
|
|
One final comment on this thread.
First, I want to commend Nick70 for his wonderfully creative way of approaching Sudoku solving. This idea of "bifurcation logic" is amazing.
Second, I'd like to point out that the key {?TT...} --> {FTT...} logic introduced above
a) is equally well represented in a forward sense as looking for hidden singles, {?FF...} --> {TFF...},
b) is only one of an entire set of methods that could be -- and for some Sudoku almost certainly MUST be -- applied in order to arrive at a solution, and
c) simply represents adding depth to a trial-and-error strategy.
OK:
a) This is the same as looking for hidden singles. The proof of this involves two steps. First, everything in the aforementioned discussion COULD have been presented with the capital and small case letters reversed -- starting with "A: r9c7#3 cannot be eliminated" and then following through just like when normally solving a Sudoku: Then the rest of the nodes in r9c7 CAN be eliminated (b instead of B), etc. C becomes "c", "c" becomes "C", and on. Second, that means that the final "key" step involving setting a value false because all the rest in that column are true {?TT...} --> {FTT...} can simply be stated in its "normal" form: {?FF...} --> {TFF...}, which is a hidden single search --- "If only one possible cell for a candidate still exists, then that cell must be that candidate."
b) This is just one of the miriad of possible findings that could be made during this analysis. Since this analysis step amounts to looking for hidden singles, we could postulate that other searches might be equally effective (and even necessary) for arriving at a proof and solving the Sudoku. For example, in the table given above, reproduced here again:
Code: |
1 2467 3467 | 24678 5 23678 | 678 4678 9
5 24679 4679 | 1 2478 26789 | 678 3 467
369 4679 8 | 4679 347 679 | 2 5 1
---------------------+----------------------+---------------------
2389 5 179 | 2789 1278 4 | 679 2679 367
4 179 1379 | 5 6 1279 | 379 279 8
a A
2689 6789 679 | 3 278 2789 | 4 1 5
---------------------+----------------------+---------------------
689 14689 2 | 4678 13478 1678 | 5 46789 3467
689 3 1469 | 24678 12478 5 | 16789 46789 467
7 146 5 | 468 9 368 | 1368 468 2
|
In block 4, since r5c3#3 has been "removed" from play, we have a naked triple involving 179. We can mark "TRUE" (in this reverse "bifurcation" logic") all other 1, 7, and 9 in that block. We could thus proceed, if we wished, to:
Code: |
1 2467 3467 | 24678 5 23678 | 678 4678 9
5 24679 4679 | 1 2478 26789 | 678 3 467
369 4679 8 | 4679 347 679 | 2 5 1
---------------------+----------------------+---------------------
2389 5 179 | 2789 1278 4 | 679 2679 367
B
4 179 1379 | 5 6 1279 | 379 279 8
a A
2689 6789 679 | 3 278 2789 | 4 1 5
B B B BB
---------------------+----------------------+---------------------
689 14689 2 | 4678 13478 1678 | 5 46789 3467
689 3 1469 | 24678 12478 5 | 16789 46789 467
7 146 5 | 468 9 368 | 1368 468 2
|
This could easily be necessary for some imagined Sudoku. It is not easy to see why these Bs can be inserted here. But, in the reverse logic sense, the idea would be something like "r5c3#3 will be forced to be eliminated (and the hypothesis proved) if some one of those nodes "B" is TRUE. This is because if some one of them is true, then that will force the triple, and r5c3#3 will have to be eliminated." It's twisted, for sure, but it must be true (I guess). Again, this is the "reverse bifurcation logic" introduced above. In standard logic, the table would read:
Code: |
1 2467 3467 | 24678 5 23678 | 678 4678 9
5 24679 4679 | 1 2478 26789 | 678 3 467
369 4679 8 | 4679 347 679 | 2 5 1
---------------------+----------------------+---------------------
2389 5 179 | 2789 1278 4 | 679 2679 367
b
4 179 1379 | 5 6 1279 | 379 279 8
B a
2689 6789 679 | 3 278 2789 | 4 1 5
b b b bb
---------------------+----------------------+---------------------
689 14689 2 | 4678 13478 1678 | 5 46789 3467
689 3 1469 | 24678 12478 5 | 16789 46789 467
7 146 5 | 468 9 368 | 1368 468 2
A
|
Here we are starting, actually, with the hypothesis that "r9c7#3 CANNOT be eliminated." The outcome will be that that hypothesis leads to logically inconsistancies, forcing it to be false and that r9c7#3 MUST be eliminated -- the same outcome as that desired in the original posting (because r9c7#3 and r5c7#3 are a strong edge pair, so the hypothesis that "r9c7#3 cannot be eliminated" is identical to the hypothesis that "r5c7#3 CAN be eliminated" (in a forward sense) or (as stated in a reverse sense, "r5c7=3").
In short order now, we can see a 268 triple in block 4, and, if the hypothesis is true, then r6c3=6, r6c2=8, r6c1=2, which leaves r4c1=3, but r5c3=3, so this is impossible. The hypothesis "r9c7#3 cannot be eliminated" is false, so r9c7#3 CAN be eliminated, and r5c7=3.
c) This is precisely the same conclusion using the "bifurcation reverse logic" introduced earlier for this purpose. We are simply "solving the Sudoku with the assumption that r9c7=3" -- that is, we are using trial and error, discovering the error, and throwing out that hypothesis.
Conclusions:
1) There is no particular need for this reverse bifurcation logical analysis. Anything written using it could just as well be written in a normal "forward" direction. The advantage of recasting this all in standard, forward logic is to emphasize that (a) it is no more that standard forward logic stated in opposite terms and that, as such (b) the {?TT...}-->{FTT...} idea originally stated simply represents a forward search for hidden singles, {?FF...}-->{TFF...}, a first small step into a second round of elimination in a depth-search trial-and-error strategy.
2) AS IT TURNS OUT this one little step is all that is required to solve any of top95 or impossible520 or top870. But that success should not be construed as "finding the universal solution to all possible unique Sudoku." In order to do that, one would have to extend this logic either in a reverse or a forward direction into finding block row/column exclusions (locked candidates), subset elimination, grids (X-wings, swordfish, etc.), chain incompatibilities, and, yes, more trial-and-error hypothesizing. _________________ Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr |
|
Back to top |
|
|
| Lummox JR
| Joined: 07 Sep 2005 | Posts: 202 | : | | Items |
|
Posted: Tue Nov 15, 2005 5:29 am Post subject: |
|
|
I think we can actually close the book on finding more complex logical techniques. Because forward or backward this is basically pure trial and error, it's as raw as logic can get--it's just presented in a form that's easier for solvers to understand, and even do by hand. There's likely an army of simpler techniques waiting to be discovered, but this is basically it for the extreme end of logic. |
|
Back to top |
|
|
| rkral
| Joined: 21 Oct 2005 | Posts: 233 | : | | Items |
|
Posted: Sun Dec 04, 2005 1:02 pm Post subject: |
|
|
With the pencilmarking technique described by Nick70 applied to forward implication ...
1) a true (T) propagates a new false (F) for the *same token* at all grid locations in all groups (row, col, and box) of the true, and
2) a false (F) propagates a new true (T) for *any token* at all grid locations in all groups of the false where "?FFFF..." occurs. The unmarked (?) value is a naked single [edit: when the "?FFFF..." is in one cell, a hidden single when not] and is therefore marked true.
Steps 1) and 2) are repeated until a conflict is detected ... or until no new pencilmarks are generated.
If the hypothesis (assumption, trial) that began the pencilmarking iterations leads to a conflict, we know the hypothesis is false. For example, if the assumption of r2c7=7 leads to a conflict then r2c7#7 can be eliminated. Similarly if r2c5<>5 leads to a conflict, r2c5 can be assigned the value 5. If no conflict occurs, neither eliminations nor assignments are possible.
If an elimination or assignment is made, additional iterations may be required to solve the puzzle.
Using 'naked single propagation' per the above and trying all single-valued assumptions for all candidates of all grid cells (whether or not traditional logical techniques are tried first) has solved all known puzzles ... until recently. The exception ... the new kid on the block ... is puzzle #2 of the top1465. Several solvers have been already been modified to reach the solution.
Code: | *-----------*
|7.8|...|3..|
|...|2.1|...|
|5..|...|...|
|---+---+---|
|.4.|...|.26|
|3..|.8.|...|
|...|1..|.9.|
|---+---+---|
|.9.|6..|..4|
|...|.7.|5..|
|...|...|...|
*-----------* |
Without much explanation, I offer the pencilmarked grid below showing Nick70's notation ... albeit in the forward direction ... for a hypothetical implementation that recognizes naked pairs, naked triples, and naked quads ... based on a published solution by bennys. I say "hypothetical" since I haven't implemented this extension. Therefore, the pencilmarking was necessarily done manually and may have an error or three.
Code: |
+-------------------------+-------------------------+-------------------------+
| 7 126 8 | 459 4569 4569 | 3 1456 1259 |
| | i g h | |
| 469 36 3469 | 2 34569 1 | 4679 45678 5789 |
| iiI i | g h | aaAa a a i |
| 5 1236 123469 | 78 3469 78 | 12469 146 129 |
| i | h | bcb |
+-------------------------+-------------------------+-------------------------+
| 189 4 1579 | 3579 59 3579 | 178 2 6 |
| fIh h | h gH h | Jai |
| 3 1267 12679 | 479 8 24679 | 147 1457 157 |
| c iiicI | Ich i ch | Jia bb b |
| 268 25678 2567 | 1 2456 24567 | 478 9 3 |
| i d d e | ig i | a |
+-------------------------+-------------------------+-------------------------+
| 128 9 12357 | 6 125 2358 | 127 1378 4 |
| Fce fc g | fcG c g | bCa f |
| 12468 12368 12346 | 3489 7 23489 | 5 1368 1289 |
| f e ddddE f | ie e | e ce |
| 12468 1235678 1234567 | 34589 12459 234589 | 12679 13678 12789 |
| f i ddd d e f | ig Ggggg g | bc a g gc |
+-------------------------+-------------------------+-------------------------+
r2c7=7 => {r4c7,r5c7,r6c7}={148} => {r5c8,r5c9}={57} => {r1c2,r2c2,r3c2,r5c2}={1236} => r8c2=8 => r7c1=1 => r7c5=5 => r4c5=9 => r4c1=8 => r4c7=1
r2c7=7 => {r4c7,r5c7,r6c7}={148} => {r5c8,r5c9}={57} => {r1c2,r2c2,r3c2,r5c2}={1236} => r8c2=8 => r7c1=1 => r7c5=5 => r4c5=9 => r5c4=4 => r5c7=1 |
The hypothesis r2c7=7 (pencilmark A) produces the conflict of two 1s in column 7 (pencilmark J).
One word of explanation is in order: Identification and location of a naked triple (or pair or quad) causes no true pencilmarks, since we don't know the *exact* location of the values in the triple. For the naked triple {r4c7,r5c7,r6c7}={148}, e.g., there is no 'B' pencilmark on the grid. The marking jumps directly from 'a' to 'b'. Ironically the illustrated conflict is in the cells of that triple.
Last edited by rkral on Sun Dec 04, 2005 8:14 pm; edited 1 time in total |
|
Back to top |
|
|
| Bob Hanson
| Joined: 05 Oct 2005 | Posts: 187 | : | Location: St. Olaf College | Items |
|
Posted: Sun Dec 04, 2005 5:28 pm Post subject: |
|
|
Code: |
+-------------------------+-------------------------+-------------------------+
| 7 126 8 | 459 4569 4569 | 3 1456 1259 |
| | i g h | x xx |
| 469 36 3469 | 2 34569 1 | 4679 45678 5789 |
| ! | g h | b A a a |
| 5 1236 123469 | 78 3469 78 | 12469 146 129 |
| | h | bc |
+-------------------------+-------------------------+-------------------------+
| 189 4 1579 | 3579 59 3579 | 178 2 6 |
| fIh h | h gH h | Jai |
| 3 1267 12679 | 479 8 24679 | 147 1457 157 |
| c c! | Ich i ch | Jia bb b |
| 268 25678 2567 | 1 2456 24567 | 478 9 3 |
| i d e | ig i | a |
+-------------------------+-------------------------+-------------------------+
| 128 9 12357 | 6 125 2358 | 127 1378 4 |
| Fce fc g | fcG c g | bCa f |
| 12468 12368 12346 | 3489 7 23489 | 5 1368 1289 |
| f e ddddE f | ie e | e ce |
| 12468 1235678 1234567 | 34589 12459 234589 | 12679 13678 12789 |
| f i ddd d f | ig ! gh g | b a c |
+-------------------------+-------------------------+-------------------------+
|
Indeed. That is precisely the point. I've found the biggest gain is not so much with subsets, but with locked candidates. So, for example, in your table, reproduced above:
locked 9 in the top row of block 2
locked 5 in the same place
also, you have a few more missed hidden singles:
hidden single 9 in r5c3
hidden single 1 in r9c5
I may not have that totally right. In any case, we could look for just about anything here. X-wings, whatever you want, because what we are doing is starting with a hypothetical state "r2c7=7" and continuing to solve just as we normally would. It's just adding a layer of "depth" to the trial and error tabling. _________________ Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr |
|
Back to top |
|
|
| rkral
| Joined: 21 Oct 2005 | Posts: 233 | : | | Items |
|
Posted: Sun Dec 04, 2005 8:07 pm Post subject: |
|
|
Bob Hanson wrote: | I've found the biggest gain is not so much with subsets, but with locked candidates. So, for example, in your table, reproduced above:
locked 9 in the top row of block 2
locked 5 in the same place |
And locked candidates may be programmatically simpler than naked tuples.
Quote: | also, you have a few more missed hidden singles:
hidden single 9 in r5c3
hidden single 1 in r9c5
|
I was unaware that I missed ALL the hidden singles ... probably because they weren't req'd for that particular puzzle. I'll edit my prior post.
Quote: | I may not have that totally right. In any case, we could look for just about anything here. X-wings, whatever you want, because what we are doing is starting with a hypothetical state "r2c7=7" and continuing to solve just as we normally would. It's just adding a layer of "depth" to the trial and error tabling. |
I guess it's a quasi-depth method, but I understand what you mean. Additionally, since the breadth based T&E has been so successful with just naked and hidden single "patterns", the addition of just a few other patterns might be sufficient for the very tough puzzles. |
|
Back to top |
|
|
|
|
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
|