FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Bifurcating Implication Chains == Trebor's Tables Goto page 1, 2, 3  Next          Sudoku Programmers Forum Index -> Solving sudoku View previous topic :: View next topic   Author Message Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Sun Oct 09, 2005 10:05 pm    Post subject: Bifurcating Implication Chains == Trebor's Tables I have finally found what was missing from implication chains to make them as powerful as Trebor's Tables. The interesting thing is that the new algorithm is just a simple extension of the original Double Implication Chains algorithm I proposed. This means that it remains a 0-lookahead algorithm, which can calculate proofs just from the pencilmarks present on the grid. All the problems I had that my program still needed to make a guess to solve, are now solved by the new algorithm. The new trick is that the implication chains that are built are allowed to bifurcate, provided that all paths terminate in the required proof. Here is an example: 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      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      r4c3<>1 =>    r5c3=1 => r5c3<>3 => r5c7=3    r8c3=1 => r9c2<>1 => r9c7=1 => r9c7<>3 => r5c7=3 r4c5<>1 =>    r7c5=1 => r7c5<>3 => r9c6=3 => r9c7<>3 => r5c7=3    r8c5=1 => r8c7<>1 => r9c7=1 => r9c7<>3 => r5c7=3 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. Let's see how the algorithm works. Pencilmarks have to be marked by the algorithm. To make it easier to read, I will use letters. Uppercase letters will mark possibilities that, when true, imply the thesis we want to prove. Lowercase letters will mark possibilities that, when false, imply the thesis. We want to prove that r5c7=3. Therefore the first step will be to mark that pensilmark with an A: 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 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      The next step is to mark with a the possibilities that, when false, make A true: 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                                                     a Then we mark with B the possibilities that, when true, make a false, and so on with b and with C. Code: 1      2467   3467   | 24678  5      23678  | 678    4678   9                    B                      CbCCC 5      24679  4679   | 1      2478   26789  | 678    3      467    369    4679   8      | 4679   347    679    | 2      5      1      bCC                           C ---------------------+----------------------+--------------------- 2389   5      179    | 2789   1278   4      | 679    2679   367     B                                                          bCC 4      179    1379   | 5      6      1279   | 379    279    8             C      BaBB                            A 2689   6789   679    | 3      278    2789   | 4      1      5      ---------------------+----------------------+--------------------- 689    14689  2      | 4678   13478  1678   | 5      46789  3467         C                      CbCCC                         B 689    3      1469   | 24678  12478  5      | 16789  46789  467                  C               C               bCCCC 7      146    5      | 468    9      368    | 1368   468    2             b                             B        BaBB Now comes the interesting part. We are going to mark pencilmarks with c. Previously, I would have only marked possibilities that, when false, make C true. But this is more restrictive than needed. We can insted mark possibilities that, when false, make SOME possibility marked with an uppercase letter true-regardless of which one. So look at r4c3. If r4c3<>1, then the 1 must be either in r5c3, which is marked with B, or in r8c3, which is marked with C. They are both uppercase, so we can mark r4c3 with c. The same applies to r4c6. Code: 1      2467   3467   | 24678  5      23678  | 678    4678   9                    B                      CbCCC 5      24679  4679   | 1      2478   26789  | 678    3      467    369    4679   8      | 4679   347    679    | 2      5      1      bCC                           C ---------------------+----------------------+--------------------- 2389   5      179    | 2789   1278   4      | 679    2679   367     B            c               c                             bCC 4      179    1379   | 5      6      1279   | 379    279    8             C      BaBB                            A 2689   6789   679    | 3      278    2789   | 4      1      5      ---------------------+----------------------+--------------------- 689    14689  2      | 4678   13478  1678   | 5      46789  3467         C                      CbCCC                         B 689    3      1469   | 24678  12478  5      | 16789  46789  467                  C               C               bCCCC 7      146    5      | 468    9      368    | 1368   468    2             b                             B        BaBB There are several other possibilities that we could mark with c, but r4c3 and r4c6 are all we need, because they are in the same unit, so at least one of them must be false and the thesis is proven. I hope this gives an idea oh how the algorithm works... it's not easy to explain it in every detail. Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Mon Oct 10, 2005 12:12 am    Post subject: Re: Bifurcating Implication Chains == Trebor's Tables Nick70 wrote: I have finally found what was missing from implication chains to make them as powerful as Trebor's Tables. Well done! I had taken a different approach when analysing "toughest" - running the implications in reverse to see what I have to prove - but I'm sure your logic is correct. What bothers me about the approach is that it's lookahead=2 guessing using logic as a surrogate - an extension of the lookahead=1 method in verities and veracities. I have always felt that the iterative closure of exclusions or implications does a +1 logical lookahead each iteration. The 2D implication matrix method can only model that one assertion implies another. It would take a 3D matrix to model the double implications of your example - or as you did - simulation with a copy of the grid, which is dangerously close to logic assisted trial & error. However, it's a good discovery, which I'll try to replicate. Regards Andrew Back to top Lummox JR Joined: 07 Sep 2005 Posts: 202 : Items Posted: Mon Oct 10, 2005 3:10 am    Post subject: I've been playing around with this and using it on this difficult grid: Code: +----------------------+----------------------+----------------------+ | 56     56     .      | 38     .      34     | .      48     .      | | 179    .      .      | .      2457   12     | 245    59     259    | | .      179    17     | 578    2578   128    | 2568   35689  235689 | +----------------------+----------------------+----------------------+ | 1236   12678  47     | 39     2678   .      | 246    16789  12689  | | 256    24568  .      | 278    .      268    | .      45678  258    | | 123567 125678 1357   | .      2678   39     | 2568   156789 125689 | +----------------------+----------------------+----------------------+ | 12579  12579  1357   | 125    2568   268    | 68     368    .      | | 135    15     1345   | 158    4568   .      | .      .      368    | | .      24     .      | 29     .      49     | .      15     15     | +----------------------+----------------------+----------------------+ This is after your algorithm already made several eliminations. When I postulate that (4,1)=3 I hit a dead end, but if I try (4,1)=8, I get this partial result: Code: +----------------------+----------------------+----------------------+ | 56     56     .      | 38     .      34     | .      48     .      | |                      | aA            Bb     |        Ba            | | 179    .      .      | .      2457   12     | 245    59     259    | |                      |         C            | CbC                  | | .      179    17     | 578    2578   128    | 2568   35689  235689 | |                      |                      |    F   FGGGf  FeFEFF | +----------------------+----------------------+----------------------+ | 1236   12678  47     | 39     2678   .      | 246    16789  12689  | | CCbC          cD     | Bb                   |  C         C    E C  | | 256    24568  .      | 278    .      268    | .      45678  258    | |         C            | D G                  |        bCCCC         | | 123567 125678 1357   | .      2678   39     | 2568   156789 125689 | |   C            C     |               bC     |    F        G    E f | +----------------------+----------------------+----------------------+ | 12579  12579  1357   | 125    2568   268    | 68     368    .      | |                F     |  D        F     F    | Ee     eEF           | | 135    15     1345   | 158    4568   .      | .      .      368    | |  C             eD    | GGf    cDDD          |               EdE    | | .      24     .      | 29     .      49     | .      15     15     | |        Dc            | cC            Cc     |                      | +----------------------+----------------------+----------------------+ Here I stopped, because I observed something fascinating. Note where G and A are both in column 4 for the digit 8. The logic of this method states that if one of the G choices is true, the single A choice is true. Therefore if (4,5)=8, then (4,1)=8 as well. This is a contradiction, so (4,5)<>8. What I find very interesting here is that I didn't have to do a try-and-see to eliminate that candidate, nor was it the one I was working on. The working-backwards approach of this technique shows up any contradictions that merely involve the target choice. Back to top Lummox JR Joined: 07 Sep 2005 Posts: 202 : Items Posted: Mon Oct 10, 2005 6:27 am    Post subject: It appears I've been doing this the long way around; I've been trying to find cases that fill up an entire house/digit or cell with true values. One question, though, Nick: If it's only necessary to line up two false values, need they be at the same level? I.e., must they both be c, or could you mix b and c for the same result? Instinct tells me they can mix, but I'd like to be clear. Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Mon Oct 10, 2005 7:02 am    Post subject: Re: Bifurcating Implication Chains == Trebor's Tables AMcK wrote: What bothers me about the approach is that it's lookahead=2 guessing using logic as a surrogate - an extension of the lookahead=1 method in verities and veracities. Could you please give a definition of N-lookahead, because I'm afraid I don't have a grasp of the concept. I was even claiming that the method remains 0-lookahead AMcK wrote: I have always felt that the iterative closure of exclusions or implications does a +1 logical lookahead each iteration. The 2D implication matrix method can only model that one assertion implies another. It is true that supercolouring can be calculated as a whole, while my algorithm needs to work with a definite target. This is a limitation of the algorithm, however, the payback being the ability to select the "simplest" chain of all the ones available. Supercoloring can be extended to do the same kind of logic that I described, but when doing the closure it will need to look again at the grid so it will make it less "pure". E.g. if colors a,b,c are all the colors for a digit in a unit, then you can say that a excludes the intersection of the colors escluded by b and c, and similarly for b and c. AMcK wrote: It would take a 3D matrix to model the double implications of your example - or as you did - simulation with a copy of the grid, which is dangerously close to logic assisted trial & error. I'm not following you here-I'm not running a simulation on a copy of the grid. I merely calculate the implications using the information in the grid, I don't change the pencilmarks. It could be said that calculating implication chains using this algorithm is equivalent to attempting placing a big number and looking for a contradiction, without however updating the pencilmarks. Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Mon Oct 10, 2005 7:31 am    Post subject: Lummox JR wrote: Here I stopped, because I observed something fascinating. Note where G and A are both in column 4 for the digit 8. The logic of this method states that if one of the G choices is true, the single A choice is true. Therefore if (4,5)=8, then (4,1)=8 as well. This is a contradiction, so (4,5)<>8. True. If you had a single forcing chain, then you would be able to split it in half and convert it to a double forcing chain. However you can't do that with bifurcating chains. Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Mon Oct 10, 2005 7:32 am    Post subject: Lummox JR wrote: If it's only necessary to line up two false values, need they be at the same level? I.e., must they both be c, or could you mix b and c for the same result? This cannot happen. If you place b in a unit, at the next step you'll put C in the rest of the unit, so you'll never get b and c at the same time. Back to top Lummox JR Joined: 07 Sep 2005 Posts: 202 : Items Posted: Mon Oct 10, 2005 7:03 pm    Post subject: Nick70 wrote: This cannot happen. If you place b in a unit, at the next step you'll put C in the rest of the unit, so you'll never get b and c at the same time. Yeah, I realized last night that my logic on that was flawed. Guess that's what I get for posting so late. I do like that finding a true value in the same unit (or cell) as A automatically allows you to eliminate it. That's not a bad deal! Going over this algorithm extensively last night, I found that it's actually quite difficult for human solvers. I mean truly, supremely nasty. But doable. The trick is getting the same result twice, because it's so easy to miss something. Back to top Lummox JR Joined: 07 Sep 2005 Posts: 202 : Items Posted: Thu Oct 13, 2005 5:24 am    Post subject: After partially implementing bifurcating chains in my solver, I found it came up with this cherry of a puzzle: Code: . 1 .|. 7 .|. . . . 2 6|. . .|. 5 7 5 . .|. . .|. . 3 ----------------- . . 8|2 . .|. . . . 5 .|. . 4|3 . 2 4 . .|. 3 7|. 8 . ----------------- . . .|. 5 3|4 . . . . 5|. . .|. . 8 . 8 .|. . .|. 9 6 If you alternate between supercoloring and bifurcating chains a few times, it'll finally crack. Presumably there is a magic cell in there that could make it go faster, but my solver operates on a first-clue basis, so it merely finds a few minor eliminations before getting to the meat. My partial implementation as yet only tests cases where you want to prove a placement is true; if you were to place a first and skip A, it might actually be easier to prove something. Right now it can tell me one of three possibilities: 1) A placement with a capital letter touches A, so that placement must be false because it is a contradiction. 2) Two or more false values touch, so the A placement is true. 3) A single constraint is filled with all capital letters, so the A placement is true. 2 and 3 are presented the same way in the output. Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Thu Oct 13, 2005 9:24 am    Post subject: Quote: Presumably there is a magic cell in there that could make it go faster The following cells can perform magic in this sudoku: r6c9, r7c3, r7c8, r8c7. I only checked the cells with 2 candidates. r7c8 & r8c7 are a naked pair. To call it a "magic cell", there should be only one, or can there be multiple magic cells in a sudoku? I'm not sure about the definition. Back to top Lummox JR Joined: 07 Sep 2005 Posts: 202 : Items Posted: Thu Oct 13, 2005 6:23 pm    Post subject: Roughly as I understand it a magic cell is a cell that can crack the puzzle wide open, or at least wider open, yielding a much simpler solution set than others. According to one thread that mentioned this, research using a set of difficult puzzles showed that they all could be cracked easily with no more than 2 cells being assigned the right value at the right time. Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Thu Oct 13, 2005 10:20 pm    Post subject: Lummox JR wrote: Roughly as I understand it a magic cell is a cell that can crack the puzzle wide open, or at least wider open, yielding a much simpler solution set than others. According to one thread that mentioned this, research using a set of difficult puzzles showed that they all could be cracked easily with no more than 2 cells being assigned the right value at the right time. There are two ways to enumerate magic cells: (1) A magic cell set: a minimal set of cells that when solved produces a constrained puzzle (one solved by logic alone.) (2) All of the magic cell sets. http://www.research.att.com/~gsf/sudoku/ has three magic cell examples (the last three images.) In one of them every solution cell (non-clue) is magic. So a 1-constrained puzzle has at least one cell, that when solved, cracks the puzzle. A given 1-constrained puzzle could have n>1 such cells. Also, since that original post I beefed up the constraints used by the solver and now there is only one 2-constrained puzzle out of a survey of ~225M (2 cells must be solved to make it unconstrained.) Back to top Lummox JR Joined: 07 Sep 2005 Posts: 202 : Items Posted: Fri Oct 14, 2005 3:08 am    Post subject: Quote: (1) A magic cell set: a minimal set of cells that when solved produces a constrained puzzle (one solved by logic alone.) Uh, all valid sudoku are solvable by logic alone. Perhaps you mean singles alone? Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Fri Oct 14, 2005 4:28 am    Post subject: Lummox JR wrote: Quote: (1) A magic cell set: a minimal set of cells that when solved produces a constrained puzzle (one solved by logic alone.) Uh, all valid sudoku are solvable by logic alone. Perhaps you mean singles alone? yes, I think he means this. I also classified puzzles by "lookahead-level" required to solve them, which I think is more suitable to classify sudokus than magic cells. I'm not saying magic cells were useless, they are interesting too. Suppose you have a level-x solver. Now make a level-{x+1}-solver from it this way : whenever level-x comes to a furcation, examine all possible forks with level-x. If all or all but one of these forks can be processed with level-x , then consider the remaining fork (if any) as a forced move. Consider the problem as "processed" with level-{x+1}, iff all furcations can be handled this way, i.e. all but one forks can be processed with level-x. In sudoku, usually all furcations are bifurcations. I can't remember any sudoku, where there was no bifurcation and I had to pick a trifurcation or larger. Level-0 is "singles-only". About 50% of minimal sudokus can be processed with level 0. Almost all sudokus can be processed with level-1, I only had 3 which required level-2. This was 2 months. ago, I haven't checked since then. I never had any 9*9 sudoku which couldn't be solved with level-2. edit: OK, I have some more now. I just checked my top94-list and 20 from these 94 were level-2 I forgot to say, that when there are many constraints which can be satisfied in only 2 ways (bifurcations) at some point, then we have to examine them all. If any of these have (at least) one fork which can be processed with level-x (i.e. doesn't lead to another bifurcation) then this one is picked as forced move. This is unambiguous, since when there are two or more "good" bifurcations, then it doesn't matter in which order we pick them. -Guenter. Back to top Lummox JR Joined: 07 Sep 2005 Posts: 202 : Items Posted: Fri Oct 14, 2005 5:57 am    Post subject: I've now implemented bifurcating chains to test two ways. First it tests if a placement is true, then it tests if it's false. This may be slightly redundant, but I'm not sure if that's necessarily the case; looking for falsehoods seems to be about as productive as looking for truths, except you can't find contradiction eliminations. I also decided to optimize my implementation so it tries 2-candidate cells first, then 3, etc. This seems to make it a lot better at finding magic cells. I did however get an idea inspired by the first grid I posted in this thread. The placement (6,7)=2 is a contradiction because it can be shown that it proves (4,1)=8 while simultaneously proving (4,1)<>8. I got to thinking, all I have to do is run the true and the false analyses, and then compare their results. Any placement which has the same truth value for both the true test and the false test is wrong. If that placement had a true value in both cases, you can eliminate it. Otherwise if it had a false value, you can place it! At some point I'll modify my solver to include this technique. I think it will greatly improve the ability of bifurcating chains to quickly find a solution. Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Solving sudoku All times are GMT Goto page 1, 2, 3  Next Page 1 of 3   Jump to: Select a forum Sudoku----------------Solving sudokuSetting sudokuProgramming sudokuThe mathematics of sudokuExotic sudoku Library----------------PuzzlesSoftwareSudoku elsewhere Not sudoku----------------Random thoughtsForum feedback  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