"Logic" versus trial-and-error

puffinry · Posted: Tue Aug 09, 2005 11:40 am Post subject: "Logic" versus trial-and-error

In informal discussions of Sudoku, solution techniques are often characterised as either "pure logic" or "trial-and-error".

It leads one to wonder whether there is any mathematical basis for the distinction. Have any of you given the matter any thought?

Robin

dukuso · Posted: Tue Aug 09, 2005 7:41 pm Post subject:

for me it's just the level of lookahead.
From where you are, you could search the searchtree
with deep-first (= trial and error") or with breadth-first
to a certain level and then decide which of the branches is the
most constraint to follow.

Well, we have no normal searchtree here, but alternating
AND and OR :

pick one constraint of your choice
walk through all placements for this constraint
pick ...
walk...
...

so, instead of picking the constraint with the fewest branches
you can search the neighboorhood for the most promising
constraint which gives fewest placements
k-levels in the future.
They call this "logic" then but you might also view it as backtracking
through the neighborhood of your position upto level k.

lookahead with k>2 is typically not very useful. You could just
as well start backtracking with DFS. That involves the risk that
you might pick a thick branch but it spares you the local search.

It makes sense to have larger k near the root and smaller
k near the leaves of the searchtree.

Guenter.

milt boyd · Posted: Tue Sep 13, 2005 1:34 pm Post subject: logic vs trial and error

For me, the distinction is whether the solver has to "back up and try again with some other choice".
If the solver doesn't, but proceeds ever forward (no back-tracking) to ""there is no solution", "this is the unique solution", or "this is a solution, there may be others" or "there are multiple solutions: A, B, ..." then IMO it can be described as "logic".
If on the other hand, the solver notes a partial solution, makes a selection, continues until it can't go further, and backtracks to a previous partial solution, then that is "T&E"

Note that either might be described as brute force, depending on the subtlety of the approach.

Lummox JR · Posted: Wed Sep 14, 2005 11:13 pm Post subject:

One issue with that distinction is that it basically groups forcing chains, Nishio, Bowman bingo, etc. under the label of trial-and-error. I don't think that's an entirely unfair label of course, but they're different than just applying brute force. Perhaps a nicer distinction would be to separate T&E from brute force, where T&E doesn't have to involve guessing so much as an attempt to follow a what-if to a contradiction.

On the other hand, subsets, X-wings, swordfish, fishy cycles, and simple coloring (is that really equivalent to fishy cycles?) are all purely logical. One can surmise that if there's any way to reduce one of the other techniques to a mathematical approach like building a graph, they could be counted in this group as well. Certainly the fact that so many techniques are fairly new is promising in this regard.

Lummox JR · Posted: Thu Sep 15, 2005 6:59 pm Post subject:

You know, I may have to rethink grouping forcing chains under that label. It strikes me there's a way to handle forcing chains in a similar manner to fishy cycles.

Basically if you take the set of 2-row DLX columns you can use each 2-candidate cell as a vertex in which a house-digit constraint forms the edge. (The first vertex is an exception; it may have more than 2 candidates.) From this set of vertices you can build chains; your goal is to find a chain for which the same digit is on both edges adjoining the first vertex. For two vertices to connect they must have a common endpoint cell, which can appear no more than once in a chain. Each chain is a one-way cycle, so each edge has a direction associated with it. Each vertex is also labeled true or false; start with a true value. For each vertex, flip the value from true to false or vice-versa if the vertex has the same digit on both edges. When you get to the end, since the last edge should match the first edge, flip the truth value. If you now have a false truth value, which would be applied to the first vertex since you've come full circle, the first vertex must be both false and true (meaning it must be, and must not be, that digit in order for the chain to hold). Therefore, the digit on both its edges is not a valid choice for that cell.

While laborious, I think this can be reduced to the realm of logic after all.