FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Medusa 1: "Crossed Blades" - a new pattern?          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: Tue Nov 08, 2005 1:21 pm    Post subject: Medusa 1: "Crossed Blades" - a new pattern? Now that I have Sudoku Assistant http://www.stolaf.edu/people/hansonr/sudoku running smoothly, I thought it would be interesting to explore some of the implications of mixing strong and weak chains. Here is a theoretical example of a pattern I am simply calling "Medusa 1". I have no specific Sudoku to illustrate this. Please accept it simply as a theoretical idea. I need to introduce a new notation, but I think it's pretty easy. It goes like this: Code: -----------1--------1-------------- This just means "there are only two 1s in some row, column, or block". Thus, this could be a row, but it wouldn't have to be. I'm calling this, for lack of anything better, a "blade." I DO SO HATE esoteric lingo, so if you have a better idea or a more standard term, let me know. and Code: X....(*2) This just means "any 2 that is a weakly connected to X" -- that is, in the same row, column or block as X. Again, not implying row here, but maybe a row, maybe a column, maybe a block. A lot of analyses depend upon seeing cells with only two possibilities. What I'm suggesting is that it isn't so hard to spot and therefore use rows, columns, or blocks with only two occurances of the same candidate. Here's the Medusa idea: Mix the sort of coloring attributable to cells with only two values, 12, with the sort of "X-cycle" analysis usually reserved for single-candidate cycles, like X-wings. Medusa 1 ("crossed blades"?): Code:                   |                   | --------1--------1+----         .         2         .         |3         .         |       (*1)        |         .         |         .         |         1         |          2..(*2)..2                   |                   | This says: We have two "blades" that intersect at a certain cell. Each blade has a second value, and common to both of those OTHER endpoints, we have a cell with only those two possibilities. Then one can eliminate all 1s and 2s that are weak corners as indicated. Why it works: The blades form two strong chains with a weak link: Code:   blade-cell-blade   1----1....2----2 This weak link can transmit only a T-->F, but that is fine. In this analysis, we always start with a FALSE, because our aim is to show that at the other end we have a T for the same candidate. To be useful, we have to be able to put a F in at the OTHER end and come up with a TRUE at the first end. That is, the F--->T must correlate with a T<---F. So here we have: Code:   1----1....2----2   F--->T--->F--->T and   1----1....2----2   T<---F<---T<---F The crossed blades satisfy our two-way street requirement. But the problem is, they don't end with the same candidate. So we add a single weakly linked 12 cell: Code:   blade-cell-blade--w--cell   1----1....2----2....2----1   F--->T--->F--->T--->F--->T and   T<---F<---T<---F<---T<---F There! Now any candidate 1 weakly linked to BOTH ends may be eliminated. That's the (*1) in the diagram above. Same goes for 2. This time we think of the 12 cell as being connected on the left: Code:    cell--w--blade-cell-blade   2----1....1----1....2----2   F--->T--->F--->T--->F--->T and   T<---F<---T<---F<---T<---F Any candidate 2 weakly linked to BOTH ends may be eliminated. That's the (*2) in the diagram above. Useful? Common? I don't have any idea. So that's the theory of it. I suppose you want a real example.... Help? _________________ Bob Hanson Professor of Chemistry St. Olaf College Northfield, MN http://www.stolaf.edu/people/hansonr Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Tue Nov 08, 2005 1:57 pm    Post subject: Code:                   |                   | --------1--------1+----         .         2         .         |3         .         |       (*1)        |         .         |         .         |         1         |          2..(*2)..2                   |                   | When the Left-Bottom cell only has candidates 1 and 2, the Right-Top cell (in the crossing) can only support candidates 1 and 2, because a third candidate would force 1 in Left-Top and 2 in Right-Bottom, leaving no candidates for Left-Bottom. The 3 in your picture is not an option. Doest it exist? You'd have to write some code in your program to recognize the pattern and run it against a large collection like the top870. Back to top Bob Hanson Joined: 05 Oct 2005 Posts: 187 : Location: St. Olaf College Items Posted: Tue Nov 08, 2005 3:32 pm    Post subject: OK, very good! So it is even better: Code:                   |                   | --------1--------1+----         .         2         .         |X         .         |       (*1)        |         .         |         .         |         1         |          2..(*2)..2                   |                   | ...and X can be eliminated as well. Excellent! A lot like an XY-wing, I think. _________________ 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: Tue Nov 08, 2005 5:07 pm    Post subject: Thanks, Ruud. I set Sudoku Assistant so that it doesn't connect strong edges -- only chains of length 2. Interesting, because that makes it more "human". Of course, it can't SOLVE all Sudoku puzzles in this mode, but looky here: 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    |       |       |       ||       |       |       ||       |       |        ----------------------------------------------------------------------------- This is a "crossed blades". We have only two 9s in row 7, only two 8s in column 1, intersecting at r7c1. Our "12" cell is r1c2, {8,9}. The 9s in r1c3 and r2c3 can be eliminated along with the 8 in r1c3. I think I could spot this.... _________________ 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: Tue Nov 08, 2005 5:16 pm    Post subject: no, sorry, not the 8 in r1c3. _________________ 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: Tue Nov 08, 2005 5:30 pm    Post subject: I think actually, this is an example of still another pattern: Crossed Blades II ? Code:                   |                   | --------1--------1+----         .         2         .         |3         .         |         .         |         1         |          2        |           .       |            .      |             (*2)..2                   |                   | This says: We have two "blades" that intersect at a certain cell. Each blade has a second value, and common to ONE of those OTHER endpoints, we have a cell with only those same two possibilities. Then one can eliminate all 2s that are weak corners as indicated. This is actually probably far more frequently found than Crossed Blades I, where it is stated that the "12 cell" is weakly associated with BOTH blades. Here it need only be associated with one, as in the actual example, above. I do think there's more to discover here. _________________ Bob Hanson Professor of Chemistry St. Olaf College Northfield, MN http://www.stolaf.edu/people/hansonr 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 Page 1 of 1   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