The New Sudoku Players' Forum

[Yogi]

In the thread on B E R T JasonLion said "Sudoku can be solved with trial and error alone, which many people argue is not logic. A substantial number of people who solve Sudoku puzzles do so with trial and error, even though we frown on that here." If it's to be frowned on, maybe we should carefully define it.

.9.....5.2758961436.45.7.9...2.8.56...91...7..4.....3.9.7..2.8.42.9...1....4...2.
Here, r34c2 is a Locked 1,3 Pair, and r3c5 is also 13. What happens when we look at these two possibilities?
1r3c5 => 1r9c6 => 1r7c2 Not Possible. So r3c5=3 and the puzzle is quickly solved.
BTW, what’s the hieroglyph for “Not Possible” ?

I think of this process as Chaining and I do it all the time, but is it getting too close to Trial And Error to be allowed in this forum? In my opinion this is equivalent to a Strong Link: If you can show that one case is false, the other must be true. I find this process to be not only simple, but also both scientific and logical.
But perhaps most importantly for me, I DON’T need a computer or solver program to do it.

Yogi

[Leren]

Whatever your way of thinking is, the 13 locked pair removes the 1 and 3 from r7c2, making the 1 in r7c5 a single, so r3c5 <> 1 = 3 and the puzzle is solved.

That is just a basic move, I don't see this as a contradiction. Of course, you could turn it into one by saying that if r3c1 = 1, r7c5 <> 1 and there are no 1's in Row 7.

You can often turn a constructive proof into a "contradiction".

Leren

[JasonLion]

Yogi, it would be a big help if you tried to use standard terminology. It sounds to me like you are trying to talk about Bifurcation.

[Yogi]

Yes it seems I am talking about Bifurcation, but it still feels like "What if?" to me.
It's only a label, but I will try to remember that that's what you call it.

So how would you define the Trial & Error that you would discourage?

And thanx for the observation.
I might have eventually noticed that simplification, but I was primarily looking for an illustration for my post on bifurcation.

[David P Bird]

Here's my stab at summarising the various solving approaches.

1. Guessing = using an assumption that can only succeed if it results in a contradition.
2. Pattern recognition = looks for pre-analysed patterns that produce eliminations
3. Two-case logic = finding eliminations that are common to two rival cases
4. Multi-case logic = finding eliminations that are common to all possible cases.
5. Branched logic = whenever an inconclusive position is reached using case logic, branching by adding sub-cases to explore.

Of these 2 and 3 are considered the most elegant and acceptable although some pattern deductions can only be proved using branched methods. However these patterns are accepted when they are common enough and are recognisable.

These different methods can be used in various combinations some of which have popular names.
For example
Pure bifurcation repeatedly splits a puzzle into sub-puzzles only one of which will eventually survive
Net-working branches all consequences of a two case starting position combining the inferences that result from different paths.
Templating examines all the possible ways a digit or combination of digits can be configured to eliminate the impossible ones.

'Brute Force' is generally used to describe a method when it is purely mechanical and can be applied without thinking.
'Trial and Error' is a terrble term as all solving methods depend on this to some extent. However it usually implies that little thought is needed in the way a method is applied.

DPB

[JasonLion]

There is no generally agreed upon definition of brute force, despite lots of debate. Some people have tried to define it in terms of logical/illogical (guessing is illogical). However, it turns out to be possible to specify logical techniques that are equivalent to guessing. This debate resulted in the invention of several techniques with "very little" guessing, which seems to have muddied the waters further. I suspect that there may be a definition possible using computation complexity arguments, but a proper formulation has eluded me. Besides, computation complexity can be difficult to evaluate, and thus would be somewhat impractical even with a proper definition.

[David P Bird]

Jason, pondering your point about computational simplicity:

Excluding those that are designed for speed, a computer solvers should demonstrate methods which a human player could use to solve a puzzle preferably without using reams of paper. Surely this must put a huge constraint on the selection of computationally simple/efficient methods? Would you include some measure about the probabilty of success in the mix? If so the waters get very murky indeed.

With a computer it's easy to iterate all the possibities using nested loops for example to find fish and multi-fish, but a human player would only explore these options via different routes if there was a clear indication that a promising pattern existed in a puzzle. A good example of this is puzzles with SK loops that produce multiple eliminations which are recognisable by experienced players.

Another point is that experienced player will develop an eye for the potential weak points in a puzzle. A single sided assumption (a guess) could then be enough to open a puzzle up. Considering the possible gains it seems this seems an entirely rational approach (and I'm sure Eleven will be pleased to hear me say that). However what our notations lack is any sort of justification for the choice of the start points for our different methods so suspicious minds will assume the worst.

These points cover how experienced players are able to shorten and simplify an overall solution by adopting a tagetting strategy. This is somthing that, as yet, no computer solver does because it would require some sort of Artificial Intelligence that would skyrocket the computational complexity!

In general I agree that it's very unlikley a forum debate on any subject will ever reach an definite agreement but nevertheless over time a popular view seems to emerge.

David

[Pat]

an old discussion --
The continuum of Sudoku logic

[JasonLion]

Excluding those that are designed for speed, a computer solvers should demonstrate methods which a human player could use to solve a puzzle preferably without using reams of paper. Surely this must put a huge constraint on the selection of computationally simple/efficient methods?

With a computer it's easy to iterate all the possibities using nested loops for example to find fish and multi-fish, but a human player would only explore these options via different routes if there was a clear indication that a promising pattern existed in a puzzle. A good example of this is puzzles with SK loops that produce multiple eliminations which are recognisable by experienced players.

Human solving emulation does indeed constrain things, but I am not sure how useful this constraint is in practice. Humans are very good at certain kinds of pattern matching in ways that computers are typically very bad at emulating. That lack of correspondence makes it difficult to "prune" the set of computer techniques you need to explore to develop equivalents to human solving techniques. Your example with SK loops is good. Humans seem to be good at looking at looking at a broad situation and zeroing in on a few specific points that are worth exploring further without exploring the entire space of all possible methods. Our computer emulations of that ability tends to use approaches, for example exhaustive search, that on the surface would appear to be ruled out when considering only human style solving techniques.

Would you include some measure about the probabilty of success in the mix? If so the waters get very murky indeed.

Computational Complexity Theory does not take probabilities into account. It focuses on worst case performance, and essentially ignores average case and best case situations. There has been some relatively recent theoredical work on distinguishing typical case performance from worst case performance and trying to optimize for typical case instead of worst case, but that is technically outside the domain of computational complexity as I understand it. Obviously this focusing on real world situation performance is done all the time in practical situations, but it has proven to be very complex to deal with at a theoretical level.