FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Forcing Chains - Definition and clarification required          Sudoku Programmers Forum Index -> Solving sudoku View previous topic :: View next topic   Author Message kranser Joined: 18 Aug 2005 Posts: 35 : Items Posted: Mon Nov 14, 2005 9:52 pm    Post subject: Forcing Chains - Definition and clarification required Hi, I've implemented Forcing Chains in my solver as follows: 1) For each cell, try each candidate - Make a chain of any cells that are forced to be a value due to this candidate. For each cell in the chain, add to the chain any cells forced to be a value by that cell's value. 2) When complete, search the chains for a common cells with a common value. If the same cell with the same value is found in all candidate chains, then this cell must be that value. So, I think I've got the basics; however, I have some questions: A) If a cell is forced to be a value by another cell in its column (for example) taking its other available candidate, can this cell be forced to that value, even if there is another cell in that cells block that is already set to that value? I.e. the path we followed produced an invalid puzzle, so can we still follow along the invalid path adding all forced values to the chain, or does the fact that we've reached an invalid position mean that any forced values are errors, and can not be part of the common cell with a common value search (#2 above). B) If we do find a invalid position (as per Question A) [i.e. where a cell forced to a value cannot really be that value due to the constraints of the cell's other groups], can we eliminate the candidate we're following from the original cell, or does forced chains not allow that technique, because it is tabling - or some other technique? Kranser. Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Mon Nov 14, 2005 10:26 pm    Post subject: Hi, Quote: For each cell, try each candidate - Make a chain of any cells that are forced to be a value due to this candidate. For each cell in the chain, add to the chain any cells forced to be a value by that cell's value. Well, that's how I started, calling it forcing chains, having to admit later that it was actually tabling. Where are the boundaries of these techniques? Some claim that Forcing Chains are limited to cells with 2 candidates only, but you are allowed to start from any cell. I do the whole bivalue/bilocation chains, since they yield a better result. The only limitation I have is: they must be chains. If you're taking all implications into account you're doing tabling. I do that too, but I'm now calling it tabling. When you build these methods with parameters, you can call it anything from coloring to forcing chains, from bifurcation chains to hypothesis & trial and tabling. Just depends on the parametrized limitations. You questions: When you encounter an invalid path, the source of that path is invalid (the digit you tried) and can be Eliminated. All other consequences must be ignored, because you have just proven that the path does not exist in the solution. Actually this happens much more often in forcing chains than the so-called verities. Ruud. Back to top Bob Hanson Joined: 05 Oct 2005 Posts: 187 : Location: St. Olaf College Items Posted: Tue Nov 15, 2005 7:09 pm    Post subject: Quote: 1) For each cell, try each candidate - Make a chain of any cells that are forced to be a value due to this candidate. For each cell in the chain, add to the chain any cells forced to be a value by that cell's value. Basically, this is the idea. Something to think about is the difference between "cells" and "marks" (or "nodes"). My education was in seeing that the fundmental unit is a "possible candidate" not a "cell" value. When you do this, you realize that it an be at least as informative to hypothesize that a certain cell is NOT a certain candidate as it is to hypothesize, as you are here, that it IS a certain candidate. (For example, if a cell is NOT X, then maybe that also demands that some other cell in another block is also NOT X.) Quote: 2) When complete, search the chains for a common cells with a common value. If the same cell with the same value is found in all candidate chains, then this cell must be that value. If you do it the way you describe -- postulate that a certain cell IS a certain candidate, that's fine. Then you need to recognize that if you do this, you need to be looking not for cells that have the same value regardless but, rather, conditions for which there is a logical inconsistency -- a cell with no possible value; a row, column, or block with no place for a candidate; two placements of the same candidate in the same row, column, or block, etc. Where you can be fooled on this is that some cells are "strongly connected" so saying "The cell is X" is also saying "This other cell is NOT X". This is what allows a modicum of success for your proposed strategy. Your strategy of looking for a "verity", or cell with the same value regardless of starting conditions, actually depends upon saying "This cell is NOT X". So that strategy works specifically for this sort of strongly linked cell. But this is a special case and does not blanket all the tests required IN GENERAL to solve Sudoku puzzles. That is, if using the logic that goes, "If this cell is X, then this cell is/is not Y", then you MUST look for logical inconsistencies, not "logical verities"--cases where some cell is the same value regardless of the selection of initial options. More discussion of this can be found at the Sudoku Assistant site: http://www.stolaf.edu/people/hansonr/sudoku Your "chains" are sort of a mix of strong and weak chains. But the chains at that site are not chains of cells, but chains of nodes. This might be something to think about, anyway. _________________ Bob Hanson Professor of Chemistry St. Olaf College Northfield, MN http://www.stolaf.edu/people/hansonr Back to top xyzzy Joined: 24 Aug 2005 Posts: 80 : Items Posted: Wed Nov 16, 2005 12:06 am    Post subject: Re: Forcing Chains - Definition and clarification required kranser wrote: 2) When complete, search the chains for a common cells with a You only need to search a set that must contain a correct guess. Suppose a number has only two places it can go in a row, if you guess both those places you know any common eliminations from just those two guesses must be true. Quote: I.e. the path we followed produced an invalid puzzle, so can we still follow along the invalid path adding all forced values to the chain, or does the fact that we've reached an invalid position mean that any forced values are errors, and can not be part of the common cell with a common value search (#2 above). Once you have discovered an error, there is no point to following the path further. What you have discovered so far, nodes forced or eliminated, may or may not be true. You can say that your initial guess was incorrect. What you have discovered doesn't need to be part of the common value search, but it can be. If you think about it for a bit, suppose you don't include the chains from invalid paths in your common value search. Now you find some set of common values, which you know are all correct. Now add in that invalid path, will you now find more common values? Obviously, you can't find more, you can only take away common values. So including the invalid path won't cause you to find common value which are incorrect, but may cause you to find miss common values that you could have found. 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