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 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku
View previous topic :: View next topic  
Author Message
soduko

Joined: 10 Oct 2005
Posts: 50
:

Items
PostPosted: Fri Nov 04, 2005 11:24 am    Post subject: What is logic, and what is trail and error, backtracking, ed Reply with quote

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

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

Items
PostPosted: Sat Nov 05, 2005 9:03 am    Post subject: Re: What is logic, and what is trail and error, backtracking Reply with quote

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
search-space 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 poly-time(n). Of course, then it won't solve all sudokus.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Sat Nov 05, 2005 1:31 pm    Post subject: Reply with quote

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

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

Items
PostPosted: Sat Nov 05, 2005 1:43 pm    Post subject: Reply with quote

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

Joined: 10 Nov 2005
Posts: 42
:

Items
PostPosted: Thu Nov 24, 2005 1:17 pm    Post subject: Reply with quote

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 human-style rules that you're likely to find in human-solvable 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 (2-3 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. Smile
_________________
Orangeminds Sudoku
http://www.orangeminds.com/sudoku/
Back to top
View user's profile Send private message
dukuso

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

Items
PostPosted: Thu Nov 24, 2005 11:44 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Sat Nov 26, 2005 3:22 pm    Post subject: Reply with quote

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

Joined: 10 Nov 2005
Posts: 42
:

Items
PostPosted: Sat Nov 26, 2005 10:43 pm    Post subject: Reply with quote

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. Smile

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

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

Items
PostPosted: Fri Dec 23, 2005 10:17 am    Post subject: Re: What is logic, and what is trail and error, backtracking Reply with quote

dukuso wrote:
I like Mark's definition with polynomial time behaviour best.
If the technics is extended to larger n, it should only
be poly-time(n). Of course, then it won't solve all sudokus.


Eppstein provides a nice proof-sketch of this, namely that the so-called "Single Digit Sudoku Deduction" is NP-complete 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 polynomial-time 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 graph-theoretic 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, in-process 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
View user's profile Send private message
Moschopulus

Joined: 12 Aug 2005
Posts: 39
:

Items
PostPosted: Fri Dec 23, 2005 11:27 am    Post subject: Re: What is logic, and what is trail and error, backtracking Reply with quote

Mark wrote:

What's interesting, though, is that the specific 9x9 case may turn out to be solvable solely through polynomial-time 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
View user's profile Send private message Visit poster's website
gsf

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

Items
PostPosted: Fri Dec 23, 2005 3:44 pm    Post subject: Re: What is logic, and what is trail and error, backtracking Reply with quote

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
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 2:04 am    Post subject: Re: What is logic, and what is trail and error, backtracking Reply with quote

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*n-sudokus or QWHs,
is it proportional to the backdoor-size ? I mean exponentially,
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 4:37 am    Post subject: Re: What is logic, and what is trail and error, backtracking Reply with quote

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*n-sudokus or QWHs,
is it proportional to the backdoor-size ? 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 i-tuples from the already known solution
start i from 1 and increment by 1 (all singletons, all pairs, etc.)
if any i-tuple 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
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 6:33 am    Post subject: Reply with quote

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.

that O(...) is it secret or copyright by ATT or such ?
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Mark

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

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

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 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.
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 1, 2  Next
Page 1 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