
View previous topic :: View next topic 
Author 
Message 
 gsf
 Joined: 18 Aug 2005  Posts: 408  :  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 3times 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: 408  :  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 allpairs 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: 408  :  Location: NJ USA  Items 

Posted: Sat Dec 24, 2005 6:45 pm Post subject: 


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 allpairs 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 smallbackdoor hypothesis means only that backtracking will be more efficient in practice, but won't do anything to remove its underlying trialanderror, exponentialtime behavior. Or is this a misunderstanding? 

Back to top 


 gsf
 Joined: 18 Aug 2005  Posts: 408  :  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 smallbackdoor hypothesis means only that backtracking will be more efficient in practice, but won't do anything to remove its underlying trialanderror, exponentialtime 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 (!= trialanderror?) 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 (!= trialanderror?) 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 logicbased ones on puzzles that require seaching for nonrepetitive cycles or paths with conflicting endpoints. 

Back to top 


 gsf
 Joined: 18 Aug 2005  Posts: 408  :  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 logicbased 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 logicbased 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 trialanderror, or even the simple mincolumn 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 trialanderror technique, and doesn't succeed in achieving polynomialtime 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. Xwings, 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. 7481) 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 articleGottfried 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 12pair 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 nontheoretical, 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
XYWing => 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, BUGLite) => 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: 408  :  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 xychain as an example of a chain method that is theoretical. The xychain does have a pattern, which looks something like abbc...xyya, and the deduction is that any cell which sees both endpoints of the chain cannot be 'a'. The difference between the pattern of an xychain 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 xychain theory can be shown valid for the shortest 2cell xychain (a naked pair). The xychain theory can be shown valid for 3cell xychains (222 triplets and xywings). 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 xychain 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: 408  :  Location: NJ USA  Items 

Posted: Mon Apr 10, 2006 12:01 am Post subject: 


Myth Jellies wrote: 
Let's take the xychain 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]
XCycles 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 oneway 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 




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
