Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

What is logic, and what is trail and error, backtracking, ed
Goto page Previous  1, 2
 
Post new topic   Reply to topic    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
PostPosted: Sat Dec 24, 2005 10:36 am    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Sat Dec 24, 2005 10:50 am    Post subject: Re: What is logic, and what is trail and error, backtracking Reply with quote

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
View user's profile Send private message Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Sat Dec 24, 2005 12:05 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Sat Dec 24, 2005 6:45 pm    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
Mark

Joined: 19 Oct 2005
Posts: 30
:
Location: Arizona

Items
PostPosted: Sat Dec 24, 2005 10:59 pm    Post subject: Re: What is logic, and what is trail and error, backtracking Reply with quote

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
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Mon Dec 26, 2005 4:51 pm    Post subject: Re: What is logic, and what is trail and error, backtracking Reply with quote

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
View user's profile Send private message Visit poster's website
Mark

Joined: 19 Oct 2005
Posts: 30
:
Location: Arizona

Items
PostPosted: Wed Dec 28, 2005 1:27 am    Post subject: Re: What is logic, and what is trail and error, backtracking Reply with quote

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
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Wed Dec 28, 2005 4:57 am    Post subject: Re: What is logic, and what is trail and error, backtracking Reply with quote

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
View user's profile Send private message Visit poster's website
Mark

Joined: 19 Oct 2005
Posts: 30
:
Location: Arizona

Items
PostPosted: Wed Dec 28, 2005 11:17 am    Post subject: Re: What is logic, and what is trail and error, backtracking Reply with quote

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
View user's profile Send private message
weia

Joined: 12 Nov 2005
Posts: 5
:

Items
PostPosted: Mon Jan 30, 2006 7:37 pm    Post subject: Reply with quote

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
View user's profile Send private message
Myth Jellies

Joined: 20 Sep 2005
Posts: 14
:

Items
PostPosted: Sun Apr 09, 2006 6:51 am    Post subject: Reply with quote

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 Confused
_________________
Myth Jellies
Back to top
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Sun Apr 09, 2006 1:06 pm    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
Myth Jellies

Joined: 20 Sep 2005
Posts: 14
:

Items
PostPosted: Sun Apr 09, 2006 11:44 pm    Post subject: Reply with quote

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
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Mon Apr 10, 2006 12:01 am    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
Myth Jellies

Joined: 20 Sep 2005
Posts: 14
:

Items
PostPosted: Wed Apr 12, 2006 12:27 am    Post subject: Reply with quote

[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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku All times are GMT
Goto page Previous  1, 2
Page 2 of 2

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron