FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    What is logic, and what is trail and error, backtracking, ed Goto page Previous  1, 2          Sudoku Programmers Forum Index -> The mathematics of sudoku View previous topic :: View next topic   Author Message gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Sat Dec 24, 2005 10:36 am    Post subject: dukuso wrote: I have about 5000 random minimal 16*16s, about 1 is generated per second. I assume you can make it 3-times faster. That's enough to get started, we don't need 200million. post the 5000, I'm ready to go dukuso wrote: that O(...) is it secret or copyright by ATT or such ? http://www.cs.cornell.edu/gomes/papers/sat03.pdf concludes that even with small backdoors pure backtrack search is exponential but also explains why backtrack with restart can come close to polytime in practice Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Sat Dec 24, 2005 10:50 am    Post subject: Re: What is logic, and what is trail and error, backtracking Mark wrote: That's an interesting conjecture, and the results you obtained on the minimum sudokus and random sample are certainly promising. But is there any analysis to indicate (or plausibly suggest) that there won't be pathological cases that foil the all-pairs strategy for the 9x9 case? A sample size of 225M, while hefty in the usual sense, wouldn't appear to be particularly meaningful in light of the large sudoku space. well that's why its a conjecture among the 225M are puzzles scraped from the forums, including ones designed to foil the latest logic strategies, and ones generated to exhibit specific properties Back to top dukuso Joined: 14 Jul 2005 Posts: 424 : Location: germany Items Posted: Sat Dec 24, 2005 12:05 pm    Post subject: about 20000 16*16 sudokus uploaded to http://magictour.free.fr/sudoku16.gz some could be nonminimal, I just put everything I could find into one big file. Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Sat Dec 24, 2005 6:45 pm    Post subject: dukuso wrote: about 20000 16*16 sudokus uploaded to http://magictour.free.fr/sudoku16.gz thanks here's preliminary results for 16 sudoku backdoor size f means the first forward check solved the puzzle the 1's should have been found by the first forward check so there's some debugging in order looks like 4 or 5 may be the max min backdoor size for 16 sudoku Code: f 13612 1 63 2 6440 3 2408 4 18 5 0 Back to top Mark Joined: 19 Oct 2005 Posts: 30 : Location: Arizona Items Posted: Sat Dec 24, 2005 10:59 pm    Post subject: Re: What is logic, and what is trail and error, backtracking gsf wrote: Mark wrote: But is there any analysis to indicate (or plausibly suggest) that there won't be pathological cases that foil the all-pairs strategy for the 9x9 case? well that's why its a conjecture Indeed, a simple conjecture is all that it appears to be. One had hoped there was a deeper analysis to suggest why only two independent variables would be required to address the underlying structure of 9x9 sudoku. Also, the small-backdoor hypothesis means only that backtracking will be more efficient in practice, but won't do anything to remove its underlying trial-and-error, exponential-time behavior. Or is this a misunderstanding? Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Mon Dec 26, 2005 4:51 pm    Post subject: Re: What is logic, and what is trail and error, backtracking Mark wrote: Also, the small-backdoor hypothesis means only that backtracking will be more efficient in practice, but won't do anything to remove its underlying trial-and-error, exponential-time behavior. Or is this a misunderstanding? the exponential behavior is w.r.t. problem size for nxn sudoku (where n is a square), as n increases, the solution time increases exponentially, but the possible existence of small backdoors may allow some solvers to consistently beat the worst case time for 9x9 sudoku with conjectured backdoor size 2 the exponential component is 2^2=4 well within the range of beating any logic (!= trial-and-error?) method Back to top Mark Joined: 19 Oct 2005 Posts: 30 : Location: Arizona Items Posted: Wed Dec 28, 2005 1:27 am    Post subject: Re: What is logic, and what is trail and error, backtracking gsf wrote: the exponential behavior is w.r.t. problem size for nxn sudoku (where n is a square), as n increases, the solution time increases exponentially, but the possible existence of small backdoors may allow some solvers to consistently beat the worst case time I realize there's always been this paradox in the mathematical programming disciplines: namely, that exptime techniques turn out to perform very well in practice. The small backdoor hypothesis seems to be pragmatic in nature, merely posited with a view to creating faster search programs. There's still no suggestion how these backdoor variables might relate to the underlying structure of the problem. gsf wrote: for 9x9 sudoku with conjectured backdoor size 2 the exponential component is 2^2=4 well within the range of beating any logic (!= trial-and-error?) method Yes, there's probably no doubt in this case that a sophisticated trial and error approach has the best performance. Perhaps even a naive DLX solver outperforms the logic-based ones on puzzles that require seaching for nonrepetitive cycles or paths with conflicting endpoints. Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Wed Dec 28, 2005 4:57 am    Post subject: Re: What is logic, and what is trail and error, backtracking Mark wrote: Yes, there's probably no doubt in this case that a sophisticated trial and error approach has the best performance. Perhaps even a naive DLX solver outperforms the logic-based ones on puzzles that require seaching for nonrepetitive cycles or paths with conflicting endpoints. what sophistication for 9x9 check all singletons and check all pairs => solved or conjecture refuted and I'm not convinced that dlx link/unlink is cost effective for 9x9 sudoku Back to top Mark Joined: 19 Oct 2005 Posts: 30 : Location: Arizona Items Posted: Wed Dec 28, 2005 11:17 am    Post subject: Re: What is logic, and what is trail and error, backtracking gsf wrote: Mark wrote: Yes, there's probably no doubt in this case that a sophisticated trial and error approach has the best performance. Perhaps even a naive DLX solver outperforms the logic-based ones on puzzles that require seaching for nonrepetitive cycles or paths with conflicting endpoints. what sophistication for 9x9 check all singletons and check all pairs => solved or conjecture refuted and I'm not convinced that dlx link/unlink is cost effective for 9x9 sudoku The sophistication simply refers to using the backdoor hypothesis (i.e. checking all pairs for 9x9) in lieu of brute force trial-and-error, or even the simple min-column heuristic of Knuth's DLX. It would appear that the primary motivation for using the backdoor approach stems from what I'm assuming is its performance advantage over DLX. That's great; faster software is always a plus. But it's still a trial-and-error technique, and doesn't succeed in achieving polynomial-time execution. Back to top weia Joined: 12 Nov 2005 Posts: 5 : Items Posted: Mon Jan 30, 2006 7:37 pm    Post subject: Is 'logic' meant in a broad or a narrow sense in this topic? In the broad sense every manner to find a solution of a unique sudoku (with not more than 1 solution) is logic. In a narrow sense it maybe is a matter of taste. I see three different kinds of steps on the way to the solution: 1 singles and hidden singles are straightforward and clear 2 you can look for patterns that reduce the number of possibilities in a certain cell (followed by new singles) 3 you can follow a chain until you find a contradiction or a solution. This last thing I feel as 'trial and error', so finding a solution by colouring is in my view not logic. X-wings, triples and so on are. Again: to my taste. Back to top Myth Jellies Joined: 20 Sep 2005 Posts: 14 : Items Posted: Sun Apr 09, 2006 6:51 am    Post subject: Rather than term it "logic" versus "trial & error" (which is arguably a form of logic), I am going to refer to the solution methods as "theoretical" versus "brute force". Theoretical solution methods rely on some valid theory to make deductions about the puzzle. There is mathematical branch, algorithmic information theory, which has something to say about what makes a valid theory. I just caught an article in Scientific American (March 2006 pp. 74-81) which is related to the idea of complexity versus useful logical theory. The article entitled The Limits of Reason was written by Gregory Chaitin, the pioneer of algorithmic information theory. Summarizing the article--Gottfried W. Leibniz made the observation in his 1686 essay, Discourse on Metaphysics, that a theory has to have an quality of simplicity, otherwise it does not explain anything. If you allow theories and laws unlimited complexity, then you can devise a theory to explain any random set of data; but that theory is essentially meaningless. The algorithmic information theorists have quantified this concept of complexity versus theory. In essence, they state that for a theory to have any teeth, it must be simpler than the data it explains. So how does this all relate to a sudoku puzzle and our proposed "theoretical methods"? Well, say you have a theory which allows you to eliminate a particular candidate in a particular cell. For most cases, your "theory" consists of all of the candidates that you needed to make your deduction. On the other hand, your "data" is the number of candidates you need to consider if you happened to randomly assume that the candidate you eliminated was true and then followed things along until the puzzle crashes. If you can make a case that often your number of theory candidates is less than your number of data candidates, then you have the makings of a viable theoretical or logical method. Take as an example, the naked pair in the following row... Code: 12  12  13  34  45  56  7  8  9 The naked 12-pair uses precisely four "theory" candidates to eliminate any other 1's and 2's in the row, in this case, the 1 in the third cell. Now if we assume the third cell is a 1, that is one candidate of data. That eliminates the 1's from the first two cells (3 candidates of data so far). That leaves only a 2 in both those cells for a total of 5 data candidates involved in the crash. The theory is smaller than the data, thus making it useful. One of the outcomes of this way of looking at things is that methods which provide an action/deduction at a distance, i.e. a reduction in cells that are not part of the theoretical pattern, tend to be valid theoretical methods. Those which require participation of the deductee in the pattern are suspect, and tend to fall in the non-theoretical, brute force pile. Some interesting results applying algorithmic information theory (the way I interpret it) to some questionable solution methods: Simple Coloring (cell sees both conjugate colors) => Theoretical Simple Coloring (same color twice in group) => Brute Force* Multicoloring (type 2 reduction) => Theoretical XY-Wing => Theoretical Forcing Chain Method (reduction candidate not part of chain) => Theoretical Forcing Chain Method (reduction candidate is part of chain) => Brute Force Zero or Two Occurances Rule (Uniqueness, BUG, BUG-Lite) => Theoretical (*Note that for simple coloring, you always have a cell that sees both conjugate colors prior to filling it in and having the same color twice in a group. Thus the coloring method is safely 'theoretical".) Some comments based on the algorithmic information theory concept: First, the absolute complexity of a theory candidate is immaterial. If the data being explained is of "exponential complexity", then there can exist valid theories that explain that data that are also of "exponential complexity". On the other hand, a potential theory can be of "polynomial complexity", but if it only comes up with a reduction when the data it applies to is less complex, then it still might not be a valid theory. It is only the relative complexity between a theory and the part of the puzzle it is trying to explain that matters. Second, a theoretical method is allowed to fail. One might attempt to construct all sorts of grouped colors or forcing chains, most or all of which may fail to result in a reduction. No matter how elaborate those failed constructions may have been, they have no bearing on whether a method is theoretical or brute force. An article similar to the one appearing in SA is http://plus.maths.org/issue37/features/omega/ Gregory Chaitin's home page with lots of related links is http://www.umcs.maine.edu/~chaitin/ Before reading these, I fully believed that every sudoku puzzle could be cracked using only the basic rules and theoretical methods. Now, I am not quite so sure _________________ Myth Jellies Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Sun Apr 09, 2006 1:06 pm    Post subject: Myth Jellies wrote: (A) Forcing Chain Method (reduction candidate not part of chain) => Theoretical (B) Forcing Chain Method (reduction candidate is part of chain) => Brute Force what are the limits on forcing chain length for either type? (empirical/estimate ok) what is the theory for picking the start cell and value for either type? what mathematical properties differentiate A from B? I think there is a clear difference between pattern based and chain based methods human solvers (brain+eyes+penchant for patterns) have a much better chance (and probably more fun too) finding patterns rather than serpentine chains that may fail (and possibly #empty cells X #candidates of them!) Back to top Myth Jellies Joined: 20 Sep 2005 Posts: 14 : Items Posted: Sun Apr 09, 2006 11:44 pm    Post subject: gsf wrote: what are the limits on forcing chain length for either type?...I think there is a clear difference between pattern based and chain based methods Let's take the xy-chain as an example of a chain method that is theoretical. The xy-chain does have a pattern, which looks something like ab-bc-...-xy-ya, and the deduction is that any cell which sees both endpoints of the chain cannot be 'a'. The difference between the pattern of an xy-chain and those of simpler methods is that there is no implied limit to how large the pattern is, or alternatively, how many theory cells there are. The xy-chain theory can be shown valid for the shortest 2-cell xy-chain (a naked pair). The xy-chain theory can be shown valid for 3-cell xy-chains (2-2-2 triplets and xy-wings). Thus the theory can be applied for chains of practically any length. Brute force forcing chains are brute force no matter what their length is. gsf wrote: what is the theory for picking the start cell and value for either type? Drifting off topic here. It would depend on the particular method you choose. I find it is not so much picking a starting cell as it is knowing when to give up on a particular chain start. Comes with experience I guess. gsf wrote: what mathematical properties differentiate A [theoretical chain methods] from B [brute force chain methods]? Brute force chain methods are never simpler (require fewer candidates) than the data they describe/reduce. gsf wrote: human solvers (brain+eyes+penchant for patterns) have a much better chance (and probably more fun too) finding patterns rather than serpentine chains that may fail (and possibly #empty cells X #candidates of them!) Noting the difficulty of the majority of puzzles that are published, you likely are echoing the opinion of the majority. Tastes vary, though. Personally I find it much easier to construct an xy-chain than it is to find a devilish hidden triple, hidden quad, swordfish, or jellyfish. The search for any particular pattern may fail. It just takes a lot longer to figure that out for pattern of indeterminate length than it does for relatively static patterns. However, it should come as no surprise that the more difficult puzzles require theories that are more difficult to apply. _________________ Myth Jellies Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Mon Apr 10, 2006 12:01 am    Post subject: Myth Jellies wrote: Let's take the xy-chain as an example of a chain method that is theoretical. I agree with your take on xy chains there's no if involved the chain exists and you draw a conclusion from its existence so I assume x cycles fall into the theoretical category too is the differentiating factor "start a chain by assuming this cell has this value" => "brute force" i.e., brute force chains don't exist until a candidate assignment is made Back to top Myth Jellies Joined: 20 Sep 2005 Posts: 14 : Items Posted: Wed Apr 12, 2006 12:27 am    Post subject: [quote="gsf"]so I assume x cycles fall into the theoretical category too [/quote] X-Cycles can always be performed in such a way that they are theoretical. There are methods for finding them which avoid including removed candidates in the chain. [quote="gsf"]is the differentiating factor "start a chain by assuming this cell has this value" => "brute force" i.e., brute force chains don't exist until a candidate assignment is made?[/quote] That is one way you can tell; although, for chains, it is a bit more stringent than that. Starting a chain assuming a candidate is not true, starting a chain using a one-way link assumption, or starting a chain, and including the candidate that will be deleted are other likely indications of a brute force method. _________________ Myth Jellies Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> The mathematics of sudoku All times are GMT Goto page Previous  1, 2 Page 2 of 2   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