FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    simple intersection picture of Sudoku          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: Sun Dec 04, 2005 12:16 am    Post subject: simple intersection picture of Sudoku I offer here a simple picture of all basic methods. The picture is one of INTERSECTING sets. The principle behind all these methods is simply that if a candidate is located only in the intersection area of one of two overlapping sets, then it is solely in the intersection area of the other set as well. The statement is this: If a candidate k is possible in area A^B (A intersect B) and not elsewhere in A, then k can be eliminated from any other position in B as well. Code:                                    ---------------                      | A             |                    |               |                  |               |                |        ---------------        |       |     k |       |        |       | A^B   |     k |      |       |      k|   k   |       ---------------        |            |          k    |            |    k          |          |         k   B |          --------------- implies Code:                                    ---------------                      | A             |                    |               |                  |               |                |        ---------------        |       |     k |       |        |       | A^B   |       |      |       |      k|       |       ---------------        |            |               |            |               |          |             B |          --------------- Methods involving more than one candidate simply require more than one A and/or more than one B. Code: method        A          B         candidate singles      row        col            k              col        row            k              block      cell           k locked       block      row            k candidates   block      col            k tuples       row        (col)n        (k)n              col        (row)n        (k)n              block      (cell)n       (k)n X-wing       (row)2     (col)2         k swordfish    (row)3     (col)3         k n-grid       (row)n     (col)n         k uniqueness?  (row)n     (col)n        (k)n --------- 4x4 Sudoku or larger --------- n-locked     (block)n   (row)n         k candidates   (block)n   (col)n         k uniqueness?  (block)n   (row)n        (k)n              (block)n   (col)n        (k)n [edited 12/4/2005 ot add uniqueness -- not sure on this] _________________ Bob Hanson Professor of Chemistry St. Olaf College Northfield, MN http://www.stolaf.edu/people/hansonr Last edited by Bob Hanson on Sun Dec 04, 2005 7:53 am; edited 2 times in total Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Sun Dec 04, 2005 4:23 am    Post subject: wondering, how this translates into exact (cover) speak. trying: Let C1,C2 be sets of columns and R1 a set of rows, if R1/\N(C1)/\N(C2) != {} and R1/\(N(C1)-N(C2))={} and r in N(C2)-N(C1) then r can be removed but R1,C1,C2 must probably have some properties... (hope I can edit and improve this later) Back to top Bob Hanson Joined: 05 Oct 2005 Posts: 187 : Location: St. Olaf College Items Posted: Sun Dec 04, 2005 7:57 am    Post subject: how does this exact-cover speak compare to http://www.setbb.com/phpbb/viewtopic.php?t=480&mforum=sudoku I'm guessing it's about the same thing. Can you translate that into English or point me to a good description of "exact cover"? _________________ Bob Hanson Professor of Chemistry St. Olaf College Northfield, MN http://www.stolaf.edu/people/hansonr Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Sun Dec 04, 2005 9:05 am    Post subject: Bob Hanson wrote: how does this exact-cover speak compare to http://www.setbb.com/phpbb/viewtopic.php?t=480&mforum=sudoku I'm guessing it's about the same thing. Can you translate that into English or point me to a good description of "exact cover"? yes, I downloaded these 12 rules, but didn't yet examine for exact cover see http://magictour.free.fr/suexco.txt (should be updated..) this thread: http://www.setbb.com/phpbb/viewtopic.php?t=395&mforum=sudoku http://www.setbb.com/phpbb/viewtopic.php?t=431&mforum=sudoku and probably other places here also: http://www-cs-faculty.stanford.edu/~knuth/papers/dancing.ps.gz 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