Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Bifurcating Implication Chains == Trebor's Tables
Goto page Previous  1, 2, 3
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Tue Nov 01, 2005 7:24 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Mon Nov 14, 2005 9:13 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Tue Nov 15, 2005 5:29 am    Post subject: Reply with quote

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
View user's profile Send private message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Sun Dec 04, 2005 1:02 pm    Post subject: Reply with quote

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
View user's profile Send private message
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Sun Dec 04, 2005 5:28 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Sun Dec 04, 2005 8:07 pm    Post subject: Reply with quote

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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Goto page Previous  1, 2, 3
Page 3 of 3

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron