What is logic, and what is trail and error, backtracking, ed

soduko

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

dukuso

Ruud · Site Admin

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.

dukuso · 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.

dom · 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 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/

dukuso · 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.

Ruud · Site Admin

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

Mark

Moschopulus

gsf

dukuso

gsf

dukuso · 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 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 ?

Mark