
View previous topic :: View next topic 
Author 
Message 
 soduko
 Joined: 10 Oct 2005  Posts: 50  :   Items 

Posted: Fri Nov 04, 2005 11:24 am Post subject: What is logic, and what is trail and error, backtracking, ed 


There are a lot of treads that discuss what is T&E and what is logic
Is it not an idea to have the discussion in one tread. (THIS ONE)
Trail and Error is for this tread at the moment the same as Brute Force, and Backtracking.
(until somebody gives examples that are Backtracking /brute force / Trail & error, but not one of the others)
My own very simplistic working hypothesis of trial & error:
Trial & error will find a solution even if there is more than one.
Logic will not find a solution if there is more than one.
(in the case of less than two solutions you cannot use this hypothesis, and the uniquenesstests are a little fuzzy in this definion)
So I am already ready to trade it in for a better one.
Lets hope that this discussion gets somewhere 

Back to top 


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

Posted: Sat Nov 05, 2005 9:03 am Post subject: Re: What is logic, and what is trail and error, backtracking 


soduko wrote:  Trial & error will find a solution even if there is more than one.
Logic will not find a solution if there is more than one.

well, that's not the point. "Logic" might reduce the
searchspace by reducing the original problem to a
smaller problem with exactly the same set of solutions.
Quote: 
(in the case of less than two solutions you cannot use this hypothesis, and the uniquenesstests are a little fuzzy in this definion)
So I am already ready to trade it in for a better one.
Lets hope that this discussion gets somewhere 
I like Mark's definition with polynomial time behaviour best.
If the technics is extended to larger n, it should only
be polytime(n). Of course, then it won't solve all sudokus. 

Back to top 


 Ruud Site Admin
 Joined: 17 Sep 2005  Posts: 708  :  Location: Netherlands  Items 

Posted: Sat Nov 05, 2005 1:31 pm Post subject: 


IMHO, these are the definitions:
Logic is the foundation for every solving technique. Without it, we would not know what a puzzle is.
Basic methods use logic to make eliminations. They test possible placements against the 4 constraints of the puzzle. All other techniques rely on the basic methods.
Trial & Error only works because it uses logic. What it lacks is a good starting point, therefore it is often confused with a lucky guess.
Exponential methods like tabling, Bowman's Bingo, bifurcating chains, et al, ignore the starting point problem and build a list of implications for every possible move. It is upto the programmer to decide what information to pick from this huge list and use it to move forward.
Focussed Exponential methods like Nishio, coloring and forcing chains limit the implication list by focussing on a certain aspect, conjugate pairs for a single digit, or only cells with 2 candidates. This reduces the time to build the implication tables (now called "chains"), and also makes the technique user friendly, because the paths are pretty straightforward.
Pattern Recognition methods rely on the existence of certain patterns (subsets, XWing, swordfish, uniqueness rectangles). These methods use heuristics. We ignore the full proof, but jump straight to the conclusion, once we find them.
Backtracking uses logic. It is exponential. The only difference is that it does not stop until it has found the complete solution. Where other techniques try to unlock a puzzle piece by piece, backtracking does not stop and allow the user friendliest technique to complete the job.
As for the application, I like to have an array of tools at my disposal.
Backtracking is ideal for generating puzzles, and testing their validity.
The other tools are great to assess the difficulty of the puzzle, and can be used to help a player with hints or a solver log.
Trial & Error seems to fit into none of these categories. It is considerably slower than any other technique used to generate and validate puzzles, and no difficulty assessment can be made with it. That is probably why there is such an aversion against this technique in the programmers community. It's useless for a programmer. (but not for a player)
Ruud. 

Back to top 


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

Posted: Sat Nov 05, 2005 1:43 pm Post subject: 


Ruud,
trial and error is not as useless for programmers as you might think.
These are called "incomplete solvers", and they were the reason
why they went from QCP  instances to QWH instances
for benchmarking the related quasigroup completion problems. 

Back to top 


 dom
 Joined: 10 Nov 2005  Posts: 42  :   Items 

Posted: Thu Nov 24, 2005 1:17 pm Post subject: 


Ruud,
I'm not sure I agree on your definition of "Basic" solvers. It's certainly possible to create a Logic solver which actually solves fairly complex puzzles without resorting to T&E (backtracking etc..) but using more complex rules than naked/hidden singles.
For example the naked triple rule can be encoded in a solver and used logically to attempt to find a solution.
This can actually be fairly quick (right now I can solve 5000 simple puzzles per GHz per second with my pure logic solver). Absolutely no guesses occur, so another added benefit is that the solver will not complete if there are multiple solutions. Also, memory usage is extremely low as you only need to keep track of current values, and current possible values (encoded in 13 bits if you so wish, although I use 2x32 bits for simplicity's sake). Actually, you also need a bit of memory when applying the rules (rule dependent) but this doesn't take up much space for all the humanstyle rules that you're likely to find in humansolvable puzzles.
Also, I think it's worth defining the first solver that people usually come up with as the "brute force" solver. I guess it is just the T&E solution you refer to, but really it's more of a complete search through sudoku space. This is also not entirely slow (23 per GHz per second if you build the possible options with a simple row/column/region elimination round before you start iterating), which is perfectly fine for testing that your sudoku has no multiple solutions etc..
Anyway, just thought I'd add that. _________________ Orangeminds Sudoku
http://www.orangeminds.com/sudoku/ 

Back to top 


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

Posted: Thu Nov 24, 2005 11:44 pm Post subject: 


reading, what I wrote earlier in this thread,
I'd like to redefine T&E as an "incomplete" algo.
One which might find a solution but can't count them. 

Back to top 


 Ruud Site Admin
 Joined: 17 Sep 2005  Posts: 708  :  Location: Netherlands  Items 

Posted: Sat Nov 26, 2005 3:22 pm Post subject: 


dom wrote:  I'm not sure I agree on your definition of "Basic" solvers. 
I did not mean to classify solvers, but the techniques used by them.
Basic techniques deal with detection of naked and hidden singles. All "higher" techniques have the elimination of candidates as a result, with the exception of only a few uniqueness tests and some verities found in tabling. Therefore these higher techniques must rely on basic techniques to take advantage of the eliminated candidates.
Ruud. 

Back to top 


 dom
 Joined: 10 Nov 2005  Posts: 42  :   Items 

Posted: Sat Nov 26, 2005 10:43 pm Post subject: 


Ruud wrote:  Therefore these higher techniques must rely on basic techniques to take advantage of the eliminated candidates. 
Ahhh, yeah, I see what you're getting at then.
Ignore me, compared to your knowledge of the field, I am but a beginner.
Cheers,
Dom _________________ Orangeminds Sudoku
http://www.orangeminds.com/sudoku/ 

Back to top 


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

Posted: Fri Dec 23, 2005 10:17 am Post subject: Re: What is logic, and what is trail and error, backtracking 


dukuso wrote:  I like Mark's definition with polynomial time behaviour best.
If the technics is extended to larger n, it should only
be polytime(n). Of course, then it won't solve all sudokus. 
Eppstein provides a nice proofsketch of this, namely that the socalled "Single Digit Sudoku Deduction" is NPcomplete for the general NxN case:
http://www.livejournal.com/users/11011110/20637.html#cutid1
What's interesting, though, is that the specific 9x9 case may turn out to be solvable solely through polynomialtime methods. Methods continue to evolve, so there's reasonable hope that such a conjecture may in fact be true.
My personal view is that inference chains provide a great deal of promise in this direction. These techniques would be progressive generalizations of Eppstein's graphtheoretic methods, which currently focus only on bivalued or bilocated cells. A more general cell type can be included in candidate chains provided one performs simple, inprocess eliminations in a way that preserves the "conflicting endpoints" idea.
It's also interesting to speculate on how one would gauge progress in solving the 9x9 case. The sheer combinatorics of it appear daunting.
Mark 

Back to top 


 Moschopulus
 Joined: 12 Aug 2005  Posts: 39  :   Items 

Posted: Fri Dec 23, 2005 11:27 am Post subject: Re: What is logic, and what is trail and error, backtracking 


Mark wrote: 
What's interesting, though, is that the specific 9x9 case may turn out to be solvable solely through polynomialtime methods. Methods continue to evolve, so there's reasonable hope that such a conjecture may in fact be true. 
I agree. People are expending a huge amount of effort coming up with new "techniques". Whenever someone finds a 9x9 puzzle that can be only be solved by "guessing" and not by any existing "techniques", people find a new "technique" that solves this puzzle. (Apparently pure backtracking does not count as a "technique" here.) As we come up with more techniques, the number of sudokus that can be solved by techniques increases, and eventually this number will reach the total number of sudokus. Then we can say that all puzzles are solvable by techniques, and not by guessing, But this is only because 9x9 is too small. This will never happen for nxn, and probably not even for 16x16. The gap between the total number and the number that can be solved by "techniques" will increase with n, probably exponentially, although the gap may be 0 for 9x9. 

Back to top 


 gsf
 Joined: 18 Aug 2005  Posts: 408  :  Location: NJ USA  Items 

Posted: Fri Dec 23, 2005 3:44 pm Post subject: Re: What is logic, and what is trail and error, backtracking 


Moschopulus wrote:  But this is only because 9x9 is too small. This will never happen for nxn, and probably not even for 16x16. The gap between the total number and the number that can be solved by "techniques" will increase with n, probably exponentially, although the gap may be 0 for 9x9. 
I believe "too small" is related to the maximum backdoor size. For 9x9 sudoku it looks like this may be 2 using the two simplest constraints. This means that you can construct a 9x9 solver that checks all candidate values for all pairs. One of those pairs will be a backdoor and trivially solve the problem (if the conjecture holds.)
I haven't gone through enough data to conjecture the maximum backdoor size for 16x16 sudoku. 

Back to top 


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

Posted: Sat Dec 24, 2005 2:04 am Post subject: Re: What is logic, and what is trail and error, backtracking 


gsf wrote:  Moschopulus wrote:  But this is only because 9x9 is too small. This will never happen for nxn, and probably not even for 16x16. The gap between the total number and the number that can be solved by "techniques" will increase with n, probably exponentially, although the gap may be 0 for 9x9. 
I believe "too small" is related to the maximum backdoor size. For 9x9 sudoku it looks like this may be 2 using the two simplest constraints. This means that you can construct a 9x9 solver that checks all candidate values for all pairs. One of those pairs will be a backdoor and trivially solve the problem (if the conjecture holds.)
I haven't gone through enough data to conjecture the maximum backdoor size for 16x16 sudoku. 
come on, please give us your conjecture, even if it's built on
waving ground ! It's probably still more profound than our
own estimates...
Is there something known about the backdoor size for QWH ?
The solving complexity of the hardest n*nsudokus or QWHs,
is it proportional to the backdoorsize ? I mean exponentially, 

Back to top 


 gsf
 Joined: 18 Aug 2005  Posts: 408  :  Location: NJ USA  Items 

Posted: Sat Dec 24, 2005 4:37 am Post subject: Re: What is logic, and what is trail and error, backtracking 


dukuso wrote: 
come on, please give us your conjecture, even if it's built on
waving ground ! It's probably still more profound than our
own estimates...
Is there something known about the backdoor size for QWH ?
The solving complexity of the hardest n*nsudokus or QWHs,
is it proportional to the backdoorsize ? I mean exponentially, 
nothing concrete, but a lot of analysis based on "if function f() is a good predictor of backdoor size then then solution complexity is O(...)"
point me to a good supply of 16x16 sudoku/QWH problems
I'll code a brute force NxN backdoor search
it starts with a solver
once a solution is found go back to the original problem and
systematically plug in ituples from the already known solution
start i from 1 and increment by 1 (all singletons, all pairs, etc.)
if any ituple trivially solves the problem then the backdoor size
for the puzzle is i
for a collection of 225,116,397 mostly random 9x9 sudoku including
24K 17's from Gordon about 68.2% were trivially solved, 31.7% had
backdoor size 1, and about 0.02% had backdoor size 2, so I'm guessing
we'll need a pretty big random sample to catch the maximum 16x16
backdoor 

Back to top 


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

Posted: Sat Dec 24, 2005 6:33 am Post subject: 


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.
that O(...) is it secret or copyright by ATT or such ? 

Back to top 


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

Posted: Sat Dec 24, 2005 10:11 am Post subject: Re: What is logic, and what is trail and error, backtracking 


gsf wrote:  This means that you can construct a 9x9 solver that checks all candidate values for all pairs. One of those pairs will be a backdoor and trivially solve the problem (if the conjecture holds.) 
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. 

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
