FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Leveraged By-Out -- a new method? Goto page 1, 2  Next          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 Posted: Mon Dec 05, 2005 5:16 pm    Post subject: Leveraged By-Out -- a new method? (pun intended) I think I have a new technique, and I will illustrate it with this example. Please do let me know if this is an established method. Here's the idea: Let's say we've exhausted all our standard techniques. All of these techniques involve simply looking at intersections of cells, rows, columns, and blocks. In this "leveraged by-out" technique, we are going to do something a little different. We will say this: Suppose two cells (of several) A and B might be 9. We propose that one or the other IS 9 and see what turns up. If we can show that this proposition leads to "B is not 9", then we KNOW that B is not 9. We can remove the 9 mark from cell B. Logically we have: Either A or B is 9, or both are not 9. If A or B is 9, then (by this method) B is not 9. Then B is not 9. Another possible outcome is that NEITHER A nor B can be 9. That would be fine as well. It's a simple idea that "leverages" the clout of two cells for the exploration of the elimination of one's possibilities. An Example. Shown below is a configuration from http://www.stolaf.edu/people/hansonr/sudoku .It's what you end up with if you load the "Y-Cycles" example, uncheck "3D Medusa", and then solve. Code:    |---c1--|---c2--|---c3--||---c4--|---c5--|---c6--||---c7--|---c8--|---c9-- ----------------------------------------------------------------------------- r1 |     4 |    89 |  3789 ||     2 |     1 |    58 ||    35 |     6 |    79 ---+-------+-------+-------||-------+-------+-------||-------+-------+------- r2 |    19 |    16 |   369 ||    39 |     7 |    45 ||    45 |     8 |     2 ---+-------+-------+-------||-------+-------+-------||-------+-------+------- r3 |   789 |     5 |     2 ||    39 |     6 |    48 ||   134 |    13 |    79 ===========================||=======================||======================= r4 |     5 |    28 |     1 ||     6 |    38 |     9 ||     7 |    23 |     4 ---+-------+-------+-------||-------+-------+-------||-------+-------+------- r5 |     6 |     7 |    48 ||    14 |    38 |     2 ||    13 |     9 |     5 ---+-------+-------+-------||-------+-------+-------||-------+-------+------- r6 |     3 |    29 |    49 ||    14 |     5 |     7 ||     8 |    12 |     6 ===========================||=======================||======================= r7 |   789 |    16 |   789 ||    78 |     4 |    16 ||     2 |     5 |     3 ---+-------+-------+-------||-------+-------+-------||-------+-------+------- r8 |    17 |     3 |   567 ||    57 |     2 |    16 ||     9 |     4 |     8 ---+-------+-------+-------||-------+-------+-------||-------+-------+------- r9 |     2 |     4 |    58 ||    58 |     9 |     3 ||     6 |     7 |     1 ----------------------------------------------------------------------------- So in this configuration, I claim that neither r1c3 nor r2c3 can be 9. Tell me if you see that as being obvious. The way this implemenation goes is that we look for blocks (could be rows or columns) with both a 2-valued cell (xy) and a three-valued cell (xyz). We are going to leverage that combination in conjunction with some OTHER pair of cells maybe being one of x or y. I don't think leveraging the 2-valued cell or 3-valued cell is critical, but what I found was this works very quickly with them, and so that's an easy place to start. The key is starting with the idea "Either A or B is x" and going from there. In this example, I see an 89 and a 789. I propose "Either r1c3 or r2c3 is 9." The deal with the 2- and 3-valued cells is that they are set by this proposition, and we can eliminate 7, 8, and 9 from all other cells in that block -- mentally. This sets r2c1 to 1. But look! If r2c1 is 1 and r3c1 is 7, what's left for r8c1? Nothing -- the proposition is false; NIETHER r1c3 NOR r2c3 is 9. We can remove those marks. The exact same logic removes 8 from r1c3. Continuing, we have: Code:    |---c1--|---c2--|---c3--||---c4--|---c5--|---c6--||---c7--|---c8--|---c9-- ----------------------------------------------------------------------------- r1 |     4 |    89 |    37 ||     2 |     1 |    58 ||    35 |     6 |    79 ---+-------+-------+-------||-------+-------+-------||-------+-------+------- r2 |    19 |    16 |    36 ||    39 |     7 |    45 ||    45 |     8 |     2 ---+-------+-------+-------||-------+-------+-------||-------+-------+------- r3 |   789 |     5 |     2 ||    39 |     6 |    48 ||   134 |    13 |    79 ===========================||=======================||======================= r4 |     5 |    28 |     1 ||     6 |    38 |     9 ||     7 |    23 |     4 ---+-------+-------+-------||-------+-------+-------||-------+-------+------- r5 |     6 |     7 |    48 ||    14 |    38 |     2 ||    13 |     9 |     5 ---+-------+-------+-------||-------+-------+-------||-------+-------+------- r6 |     3 |    29 |    49 ||    14 |     5 |     7 ||     8 |    12 |     6 ===========================||=======================||======================= r7 |   789 |    16 |   789 ||    78 |     4 |    16 ||     2 |     5 |     3 ---+-------+-------+-------||-------+-------+-------||-------+-------+------- r8 |    17 |     3 |   567 ||    57 |     2 |    16 ||     9 |     4 |     8 ---+-------+-------+-------||-------+-------+-------||-------+-------+------- r9 |     2 |     4 |    58 ||    58 |     9 |     3 ||     6 |     7 |     1 ----------------------------------------------------------------------------- Now we propose that either r2c1 or r3c1 is 9. This one gets a bit messy, but it ends up arguing that r3c1 would have to be 9 -- which doesn't mean r3c1 IS 9, only that then r2c1 is NOT 9. It goes like this: then r1c2 is 8, not 9, r1c9 is 9, r3c9 is 7, r3c1 is not 7, and since it's not 8 either, it must be 9. The puzzle is solved trivially from there. The idea in a nutshell: It is a fact that either A or B is x, or both are not x. Propose that either A or B is x. For speed, choose an x that is part of a 2-valued cell xy in a block that also has a 3-valued cell xyz. Scan quickly for implications. Success is indicated by either a) we discover one of A or B is not x. Then that cell is not x. or b) we discover, even better, that neither A nor B is x. OK, here's another. Note that this one is my "proof" example at http://www.stolaf.edu/people/hansonr/sudoku after solving 3D Medusa only set at "weak", indicating all standard methods except trial and error have been exhausted. Code:    |---c1--|---c2--|---c3--||---c4--|---c5--|---c6--||---c7--|---c8---|---c9--- ------------------------------------------------------------------------------- r1 |    14 |     2 |     3 ||     7 |     5 |     9 ||   148 |    148 |      6 ---+-------+-------+-------||-------+-------+-------||-------+--------+-------- r2 |     8 |     7 |    14 ||     2 |     6 |   134 ||     5 |      9 |    134 ---+-------+-------+-------||-------+-------+-------||-------+--------+-------- r3 |     9 |    56 |    56 ||   138 |   138 |  1348 ||     7 |      2 |    134 ===========================||=======================||========================= r4 |    26 |   156 | 12568 ||  1358 |     4 |   138 ||     9 |      7 |    158 ---+-------+-------+-------||-------+-------+-------||-------+--------+-------- r5 |     3 |   145 |     7 ||   158 |     9 |     6 ||   148 |   1458 |      2 ---+-------+-------+-------||-------+-------+-------||-------+--------+-------- r6 |    14 |  1459 | 14589 ||   158 |     2 |     7 ||    36 |     36 |   1458 ===========================||=======================||========================= r7 |     5 |  1369 |  1269 ||     4 |     7 |   138 || 12368 |   1368 |    189 ---+-------+-------+-------||-------+-------+-------||-------+--------+-------- r8 |    67 | 13469 |  1469 ||    69 |   138 |     2 || 13468 | 134568 | 145789 ---+-------+-------+-------||-------+-------+-------||-------+--------+-------- r9 |   267 |     8 | 12469 ||    69 |    13 |     5 || 12346 |   1346 |   1479 ------------------------------------------------------------------------------- Messy, messy! Yesterday I would have said you had to use trial and error now. But look! The key is the 67 and 267 in the bottom left corner. We leverage the 2 by proposing that one of r7c2 and r7c3 is 6. We mentally set r8c1 to 7 and r9c1 to 2. Mentally erasing 2, 6, and 7 from the other cells in this block, we get a nice naked triple involving 1, 4, and 9 in column 3, cells r2c3, r8c3, and r9c3. That's it! This allows us to remove 1 and 9 from r7c3. We've already removed 2 -- r7c3 would have to be 6!. Not that it IS 6, but that means that r7c2 is certainly NOT 6. I'm not saying this solves this particular extremely difficult puzzle. But, it does advance it. I think the logic is this: "If P or Q, but not both, and (P or Q) implies P, then not Q." and "If P or Q, but not both, and (P or Q) implies not P and not Q, then not P and not Q." I suppose it's just a flavor of trial and error -- but it is focused and seems to be productive. I hope someone tries this and it works for them. _________________ 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: Mon Dec 05, 2005 6:38 pm    Post subject: Re: Leveraged By-Out -- a new method? Bob Hanson wrote: This allows us to remove 1 and 9 from r7c3. We've already removed 2 -- r7c3 would have to be 6!. Not that it IS 6, but that means that r7c2 is certainly NOT 6. This allows us to remove 1 and 9 from r7c3 .... leaving r7c3 without candidates. Your approach on the second puzzle looks much like the set approach by bennys on the Players Forum. Back to top Bob Hanson Joined: 05 Oct 2005 Posts: 187 : Location: St. Olaf College Items Posted: Mon Dec 05, 2005 7:39 pm    Post subject: Not quite. "The key is the 67 and 267 in the bottom left corner. We leverage the 2 by proposing that one of r7c2 and r7c3 is 6." We don't eliminate THAT 6 -- its possibility is built into the proposition. So r7c3 still has 6 as a possibility -- the only possibility. So then r7c2 can't be 6 even if "r7c2 or r7c3 is 6". I'll take a look at that reference, thanks. _________________ 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: Mon Dec 05, 2005 8:16 pm    Post subject: Re: Leveraged By-Out -- a new method? [edit: deleted a "thinking out loud" set theory approach that was flawed] Back to top bennys Joined: 30 Sep 2005 Posts: 6 : Items Posted: Mon Dec 05, 2005 9:41 pm    Post subject: Yes you can use the following rule Code: Almost locked sets xz rule If 1)A,B be almost locked sets. 2)Specific common candidate (lets say x) can appear for A and B only in specific unit (U) Then Any other common candidate (lets say z) cant appear outside of A and B if it can see all the z candidates in both A and B. The reason? If z appear then both A and B are locked but only one can get the x. Its easy to see that its a generalization of the xyz wing rule (that's the reason for the name). in that case A={R2C1,R3C1,R8C1} b={R1C2} x=8 z=9 (you can also switch x and z) We get no 8 or 9 outside A and B in box1 Back to top Bob Hanson Joined: 05 Oct 2005 Posts: 187 : Location: St. Olaf College Items Posted: Mon Dec 05, 2005 11:00 pm    Post subject: If you mean this "Almost locked sets xz rule", I see that. Oooh, that is pretty. This is, in fact, equivalent to "trial and error plus depth through subset elimination." Very nice. If I have this right, bennys's observation is that if you have two "almost locked" sets, A and B, with two common numbers, such 4 and 8 in {48 468} and {46 468} that intersect, then any 4 "buddy" of all of the members of both sets can be eliminated because: a. If that cell is 4, then 4 drops out from both subsets. We would have {8 68} and {6 68}, and b. the intersecting cell, 68, can't be both 6 and 8. For this to work, the intersecting cell has to have the only occurance in each case of a number NOT already accounted for -- in this case 6 in the {48 468} set and 8 in the {46 468} set. I don't have that exactly right, and benny is describing a union, while I'm describing an intersection. But I think an intersection is the right idea here. Other examples bennys gives (* indicates intersection): A {79, 3479, 249*, 3479} B {24, 249*} link is 2/9; knocking out 4 gives: A {79, 379, 29*, 379} B {2, 29*} leaving only the possibility of 2 for A and 9 for B. another, showing that the "intersection" can be via a conjugate pair rather than a single cell: A {35 45 47} B {17 13} link here is a strong 7-7 conjugate pair knocking out 3 gives: A {5 45 47} B {17 1} 7 is forced in both cases, but can't be, because the two 7s are at the end of a strong chain. Definitely very slick. OK, maybe intersection is NOT the right word! But that strong chain could be ANY length, so there's a far greater implication here than alluded to already. Let's see. I have {89, 789*} {17, 19, 789*} Link is 7/8; knock out 9: {8, *} {7, 1, *} and there's nothing left for the intersection. It definitely looks like in this particular case there is a way of writing it this way. What I'm getting at is somewhat different, I think. bennys is still hypothesizing just one cell being TRUE and seeing this as a way to check that out. It's really VERY slick. There should be lots of great applications of bennys's method, some of which fall under the "doubly weakly linked strong chains" idea but some of which are much better than that. bennys does have a great idea here. It shows that one can work with subsets the way one would work with strong chains. --- oh, wait! ---- Write them this way: {79, 3479, 3479,*4}--29--{4*,24} Where I've explicitly written the "hidden" subsets that are linked by the "strong chain" 2--9 The * means "intersecting here" So there are the two subsets, just hidden because there is a 29 in there. knocking out 4 forces: {79, 379, 379, *}--9--{*, 2} and 9 is not allowed in position * by exclusion of the first set. {35, 45, 4*}7--7{*1, 13} knocking out 3 forces: {5, 4, *}7--7{*, 1} but both can't be 7. In my case we have {17, 19, 9*}--78--{9*, 89} [edited a mistake here] OK, now the knockout of 9 gives (sequentially): take out 9 {17, 1, *}--78--{*, 8} forces removal of 8 {17, 1, *}--7--{*, 8} forces removal of 1 and 7 from 17 {_, 1, *}--7--{*, 8} BASICALLY, I think, what bennys is doing is identifying weakly linked subsets the way I would have had weakly linked chains. When two chains are doubly weakly linked, there is a possibility that one of the two weak links can be eliminated. That's pretty much what is going on here. The two subset are like chains that are linked; the proposition adds a weak link that is inconsistent with the already linked subsets. VERY interesting. _________________ Bob Hanson Professor of Chemistry St. Olaf College Northfield, MN http://www.stolaf.edu/people/hansonr Back to top xyzzy Joined: 24 Aug 2005 Posts: 80 : Items Posted: Tue Dec 06, 2005 4:53 am    Post subject: How is this any different than trial and error? In your first example, guess r1c3 is 9, which causes a contradiction. Then guess r2c3 is 9, another contradiction. It's not like you knew ahead of time that 9 would cause a contradiction, it was still a guess. Now if you wanted to say that digits which appear in multiple cells that have few possibilities make good guesses, you would have something. You'd be a little late to coin a phase, as this is a well known heuristic, called MOM's heuristic, for Maximum Occurrences in clauses of Minimum size. Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Tue Dec 06, 2005 6:23 am    Post subject: xyzzy wrote: How is this any different than trial and error? In your first example, guess r1c3 is 9, which causes a contradiction. Then guess r2c3 is 9, another contradiction. It's not like you knew ahead of time that 9 would cause a contradiction, it was still a guess. it's still a complete solver, which apparantly your solver isn't. It finds all solutions or can prove that there is none, while trial and error (how I'd define it) might run forever, yet you don't know whether there is a solution or not. Trial and error might also find the same solution twice Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Tue Dec 06, 2005 7:41 am    Post subject: dukuso wrote: xyzzy wrote: How is this any different than trial and error? In your first example, guess r1c3 is 9, which causes a contradiction. Then guess r2c3 is 9, another contradiction. It's not like you knew ahead of time that 9 would cause a contradiction, it was still a guess. it's still a complete solver, which apparantly your solver isn't. It finds all solutions or can prove that there is none, while trial and error (how I'd define it) might run forever, yet you don't know whether there is a solution or not. Trial and error might also find the same solution twice wikipedia provides a good definition http://en.wikipedia.org/wiki/Trial_and_error the main point is that trial and error is a technique, not an algorithm: there is no implication of completeness or uniqueness -- that is left up to the algorithm that applies trial and error once can certainly code a backtrack tree search that uses trial and error and generates all solutions and each solution exactly once I;m with xyzzy here -- an algorithm that says "plug this value in, but don't commit to it, and see what happens" is trial (plug) and error (it happened to fail) if the trial fails then you can't commit to it and you must unwind to a state before the trial -- just like a backtrack Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Tue Dec 06, 2005 8:18 am    Post subject: but can you make it into an exact "definition" ? Suppose there is a bifurcation and one fork leads to a dead end after one or two ..n forced moves, so you conclude that the other fork is forced. It it still trial and error ? How big must n be, so it's trial and error ? does trial and error come in degrees ? Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Tue Dec 06, 2005 8:55 am    Post subject: Wikipedia wrote: In trial and error, one tries an option to see if it works. If it works, then we have a solution. If it doesn't work - there is an error - then one tries another option. In sudoku, this does not apply. Even if it "works", we may be a long way from a solution. T&E in sudoku is completely focused on the "Error" part. With all forms of T&E, we try to prove something is not true, so we can eliminate candidates. We do this until a single candidate remains, which then can be placed, without further testing. Ruud. _________________ Meet me at sudocue.net Back to top xyzzy Joined: 24 Aug 2005 Posts: 80 : Items Posted: Tue Dec 06, 2005 10:48 am    Post subject: This is just like the Davis-Putnam method invented in the 1960s for solving the satisifiability problem. It's a depth first search with unit propagation after each search node. You will see many people talking about using this method to solve Sudokus on this forum. Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Tue Dec 06, 2005 2:24 pm    Post subject: Ruud wrote: Wikipedia wrote: In trial and error, one tries an option to see if it works. If it works, then we have a solution. If it doesn't work - there is an error - then one tries another option. In sudoku, this does not apply. Even if it "works", we may be a long way from a solution. I can see how "trial and error" generates so much traffic better to concentrate on code than nomencalture ... Back to top Bob Hanson Joined: 05 Oct 2005 Posts: 187 : Location: St. Olaf College Items Posted: Sat Dec 10, 2005 5:18 am    Post subject: Re: Leveraged By-Out -- a new method? I wrote: The example I gave is nicely treated in terms of almost-locked sets. Code:    |---c1--|---c2--|---c3--||---c4--|---c5--|---c6--||---c7--|---c8--|---c9-- ----------------------------------------------------------------------------- r1 |     4 |    89 |  3789 ||     2 |     1 |    58 ||    35 |     6 |    79                Bxx      ** ---+-------+-------+-------||-------+-------+-------||-------+-------+------- r2 |    19 |    16 |   369 ||    39 |     7 |    45 ||    45 |     8 |     2        A x               * ---+-------+-------+-------||-------+-------+-------||-------+-------+------- r3 |   789 |     5 |     2 ||    39 |     6 |    48 ||   134 |    13 |    79       A xx ===========================||=======================||======================= r4 |     5 |    28 |     1 ||     6 |    38 |     9 ||     7 |    23 |     4 ---+-------+-------+-------||-------+-------+-------||-------+-------+------- r5 |     6 |     7 |    48 ||    14 |    38 |     2 ||    13 |     9 |     5 ---+-------+-------+-------||-------+-------+-------||-------+-------+------- r6 |     3 |    29 |    49 ||    14 |     5 |     7 ||     8 |    12 |     6 ===========================||=======================||======================= r7 |   789 |    16 |   789 ||    78 |     4 |    16 ||     2 |     5 |     3 ---+-------+-------+-------||-------+-------+-------||-------+-------+------- r8 |    17 |     3 |   567 ||    57 |     2 |    16 ||     9 |     4 |     8        A ---+-------+-------+-------||-------+-------+-------||-------+-------+------- r9 |     2 |     4 |    58 ||    58 |     9 |     3 ||     6 |     7 |     1 ----------------------------------------------------------------------------- The way this works is that in column 1 there is an almost-locked set A, consisting of three cells and four candidates: {17 789 19} and in block 1 there is an almost-locked set B consisting just of the single cell {89}. Now, these two almost-locked sets are doubly weakly linked by 8 and 9 -- All occurances of 8 in A are buddies of all occurances of 8 in B. The same goes for 9. This means that ANY 8 or 9 anywhere else in block 1 can be eliminated -- my original conclusion, but from a different angle. As for trial and error -- of course this is trial and error. All Sudoku solving is trial and error -- what we call "methods" -- subset elimination, X-Wings, etc., are just shortcuts to expressing that logical trial and error in recognizable "patterns". In chain notation, the situation is: Code:         .8        .  \       8    9       |   .   1---+--9       |       7 Since the two chains are mutually weakly linked, together they are essentially "locked" on 8 and 9, act just like a naked 89 89 pair -- all other 8s an 9s weakly linked to THEM BOTH can be eliminated. Sudoku Assistant, http://www.stolaf.edu/people/hansonr/sudoku is now programmed to find simple almost-locked sets. It also found this one: Code:    |---c1--|---c2--|---c3--||---c4--|---c5--|---c6--||---c7--|---c8--|---c9-- ----------------------------------------------------------------------------- r1 |     4 |    89 |  3789 ||     2 |     1 |    58 ||    35 |     6 |    79                A x    z                         A        A ---+-------+-------+-------||-------+-------+-------||-------+-------+------- r2 |    19 |    16 |   369 ||    39 |     7 |    45 ||    45 |     8 |     2        B x     B      B  x ===========================||=======================||======================= A={89 58 35} B={19 16 369} x=9 (weak link) z=3 (common, can be eliminated)            8 (r1c3)     |    {89 58 35}     3...3--A--5      .     |       3    9       |   .   1---B--9       |    {19 16 369}       6 _________________ 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: Sat Dec 10, 2005 10:25 am    Post subject: Re: Leveraged By-Out -- a new method? Post moved to Players Forum. Off topic: I am seriously considering giving up on setbb.com. The "Solving sudoku" forum is almost dead even though it is frequently agonizingly slow ... and I think this site is the source of many pop-ups that my popup blocker doesn't block. Hmmm! Popups that my blocker does block *may* be part of the reason for the apparent slowness of this site. 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  Next Page 1 of 2   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