FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    simple question -- what would you do?          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: Wed Nov 23, 2005 3:51 pm    Post subject: simple question -- what would you do? 081075009009800500056900800602000480075000020034000705003008000067002108508610200 .81.75..9 ..98..5.. .569..8.. 6.2...48. .75....2. .34...7.5 ..3..8... .67..21.8 5.861.2.. After a few simple locked cells and hidden duples, what would you do next? _________________ 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: Wed Nov 23, 2005 5:54 pm    Post subject: Re: simple question -- what would you do? Bob Hanson wrote: After a few simple locked cells and hidden duples, what would you do next? Eliminate r4c5#9 because r4c5=9 causes a contradiction in row 9 ... and then sit here and wonder, *now* what next? Back to top Carcul Joined: 29 Dec 2005 Posts: 50 : Location: Coimbra, Portugal Items Posted: Thu Dec 29, 2005 11:39 am    Post subject: I have a solution Hi Bob. I guess you have already solved this puzzle, but if not, or if you are interested in a "human" solution, I can post my solution. Regards, Carcul Back to top gaby Joined: 02 Jul 2005 Posts: 120 : Items Posted: Fri Dec 30, 2005 12:42 am    Post subject: My solver cracks it, but only with tabling (highlight text to see full solution). Everything after this is simple pins. # 6 <- [r2,c8] b2 only has 6 in r2 # 6 <- [r2,c9] b2 only has 6 in r2 # 1 <- [r4,c6] b2 only has 1 in c6 # 1 <- [r5,c6] b2 only has 1 in c6 # 1 <- [r6,c6] b2 only has 1 in c6 # 4 <- [r7,c1] Number Pair in b7 {4,9}, in {[r8,c1][r9,c2]} # 4 <- [r7,c2] Number Pair in b7 {4,9}, in {[r8,c1][r9,c2]} # 9 <- [r7,c1] Number Pair in b7 {4,9}, in {[r8,c1][r9,c2]} # 9 <- [r7,c2] Number Pair in b7 {4,9}, in {[r8,c1][r9,c2]} # 9 <- [r4,c5] Nishio won't allow 9 in [r4,c5] # 9 <- [r5,c6] Nishio won't allow 9 in [r5,c6] # 2 <- [r2,c1] Tabling negative verity # 2 <- [r3,c1] Tabling negative verity # 9 <- [r6,c5] Tabling negative verity # 6 <- [r6,c5] Tabling negative verity # 1 <- [r6,c1] Tabling negative veracity # 1 <- [r4,c4] Tabling negative veracity # 3 <- [r1,c4] Tabling negative veracity # 6 <- [r6,c8] Tabling negative veracity # 3 <- [r2,c8] Tabling negative veracity # 3 <- [r2,c9] Tabling negative veracity # 4 <- [r2,c1] Tabling negative veracity # 3 <- [r3,c8] Tabling negative veracity # 3 <- [r3,c9] Tabling negative veracity # 4 <- [r3,c1] Tabling negative veracity # 3 <- [r5,c9] Tabling negative veracity # 6 -> [r6,c6] Tabling positive veracity # 5 <- [r7,c5] Tabling negative veracity # 9 <- [r8,c8] Tabling negative veracity # 4 <- [r9,c8] Tabling negative veracity # 4 <- [r9,c6] Tabling negative veracity # 9 <- [r9,c8] Tabling negative veracity # 3 <- [r9,c9] Tabling negative veracity # 2 <- [r2,c5] Tabling negative veracity # 6 -> [r2,c5] Tabling positive veracity # 1 <- [r2,c9] Tabling negative veracity # 3 -> [r4,c9] Tabling positive veracity # 5 -> [r4,c5] Tabling positive veracity # 3 <- [r1,c1] Tabling negative veracity # 1 <- [r5,c1] Tabling negative veracity # 9 <- [r7,c5] Tabling negative veracity # 3 <- [r1,c8] Tabling negative veracity _________________ Free daily sudoku - Online puzzle database http://vanhegan.net/sudoku/ Back to top rkral Joined: 21 Oct 2005 Posts: 233 : Items Posted: Fri Dec 30, 2005 4:33 am    Post subject: gaby, that white text really sucks! [edit: OK, I see your intent is invisibility ... until we turn on our ultraviolet light. ] Last edited by rkral on Fri Dec 30, 2005 11:01 am; edited 1 time in total Back to top Carcul Joined: 29 Dec 2005 Posts: 50 : Location: Coimbra, Portugal Items Posted: Fri Dec 30, 2005 9:02 am    Post subject: I don't think tabling is required to solve this puzzle: personally, I have used just nine loops. But, I have never used tabling, so I cannot say what technique is "easier" or more straightforward. BTW, can someone give me a brief description of the Tabling technique, or point me to a relevant post? Thanks in advance. Carcul Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Fri Dec 30, 2005 12:03 pm    Post subject: Carcul wrote: BTW, can someone give me a brief description of the Tabling technique, or point me to a relevant post? Tabling was 'invented' in this thread: http://www.setbb.com/phpbb/viewtopic.php?t=126&mforum=sudoku In short: For all candidates in the unassigned cells, make the assertion that: 1. The candidate is placed (true); 2. The candidate is not placed (false); And write all direct implications for those assertions. Then build a tree of all direct+indirect implications for each assertion by linking the direct implications together. Then check the tree for situations where the combined implications have eliminated all but one candidates for a cell, or in a house constraint. Assume the last candidate is true in this situation and expand the tree. More recent addition (not found in this original topic): Check the situation for each assertion. When it contains locked pairs or subsets, expand the tree with the implications of those discoveries. Now check each implication tree to see if it contains inconsistencies (no candidates left for a cell or house constraint, 2 candidates forced in a cell or house constraint) If so, then the assertion must be false, and may be removed. In case the assertion sets a candidate to true, that candidate may be removed. Also, the tables can be searched for assertions that are linked to that assertion (in other words, force it) Those can also be declared false. The tables can also be used in another way. We can compare the implication trees for mutually exclusive sets of assertions, i.e. all candidates in a cell or all candidates in a house constraint). When any implication is forced for each assertion in such a set, we must assume that effect is always true. This is called a verity (and also a veracity, depending on the type of set you are testing) There are more tricky things you can do with tables, but you will read that in the thread I referred you to. Tabling is "structured T&E", very powerful and not implemented in many solvers. I know only of these implementations: - Sudoku Susser by MadOverlord; - My SudoCue solver; - Gaby's online solver; - Bob Hanson's online Sudoku Assistant; - Rubylips' solver. Ruud. _________________ Meet me at sudocue.net Back to top Carcul Joined: 29 Dec 2005 Posts: 50 : Location: Coimbra, Portugal Items Posted: Fri Dec 30, 2005 12:40 pm    Post subject: Thanks Ruud. Regards, Carcul Back to top gaby Joined: 02 Jul 2005 Posts: 120 : Items Posted: Fri Dec 30, 2005 12:52 pm    Post subject: Sorry about that, it worked on the previous version of the BB. I wasn't aware that there were so few solvers that had tabling. I found it one of the easier techniques to implement. Also, when you say you used 9 loops, what kind of loop was it? A forcing chain? A unique loop? Gaby _________________ Free daily sudoku - Online puzzle database http://vanhegan.net/sudoku/ Back to top Carcul Joined: 29 Dec 2005 Posts: 50 : Location: Coimbra, Portugal Items Posted: Fri Dec 30, 2005 10:46 pm    Post subject: Hi Gaby. I use the following loops, but only in manual solving, since I dont solve puzzles with computer progams: simple nice loops (double implication forcing chains) and advanced nice loops (which include generalized strong links, almost locked sets, and multiple implication arguments). See the players forum for more details. Regards, Carcul Back to top tarek Joined: 31 Dec 2005 Posts: 153 : Location: London, UK Items Posted: Sat Dec 31, 2005 12:25 pm    Post subject: As my solver doesn't implement colouring/Tables, the puzzle finally falls to X-Wing (x1), Forcing chains(x4) & Nishio(x3) 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