FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Top95: Our common benchmark? Goto page Previous  1, 2, 3, 4  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: Thu Nov 03, 2005 2:24 pm    Post subject: By the way, the "uniqueness" idea is covered trivially by Medusa, if I have this right: You are trying to show that, for example, 12 ...... 21 21 ...... 12 .... X arises IF certain node X (1 or 2) is eliminated. Is that right? I don't think any #1 or #2 node weakly assoicated with any part of this will allow it to stand. The presence of the weak node with cause one or more of the links in the chain to be eliminated. Can you show another example where uniqueness somehow helped? I guess a full 3x3 with ALL THREE values at ALL THREE places would be a different story. I doubt there can be many of these, though. _________________ 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: Thu Nov 03, 2005 7:46 pm    Post subject: I've just started to delve into this subject, but the basic concept is this: When you encounter this candidate pattern Code: 12....12  .    .  .    . 12....12 within a 9x3 or 3x9 section of the puzzle, you're in trouble. This pattern has 2 solutions: Code: 1....2       2....1 .    .       .    . .    .  and  .    . 2....1       1....2 Any of these 2 rectangles can only exist if at least one of the 4 digits is a clue, otherwise they would be interchangable, giving the puzzle 2 solutions. When you can safely assume that the puzzle has only one solution, either as a guarantee by the maker, or by testing it with a backtracking solver, then this pattern (now named "the Deadly Pattern") will never be formed when you solve a puzzle (unless you make a mistake). Please notice that this pattern would not be rejected by normal solving methods, because they do not contain an inconsistency by themselves. All uniqueness tests (4 different ones) are aimed at avoiding this pattern. The surplus digits (now named the quantum) determine which test can be applied. Check this forum for more info on how to do the 4 tests. I've placed a couple of good links in the SOLVING TECHNIQUES INDEX I posted earlier. These uniqueness tests are very interesting because they have a different premise than most other techniques. This gives it a unique working area, overlapping only the most thorough of them. Ruud. Back to top Bob Hanson Joined: 05 Oct 2005 Posts: 187 : Location: St. Olaf College Items Posted: Thu Nov 03, 2005 7:51 pm    Post subject: Can you post an example or two that are at the stage where the uniqueness test doest the trick? I'd like to compare what other methods do at that particular juncture. _________________ 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: Thu Nov 03, 2005 8:17 pm    Post subject: I' like to pass this request to Lummox JR Back to top Bob Hanson Joined: 05 Oct 2005 Posts: 187 : Location: St. Olaf College Items Posted: Fri Nov 04, 2005 12:02 am    Post subject: I had another thought on this. Quote: Please notice that this pattern would not be rejected by normal solving methods, because they do not contain an inconsistency by themselves. Ah, but this pattern is not going to arise by itself, de novo, I think. It constitutes a 3D "prism" outline of all strong edges. Before it arises there will almost certainly be other nodes with 1s or 2s that would be "weakly associated" with this structure, causing one or more of its edges to not be strong and, I propose, knock out an edge node before the prism ever arises. So then my question is, won't OTHER factors force these "proto-uniqueness" states to go to a unique solution (provided the puzzle has one). Uniqueness tests assume uniqueness, so with that premise, I propose, other constraints will force a good solver to NOT achieve one of these conditions. So, for example, say you had: 12....12 12....12.....1 A "uniqueness test" could tell us that that last 1 HAS to be valid. But a simple forward logic weak edge test will do the opposite: We have a strong chain: Code: (bottom left) 1--1--2--2--1--1 (bottom right)   parities:   0  1  0  1  0  1 The two ends are opposite parity. (When one is TRUE, the other is FALSE.) So there you have it-- the last 1 is disallowed immediately, and the test leads to nonuniqueness, which simply cannot be the case for a unique puzzle. The logic isn't going to lead to the WRONG solution here. Or, perhaps we have: 12....12 12....123 A uniqueness test here tells us something. What? That the 123 has to be 3, right? But a simple reverse logic test verifies that 3 can be eliminated: Hypothesis: 3 can be eliminated lower right 123: If either 1 or 2 are TRUE, then 3 can be eliminated. lower left 12: If either 1 or 2 are FALSE, then 3 can be eliminated. lower left 12: One or the other of 1 or 2 must be FALSE, so 3 can be eliminated. The hypothesis is proven. 3 can be eliminated. I would suggest that something has ALREADY gone wrong in the solution and that for a valid puzzle, this particular arrangement simply should not -- cannot -- arise. Is there something else in the "proto-uniqueness" area that would be a precursor in the solution to 12....12 12....12 that I am missing? So a challenge: Find a valid (unique) Sudoku that is one step from this uniqueness problem and for which simple chain-forcing logic or hypothesis/proof logic deliver the NONunique solution. My suspicion is that this puzzle cannot be found -- if it is for a valid Sudoku. _________________ 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: Fri Nov 04, 2005 12:34 am    Post subject: Bob wrote: Hypothesis: 3 can be eliminated lower right 123: If either 1 or 2 are TRUE, then 3 can be eliminated. lower left 12: If either 1 or 2 are FALSE, then 3 can be eliminated. lower left 12: One or the other of 1 or 2 must be FALSE, so 3 can be eliminated. The hypothesis is proven. 3 can be eliminated. If the 4 squares were the only ones with candidates 1 and 2, you would be right. But the digits 1 and 2 can appear anywhere. Unlike swordfish and coloring, with uniqueness we only consider these 4 cells in the corners of that rectangle. The remaining cells are only taken into consideration when tests 3 and 4 are performed. Quote: Find a valid (unique) Sudoku that is one step from this uniqueness problem and for which simple chain-forcing logic or hypothesis/proof logic deliver the NONunique solution. You are probably right. So far, I have not been able to solve any extra puzzles. (I only have 4 that I cannot solve yet, so it is not really a representative sample) However, the uniqueness test can find shortcuts that remarkably speed up the solving by taking quick shortcuts. The rectangles are easily spotted in a puzzle, not only by the program, but also by a human. It is, therefore, a fast, user friendly technique, that should be present in any program claiming to be a "helper" or "assistant". Besides, I like the "think outside the box" aspect of it. Ruud. Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Fri Nov 04, 2005 4:47 am    Post subject: I uploaded a larger list now: http://magictour.free.fr/top888 and a changed version of top95 into random instances from the same equivalence class. So the solving characterics should be the same, but some solvers rely on the orientation of the grid. http://magictour.free.fr/top95eq Back to top Lummox JR Joined: 07 Sep 2005 Posts: 202 : Items Posted: Fri Nov 04, 2005 5:27 am    Post subject: I've dealt with Bob's question in the player forums, but what it basically boils down to is that we're only showing part of the candidate list for the full puzzle here, and in particular just focusing on those 4 cells. There are not "strong edges" between the roof and floor cells for both candidates; it's just that in examples we never bother showing the other cells that prevent strong edges from forming. And yes, it is logical that another technique will expose the same information--the question is how quickly. If a uniqueness test saves you from using advanced coloring or T&E to solve the puzzle, you've just vastly simplified your solution path. Back to top xyzzy Joined: 24 Aug 2005 Posts: 80 : Items Posted: Fri Nov 04, 2005 1:06 pm    Post subject: Here is another uniqueness pattern. Remember that the .'s can have any number of possibilities, including 1, 2, and 3. Code: 12 . . | 23  . . | . . . 23 . . | 31X . . | . . . 31 . . | 12  . . | . . . By uniqueness, X must be true and the other choices in that cell can be eliminated. The first column can either be 1, 2, 3 or it can be 2,3,1. Suppose we eliminated X. Now the second column can be either 2,3,1 or 3,1,2. This means there are four different ways the two columns can be placed. Let's consider one of them. Code: 1 . . | 2 . . | . . . 2 . . | 3 . . | . . . 3 . . | 1 . . | . . . It's clear that the two minicolumns can be swapped, and the sudoku will still be valid. Thus, this solution is non-unique. The other three choices for filling in the two columns will be non-unique this same way. Therefore if we eliminate the X, a unique solution no longer exists. Since X can not be eliminated it must be true. Here's another non-unique pattern for a finished sudoku: Code: 1 . . | 2 . . | 3 . . . . . | . . . | . . . 3 . . | 1 . . | 2 . . Note that the first pattern involved 2 columns, 2 boxes, 3 rows and 3 digits, while this one is 3 columns, 3 boxes, 2 rows and 3 digits. This pattern is non-unique because the 123 in the first row can be swapped with the 312 in the second row and the sudoku will still be valid. This means any possibility set that will always end up in this pattern or one of its 12 permutations is non-unique. And therefor any elimination that ends up with a possibility set like this can not be made. For instance, say we had: Code: 23 . . | 123 . . | 23X . .  . . . |   . . . |   . . .  1 . . |  23 . . |  23 . . We know the X is true, because if it was eliminated, all ways of placing the remaining non-dot cells are a non-unique pattern. Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Fri Nov 04, 2005 1:52 pm    Post subject: xyzzy wrote: Here is another uniqueness pattern I haven't seen those before. You need to think of a new name for this type of pattern. Here is another one: Code: 12 . . | 12 . . | .   . . 12 . . | .  . . | 12  . . .  . . | 12 . . | 12X . . This one's 2-digits, 6-cells (swordfish-style) I think this could even be one: 2-digits, 10 cells (squirmbag-style) Code: 12 . . | 12 .  .  | .   . . 12 . . | .  .  .  | 12  . . .  . . | .  .  12 | 12X . . -------+----------+--------- .  . . | 12 12 .  | .   . . .  . . | .  .  .  | .   . . .  . . | .  .  .  | .   . . -------+----------+--------- .  . . | .  12 12 | .   . . .  . . | .  .  .  | .   . . .  . . | .  .  .  | .   . . Ruud. Back to top Moschopulus Joined: 12 Aug 2005 Posts: 39 : Items Posted: Fri Nov 04, 2005 4:56 pm    Post subject: xyzzy wrote: Here's another non-unique pattern for a finished sudoku: Code: 1 . . | 2 . . | 3 . . . . . | . . . | . . . 3 . . | 1 . . | 2 . . An example of what some call an unavoidable set. An unavoidable set is a set of cells such that some permutation of the cells gives another valid completed grid. Any unavoidable set will give you a uniqueness test. There are lots of unavoidable sets. Back to top rubylips Joined: 07 Apr 2005 Posts: 62 : Location: London Items Posted: Fri Nov 04, 2005 7:36 pm    Post subject: dukuso wrote: I uploaded a larger list now: http://magictour.free.fr/top888 My preliminary results are that #24, #49, #195 and #204 are as hard as anything before whereas #290, #314 and #351 are harder. _________________ Java 5.0 Solver/Composer Applet: http://act365.com/sudoku GPL Source Code: http://sf.net/projects/sudoku Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Fri Nov 04, 2005 8:11 pm    Post subject: My results are: #24, #49, #73, #81, #93, #290, #314, #351 not solved without DLX. Hmmm.. that doubles my TO DO list. Ruud. Back to top rubylips Joined: 07 Apr 2005 Posts: 62 : Location: London Items Posted: Fri Nov 04, 2005 8:33 pm    Post subject: I've noticed before that puzzles with double-diagonal symmetry, such as #290, #314 and #351 (DD with a superfluous cell removed), are often hard to solve. More oddly, the first four moves are often near-impossible, while the remainder of the puzzle then becomes trivial. Any ideas why this should be? Do the initially-filled cells in a symmetric puzzle somehow duplicate information? _________________ Java 5.0 Solver/Composer Applet: http://act365.com/sudoku GPL Source Code: http://sf.net/projects/sudoku Back to top rubylips Joined: 07 Apr 2005 Posts: 62 : Location: London Items Posted: Fri Nov 04, 2005 8:44 pm    Post subject: dukuso, Talk about #290, #314 and #351 being from the same equivalence class - they're exactly the bleeding same. mate!! It's a good puzzle, though - well worth repeating. Here it is in full: Code:  6 . . | . 4 . | . . 3  . 1 . | . . . | . 7 .  . . 5 | . . . | 8 . . -------+-------+------  . . . | 5 . 2 | . . .  3 . . | . 9 . | . . 2  . . . | 1 . 3 | . . . -------+-------+------  . . 8 | . . . | 9 . .  . 7 . | . . . | . 5 .  2 . . | . 3 . | . . 4 Log up until point of submission: Code: The value 4 in Row 5 must lie in Box 5. - The moves r5c2:=4, r5c3:=4, r5c7:=4 and r5c8:=4 have been eliminated. The values 2 and 3 occupy the cells r7c8 and r8c7 in some order. - The moves r7c8:=1, r7c8:=6, r8c7:=1 and r8c7:=6 have been eliminated. Consider the chain r1c7-5-r1c6~5~r9c6-5-r9c2~5~r5c2-5-r5c7. The cell r5c7 must contain the value 5 if the cell r1c7 doesn't. Therefore, these two cells are the only candidates for the value 5 in Column 7. - The moves r2c7:=5 and r6c7:=5 have been eliminated. Consider the chain r1c6-5-r1c7-5-r5c7-5-r5c2~5~r9c2-5-r9c6. The cell r9c6 must contain the value 5 if the cell r1c6 doesn't. Therefore, these two cells are the only candidates for the value 5 in Column 6. - The moves r2c6:=5 and r7c6:=5 have been eliminated. Consider the chain r5c2-5-r5c7-5-r1c7-5-r1c6-5-r9c6-5-r9c2. The cell r9c2 must contain the value 5 if the cell r5c2 doesn't. Therefore, these two cells are the only candidates for the value 5 in Column 2. - The moves r6c2:=5 and r7c2:=5 have been eliminated. Candidates at point of submission: Code:           6      2|8|9      2|7|9 |    2|7|8|9          4    1|5|7|8|9 |      1|2|5        1|2|9          3       4|8|9          1    2|3|4|9 |  2|3|6|8|9    2|5|6|8        6|8|9 |      2|4|6            7      5|6|9       4|7|9    2|3|4|9          5 |  2|3|6|7|9    1|2|6|7      1|6|7|9 |          8    1|2|4|6|9      1|6|9 ----------------------------------+------------------------------------+-----------------------------------   1|4|7|8|9    4|6|8|9  1|4|6|7|9 |          5      6|7|8            2 |  1|3|4|6|7  1|3|4|6|8|9  1|6|7|8|9           3      5|6|8      1|6|7 |    4|6|7|8          9      4|6|7|8 |    1|5|6|7        1|6|8          2   4|5|7|8|9  2|4|6|8|9  2|4|6|7|9 |          1      6|7|8            3 |      4|6|7      4|6|8|9  5|6|7|8|9 ----------------------------------+------------------------------------+-----------------------------------       1|4|5      3|4|6          8 |    2|4|6|7  1|2|5|6|7      1|4|6|7 |          9          2|3      1|6|7       1|4|9          7  1|3|4|6|9 |  2|4|6|8|9    1|2|6|8    1|4|6|8|9 |        2|3            5      1|6|8           2      5|6|9      1|6|9 |    6|7|8|9          3  1|5|6|7|8|9 |      1|6|7        1|6|8          4 _________________ Java 5.0 Solver/Composer Applet: http://act365.com/sudoku GPL Source Code: http://sf.net/projects/sudoku 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 Previous  1, 2, 3, 4  Next Page 2 of 4   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