FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Error Chains (new solve technique?) Goto page 1, 2, 3  Next          Sudoku Programmers Forum Index -> Solving sudoku View previous topic :: View next topic   Author Message Graeme Joined: 31 Jan 2006 Posts: 22 : Location: Adelaide Items Posted: Tue Jan 31, 2006 2:41 pm    Post subject: Error Chains (new solve technique?) I haven't been around these pages for long, but I have a technique I call Error Chains that seems quite powerful. It's not on the Sadman site, so I'll publish it here. Apologies if this is well known, and already has another name. If so, I'm sure someone will set me straight Like Nishio and Forcing Chains, this involves looking at implications of a single cell guess. "Implications" here are restricted to invalid candidate removal, and placement of naked singles. If these implications lead to a cell with no remaining candidates, then the original guess candidate can be removed. I also suspect this technique is easier for humans than Forcing Chains (looking for values set regardless of initial choice), and possibly Nishio (looking for inability to place the same guess candidate elsewhere). In my own solver I place this step after all others except brute force trial and error. With my limited testing, it often removes candidates not found by other techniques and solves the puzzle! Any thoughts, anyone? G Last edited by Graeme on Wed Feb 01, 2006 9:49 am; edited 1 time in total Back to top Henk Joined: 13 Nov 2005 Posts: 105 : Items Posted: Tue Jan 31, 2006 3:54 pm    Post subject: If I understand it correctly it would find the following: 12 | 23 | 24 .....| 35 | 54 If the 12 field is an 2, the bold field can neither be 3 or 4. The 12 field cannot be 2. Does forcing chains not find it also? Can you explain more? _________________ Generate and solve Sudoku puzzles with Into Sudoku! Back to top Graeme Joined: 31 Jan 2006 Posts: 22 : Location: Adelaide Items Posted: Tue Jan 31, 2006 9:06 pm    Post subject: What you've shown is corrrect. Of course, it's not limited to pair candidates. Forcing chains look for values that are set regardless of the intial choice, while Error Chains look for errors caused by the initial choice. I'm heading off to work now, but will give a more complete reply when I get back Back to top Graeme Joined: 31 Jan 2006 Posts: 22 : Location: Adelaide Items Posted: Wed Feb 01, 2006 9:37 am    Post subject: Here's an example, starting with Code: . . 9 | . . 2 | . . . . 3 . | . 9 . | . . . . 5 . | 7 8 . | . . 9 ------+-------+------ . 4 . | 3 . . | 2 . . . . 7 | 2 . 8 | 5 . . . . 1 | . . 5 | . 6 . ------+-------+------ 6 . . | . 7 9 | . . 8 . . . | . 2 . | . . 5 . . . | 4 . . | . 7 . This puzzle has 25 solutions, so you wouldn't be surprised to need brute force T&E, but you actually don't. After naked singles, hidden singles, block/line reduction and xy-wing and some more hidden singles, it's simplified to this: Code: {1,4,7,8}  {1,7,8}     9     {1,6}  5    2   {1,3,4,6,7,8}  {1,3,4}  {3,6,7}    {1,2,7,8}     3     {2,6,8}  {1,6}  9    4     {1,6,7,8}       5     {2,6,7}    {1,2,4}       5     {2,4,6}    7    8    3      {1,4,6}     {1,2,4}     9           9          4        5       3    6    7         2           8        1           3          6        7       2    1    8         5           9        4         {2,8}      {2,8}      1       9    4    5       {3,7}         6      {3,7}         6        {1,2}   {2,3,4}    5    7    9      {1,3,4}    {1,2,3,4}    8        {1,4,7}    {1,7,9}   {3,4}     8    2  {1,6}  {1,3,4,6,9}  {1,3,4}      5           5      {1,2,8,9}  {2,8}     4    3  {1,6}    {1,6,9}       7       {2,6}      No other "standard techniques" including Nishio and Forcing Chains, find anything further, but my solver then shows: Code: Error Chain removed candidate {8} from cell A2 Error Chain removed candidate {1} from cell A7 Error Chain removed candidate {6} from cell A7 Error Chain guess {7} in A7 found complete solution PUZZLE SOLVED ~~~~~~~~~~~~~ 8 1 9 | 6 5 2 | 7 4 3 7 3 2 | 1 9 4 | 8 5 6 4 5 6 | 7 8 3 | 1 2 9 ------+-------+------ 9 4 5 | 3 6 7 | 2 8 1 3 6 7 | 2 1 8 | 5 9 4 2 8 1 | 9 4 5 | 3 6 7 ------+-------+------ 6 2 3 | 5 7 9 | 4 1 8 1 7 4 | 8 2 6 | 9 3 5 5 9 8 | 4 3 1 | 6 7 2 (my cell coordinates are A to J for rows, skipping letter "I", and 1 to 9 for columns) Here's what happens trying to set one of these values: Trying to set candidate {8} in cell A2 - sets 2 in F2 - which sets 8 in F1, and 1 in G2 - which sets 9 in J2 - which sets 7 in H2 - which sets 4 in H1 - which sets 3 in H3 - which sets 2 in G3, and 1 in H8 - which sets 7 in H2 - which sets 8 in J3, and 6 in cells B3, H6 & J7 - which sets 4 in C3, and 1 in B4 & J6, and 9 in H7, and 2 in J9 - which sets 6 in A4, and 7 in B9, and 1 in C7, and 2 in C8 and finally, an error (no candidates) in C1 Here's the pseudo code I use: Code:    for each cell       for each candidate value          set the value          loop             remove invalid candidates             if a cell has no candidates                remove the original guess candidate                exit loop             set naked singles             if all cells filled                puzzle is solved                exit loop          end_loop       next candidate value    next cell Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Wed Feb 01, 2006 10:19 am    Post subject: Graeme wrote: Here's what happens trying to set one of these values: Trying to set candidate {8} in cell A2 - sets 2 in F2 - which sets 8 in F1, and 1 in G2 ... and finally, an error (no candidates) in C1 how is this different from a backtrack tree search? how do you chose the initial cell/candidate in the error chain? once an error is found how are the eliminated candidates along the chain restored? Back to top Henk Joined: 13 Nov 2005 Posts: 105 : Items Posted: Wed Feb 01, 2006 11:52 am    Post subject: Quote: This puzzle has 25 solutions, so you wouldn't be surprised to need brute force T&E, but you actually don't. Do you find all solutions? or just one of them? It looks like standard backtracking, wich is how most programmers implement a brute force trial and error solver. _________________ Generate and solve Sudoku puzzles with Into Sudoku! Back to top Graeme Joined: 31 Jan 2006 Posts: 22 : Location: Adelaide Items Posted: Wed Feb 01, 2006 12:12 pm    Post subject: It may be the same as what you call backtracking, although the way I 've programmed my brute force solver, I think I'd call it forward tracking. Whatever the case, I used the brute force solver to find 25 solutions, and this is the easiest way to count solutions. But the point of a solver is to find a single solution, and show which techniques are required to solve the puzzle. The Error Chain technique guesses a single candidate in a single cell (it checks every candidate in every cell, one at a time), like Nishio and Forcing Chains. On the other hand, brute force is unlimited: it continues to guess values in as many cells as it needs until a solution is found. I work with a copy of the puzzle state to make it easy to restore the original state. Back to top Miles Joined: 29 Dec 2005 Posts: 30 : Items Posted: Wed Feb 01, 2006 12:57 pm    Post subject: If your solver needs a game with several solutions to work, then it's not aimed at solving Sudoku games which have only one solution. Why prefering one and not another ? Sudoku is about logic, not about "as there are several solutions, let's find one with guessing". Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Wed Feb 01, 2006 3:40 pm    Post subject: Graeme wrote: The Error Chain technique guesses a single candidate in a single cell (it checks every candidate in every cell, one at a time) I work with a copy of the puzzle state to make it easy to restore the original state. this is a backtrack tree search the backtrack happens when you go back to a previous copy of the state (the following edited in) for 0-constrained and 1-constrained 9x9 sudoku (2-constrained with all logic methods enabled are rare) one pass through all the cells/candidates (breadth first) will solve the puzzle meaning -- for most puzzles your solver will backtrack and find a solution with only depth one branching what does your solver do with this puzzle? Code: . . 3 | 4 . . | 6 . . . 5 . | . . 9 | . . . . . . | 2 . . | . . 5 ------+-------+------ 2 6 . | . 7 . | 1 3 . . . . | 8 . . | . 6 7 9 . . | 3 . . | . . . ------+-------+------ 5 . . | . . . | . . 8 . . 4 | . 2 . | . . . . 1 . | . . 3 | 7 . . Back to top Graeme Joined: 31 Jan 2006 Posts: 22 : Location: Adelaide Items Posted: Wed Feb 01, 2006 9:14 pm    Post subject: Hi Miles, The Error Chain technique does not need a puzzle with several solutions to work; it's just another technique similar to Nishio and Forcing Chains. I appreciate your views on logic and single solutiions; I also prefer those puzzles. And gsf, Thanks for the explanation of backtrack (I played my first Sudoku puzzle only weeks ago, and I'm new to some of the terminology). So yes, Error Chain is a single level backtrack tecknique, just like Nishio and Forcing Chains. My solver says there's just one solution to your puzzle, and it was found with these techniques: naked singles, hidden singles, box/line reduction, nishio (1 cell), and error chains (8 cells). Brute Force was not required. [Edit: oops, it DOES use brute force - full confession below] Last edited by Graeme on Thu Feb 02, 2006 8:42 am; edited 1 time in total Back to top Graeme Joined: 31 Jan 2006 Posts: 22 : Location: Adelaide Items Posted: Wed Feb 01, 2006 9:16 pm    Post subject: Many thanks to those who've already responded. My question in this thread is: Is this a new technique? I haven't found anything similar in all I've been able to find on solving techniques. Error Chains have similarities to Nishio, Forcing Chains and Brute Force techniques. Back to top Henk Joined: 13 Nov 2005 Posts: 105 : Items Posted: Wed Feb 01, 2006 9:31 pm    Post subject: Quote: Error Chains have similarities to Nishio, Forcing Chains and Brute Force techniques. If I understand everything correct: Error chains is the same as backtracking. I cannot find any similarities to Forcing Chains or Nishio. _________________ Generate and solve Sudoku puzzles with Into Sudoku! Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Wed Feb 01, 2006 10:08 pm    Post subject: Graeme wrote: My solver says there's just one solution to your puzzle, and it was found with these techniques: naked singles, hidden singles, box/line reduction, nishio (1 cell), and error chains (8 cells). Brute Force was not required. wikipedia wrote: a brute-force search consists of systematically enumerating every possible solution of a problem until a solution is found, or all possible solutions have been exhausted ... Generally, brute force refers to any method that does not involve a heuristic or rely on any intelligent observation, but tries every possible solution to find the best solution whatever the name, your solver guessed 8 times to arrive at a solution "error chains" fits the mold of backtracking and brute force nothing to be ashamed of the fastest computer solvers rely on judicious use of brute force just call it what it is brute force has the disadvantage that a trace of brute force moves will not aid a human solver -- there are no techniques to master, no patterns, no structure, just systematic guessing good for computers, bland and unsatisfying for humans Back to top Graeme Joined: 31 Jan 2006 Posts: 22 : Location: Adelaide Items Posted: Thu Feb 02, 2006 8:18 am    Post subject: wow - thanks for all the feedback everyone - lots of Qs & comments to keep up with, here goes: Quote: from Henk: Error chains is the same as backtracking. I cannot find any similarities to Forcing Chains or Nishio. All three techniques test the implications of placement of cell candidates in cells, one at a time. Under certain conditions, they take a certain action. For Nishio, the condition is the inability to place the test candidate elsewhere in the board, and the action is to remove the test candidate. For Forcing Chains, the condition is placement of the same value elsewhere on the board regardless of choice of the test candidate value. The action is to set that value. For Error Chains, the condition is a cell with all candidates removed, and the action is to remove the test candidate. My coding for these 3 techniques is identical except of course for detecting the condition, and action taken. Last edited by Graeme on Thu Feb 02, 2006 9:05 am; edited 1 time in total Back to top Graeme Joined: 31 Jan 2006 Posts: 22 : Location: Adelaide Items Posted: Thu Feb 02, 2006 8:39 am    Post subject: oops! Quote: I said: My solver says there's just one solution to your puzzle, and it was found with these techniques: naked singles, hidden singles, box/line reduction, nishio (1 cell), and error chains (8 cells). Brute Force was not required. My bad. Brute force is my last technique, and everytime I add a new technique, I need to increase the upper limit to show all technique statistics. Fixed that now, and my solver DOES make heavy use of Brute Force to solve this puzzle. I'll indicate the correction in the original message as well. My apologies. I've re-checked the original example above, and it does NOT use brute force. Quote: from gsf: your solver guessed 8 times to arrive at a solution I actually agree with the terminology "guess" here, but I'd point out that this is testing candidates to see if they cause an error. Error Chains found 8 candidates that cannot be used, and removed them. This is different than blind trial and error guessing in Brute Force. At this stage, I still believe the Error Chains technique is similar to the Nishio and Forcing Chain methods, and probably easier than either for humans. It's also not listed anywhere I've found in Sudoku solving techniques. After considering the generous feedback given above, I would agree that the condition my technique looks for (a cell with no candidates) is the same one that my brute force code ignores as "unhelpful" candidate selection. 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, 3  Next Page 1 of 3   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