The New Sudoku Players' Forum

[gsf]

I can't see any relation between your question and what precedes it.
You obviously know that NS and HS are resolution rules.

you asked

Do you know any situation in which using depth one T&E would be meaningful?

I replied in the affirmative using { naked-singles hidden-singles }
you balked
I then asked about singles to make sure we were addressing the same issue
we weren't
you didn't really mean any situation
you meant human solving situation

note that my post was qualified with typically used to classify hard puzzles
I wasn't proposing a solution technique, just answering the question

[ravel]

I just wonder whether BFS, with all the memory it requires, is humanly feasible (unless we are very close to the solution).

Sorry, if i'm OT (i'm very busy and dont have time to read all carefully).
In the hardest thread i saw some impressing manual solutions by Carcul and Maria, which (also) have been called brute force solved. But there are some differences to the usual (fast) computer methods. At least i had the impression that
- before they tried a "t&e move", they studied the puzzle carefully, in a complex (and personal) way, a program wouldn't be able to.
- as a result the candidate(s) they tried to eliminate were well selected (at least both for the chance to prove an elimination and that - if successful - the move would be effective for the further solution) and they did not waste more time for the majority of candidates. A program normally is dumb for that.
- though i am sure, that not all tries were successfull, from the short time they needed they could not have many "errors"
- the harder the puzzles were, the more both used level 2 "t&e" moves (also when level 1 moves still were available). This is very logical for me, why should they stop on the half way (2 case distinctions in an easier grid are faster to check than to start new)
- their solutions can be followed by any humans, who take the time to do it (but it is not said, that this is always a thrilling job - this probably is the reason, why no one solved the hardest known manually - its hard work and no one would read the solutions).

[denis_berthier]

In the hardest thread i saw some impressing manual solutions by Carcul and Maria, which (also) have been called brute force solved. But there are some differences to the usual (fast) computer methods. At least i had the impression that
- before they tried a "t&e move", they studied the puzzle carefully, in a complex (and personal) way, a program wouldn't be able to.
- as a result the candidate(s) they tried to eliminate were well selected (at least both for the chance to prove an elimination and that - if successful - the move would be effective for the further solution) and they did not waste more time for the majority of candidates. A program normally is dumb for that.
- though i am sure, that not all tries were successfull, from the short time they needed they could not have many "errors"

If the kind of knowledge they are using to do this could be formalised, a program could simulate it. This is what we usually call heuristics in AI.
But I've never seen anything written about such knowledge.

I personally consider my SudoRules solver as a testbed for new rules, as a tool for studying which rules have the best relative "return on investment" (wrt to the % of puzzles they may solve), not as a goal in itself or a competitor for human solvers. It'd be interesting to de-activate some of the complex chain rules and to complete it with knowledge for guiding T&E - it'd allow testing this knowledge.

- the harder the puzzles were, the more both used level 2 "t&e" moves (also when level 1 moves still were available). This is very logical for me, why should they stop on the half way (2 case distinctions in an easier grid are faster to check than to start new)

It seems that some people consider stopping T&E at depth 1 as a possible technique. But, I'm like you, I can't see the rationality behind that.

- their solutions can be followed by any humans, who take the time to do it (but it is not said, that this is always a thrilling job - this probably is the reason, why no one solved the hardest known manually - its hard work and no one would read the solutions).

I heard that, in the competitions, brute force (probably guided by the kind of careful selections you mention) is generally used, because it is faster than trying to find complex patterns.

So, why bother about finding rules that will avoid using brute force (except on very rare puzzles)?
I think you give the answer: "no one would read the solutions". Sudoku would be boring.
Finding a "pure logic solution" is finding a mathematical proof of the solution. It may be longer than using T&E, especially for hard puzzles, but it makes it easier to explain it.

[gsf]

It seems that some people consider stopping T&E at depth 1 as a possible technique. But, I'm like you, I can't see the rationality behind that.

I'm a proponent of using depth as a measurement technique
how is stopping T&E at depth n any more/less rational than stopping at chain length m?

[denis_berthier]

I'm a proponent of using depth as a measurement technique
how is stopping T&E at depth n any more/less rational than stopping at chain length m?

I think the two matters are very different.

Depth in T&E can be defined as a measure only wrt to a predefined set of rules.
Easter Monster has depth 2 wrt Singles but depth 1 wrt to the rules in your solver or in SudoRules. It will have depth 0 wrt to an extended set of rules if we find a "pure logic solution" (maybe Darryl's ?).
When you have chosen a set S of rules and you define depth wrt S as a measure, if you want to be able to compute this measure for any puzzle, you can't put an a priori restriction on the depth of T&E - unless you have proven that all the puzzles have depth bounded by 2 (or 3 or 4).
If You consider only Singles, we know that depth can't be limited to 1.


Anyway, what you are referring to is a best case analysis of T&E. T&E is usually not used for measuring depth but for solving puzzles. In this case, you can't put an a priori restriction on its depth.


For chains, who said we have to stop at chain length m?
As any real chain has a well defined length, choosing to look for chains with shorter lengths before longer ones is a perfectly rational strategy (although not the only one possible), which leads to another type of classification. For this, you don't have to put an a priori bound on the lengths.

[gsf]

For chains, who said we have to stop at chain length m?

sudorules?

[denis_berthier]

For chains, who said we have to stop at chain length m?

sudorules?

In SudoRules, short chains are looked for before longer ones. For practical purposes, nrczt chains have been coded "only" up to length 20, but I've never seen such a long one (I think the longets I got is 16). Indeed 99,84% of the random minimal puzzles are solved with rules of length <= 7. So we can't really say that 20 is an a priori bound.

In any case, limiting the depth is very different with T&E. If you limit the depth a priori, you loose the only valuable thing in T&E: the guarantee of finding a solution.

[gsf]

In any case, limiting the depth is very different with T&E. If you limit the depth a priori, you loose the only valuable thing in T&E: the guarantee of finding a solution.

I still find it hard to tell whne you're wearing your "pure path logic hat" vs your "rationalization" hat

you lose the same thing with limits in sudorules
if there is a puzzle just beyond the rule limits you get no solution either

and you get about the same random solution coverage with depth 1 T&E vs logic
so there is no difference adding artificial limits to either logic or T&E based algorithms
except that with T&E on sudoku limits don't really affect solution time
whereas limits for sudorules (or e.g. for X/Y cycle length in othe logical solver like mine)
can have a non-trivial affect on running time

it basically comes to an aversion to T&E based on the esthetics of logic solution vs T&E solutions
that's fine
I have the same aversion when it comes to solution paths to be consumed by humans
but there's much more to sudoku than that
but apparently not in this thread
I won't bug you any more

[denis_berthier]

gsf
The lentgh of a chain cannot be compared to the depth of T&E.
You already suggested such equivalence but it does not hold. Looking for a chain is not T&E (as defined above).
A chain of given type and length is a pattern, exactly like Swordfish or Naked Triplets. When you've found one, you have proven that an elimination is logically justified and you never have to re-assert the candidates you've eliminated.

My approach is definitely human oriented, I said it from the beginning.
I consider SudoRules only as a research tool that helps me find the most promising resolution rules and evaluate their efficiency.
Having a separate rule for each chain type and length is very useful if one wants to test different priorities on the rules. And it causes no efficiency problem, thanks to the longstanding AI techniques used.
If you mean I'm not approaching Sudoku from your programmer POV, I completely agree. I understand that optimising a solver may be an interesting topic, but it's not mine.

[RW]

A chain of given type and length is a pattern, exactly like Swordfish or Naked Triplets. When you've found one, you have proven that an elimination is logically justified and you never have to re-assert the candidates you've eliminated.

Would you have to re-assert candidates eliminated by T&E? You keep repeating that pattern based solving is logical and gives a mathematical proof for the solution while T&E doesn't. As long as you keep the "E" in T&E and don't resolve to T&S (trial and solution) the proof is just as water-tight as any pattern based solution.

I just wonder whether BFS, with all the memory it requires, is humanly feasible (unless we are very close to the solution).

As you said, most puzzles solve with chains of length <=7, that doesn't require superhuman memory. I've solved many extreme puzzles without pencilmarks, without any other marking up, keeping the chains and implications in my head. Usually the problems with memorizing starts after some 20-30 memorized cells, depending on the puzzle. By grouping the memorized cells into larger patterns I can go on and memorize a lot more, even solve whole puzzles before writing in a single digit.

In the hardest thread i saw some impressing manual solutions by Carcul and Maria, which (also) have been called brute force solved. But there are some differences to the usual (fast) computer methods. At least i had the impression that
- before they tried a "t&e move", they studied the puzzle carefully, in a complex (and personal) way, a program wouldn't be able to.
- as a result the candidate(s) they tried to eliminate were well selected (at least both for the chance to prove an elimination and that - if successful - the move would be effective for the further solution) and they did not waste more time for the majority of candidates. A program normally is dumb for that.

If the kind of knowledge they are using to do this could be formalised, a program could simulate it.

I believe my method for choosing what candidates to eliminate is quite similar to Carcul's and Maria's, even though they otherwise worked in a very different way. When solving, I'm constantly looking for different implications in the puzzle. As there is no pm's to look for patterns in, I just look ahead a few steps on what would happen if certain cells had certain values. This probably sounds as T&E as possible, but I don't see it as any different than making notes of strong/weak links and connect them to short chains. After all, it's exactly the same thing, but without the notation. Sometimes contradictions are found already at this stage, which I otherwise regard more as reading and understanding the puzzle than trying to solve it. Sometimes I notice connections between different implications and might solve something based on that.

If I get really stuck, then I often choose a target cell to solve. For this I look for a cell with as few candidates as possible, where every possible candidate immediately solves several cells (or a unit where a digit may go in as few cells as possible and every possible placement for the digit immediately solves several cells). By choosing the cell like this I make sure that solving the cell will advance the puzzle. As all possible candidates immediately advance the puzzle, I also have a good beginning for the chains to eliminate the extra candidates. Sometimes one of the paths might lead to a dead end after a few solved cells (no contradiction and no more immediate solved cells), if this happens and I'm determined to solve the cell I go on with deeper level T&E. But I don't want to do nested chains if they can be avoided, because that forces me to not only memorize the values for each solved cell, but also which of the chains solved the cell. Picking a cell to solve and sticking to that decision has it's pros and cons. Usually it leads to fewer, but longer chains.

Essentially, I think Carculs method of choosing starting points for his chains is quite similar to mine. Of course, he doesn't look for "cells where all candidates solve a lot of singles", but cells where all candidates make implications on the rest of the puzzle by strong/weak links, which again is exactly the same thing but with notation.

RW

[Mauricio]

Rationality is a strong and subjective word.
As far as I have understand, the following is a resolution rule (and hence should be rational):

• Particular puzzle==>Particular solution

But at the same time, it can be thought as we used T&E at depth 81 to get the same result.

[denis_berthier]

Mauricio
puzzle ==> solution is at best a function, not a resolution rule.
It doesn't tell you what to do in any precise situation.

[Mauricio]

puzzle ==> solution is at best a function, not a resolution rule.
It doesn't tell you what to do in any precise situation.

It does, it says that when the puzzle is exactly that puzzle, then the solution is that solution. It is the same as (2d) chains, you do not know that you can always apply it, and so it does not tell you what to do in any precise situation.

Edit: Or I misunderstood your meaning of "any precise situation". It has at least two meanings:

• Any precise situation= Any puzzle situation. That is covered above.
• Any precise situation=Any situation that qualifies for the rule. Then my rule obviously tells you what to do in the situation that the puzzle is exactly the puzzle given, then the solution is exactly the solution given
  

[denis_berthier]

Would you have to re-assert candidates eliminated by T&E?

Yes, of course, you would. When you tentatively assert a value and this leads to a dead end (i.e. a puzzle with no solution), you have to "backtrack" and delete the last hypothesis (and re-assert the candidates it allowed to delete). You never do this with pattern based rules.
In order to be able to do this, you also need a mechanism (copying the grid,…) that keeps track of the all the modifications done when you tried a value. And these mechanisms must work recursively.

You keep repeating that pattern based solving is logical and gives a mathematical proof for the solution while T&E doesn't. As long as you keep the "E" in T&E and don't resolve to T&S (trial and solution) the proof is just as water-tight as any pattern based solution.

Real T&E, unless you limit it to depth 1, will always give you a solution (if there is any).
I never said that T&E is "illogical" in the common sense of this word. Full T&E (I mean even if you don't limit the depth - what you call T&S) is a perfectly valid algorithm.
Usually, what we want in math is not only a proof but an illuminating proof. You can call this esthetics, as gsf did. No mathematician would deny it. I think the search for new rules in Sudoku pertains to the same quest. Few people would be satisfied with a T&E solution and they want what is often called a "pure logic solution". No precise meaning has ever been given to this expression.
My claim is that resolution rules provide such a precise meaning.
And my T&E theorem shows that this concept also provides a means of excluding T&E.

But the difference difference between resolution rules and T&E is not only abstract esthetics:
- using resolution rules is exactly like searching a proof of a theorem; once you find the proof, you can completely forget the paths you tried and that led to nothing;
- in T&E, dead ends always remain part of the proof.

I've solved many extreme puzzles without pencilmarks, without any other marking up, keeping the chains and implications in my head. Usually the problems with memorizing starts after some 20-30 memorized cells, depending on the puzzle. By grouping the memorized cells into larger patterns I can go on and memorize a lot more, even solve whole puzzles before writing in a single digit.

That's great. I'm obviously unable to do this, but I'm not a good player.
Did you try to find xyt or nrct chains this way? I think, with such good memory, it'd be an interesting exercise and I'd like to have your opinion on how easy it is for you to find them.

For the rest of your post, thanks for taking time to explain all this.
Seems very interesting but not very easy to formalise. Maybe that's why we are not computers. I'll need more time to think about it.
BTW, I don't consider the search for a pattern as being T&E (at least not in the sense I use in this thread: a well defined resolution technique, acting on the basic elements: values and candidates).

[RW]

In order to be able to do this, you also need a mechanism (copying the grid,…) that keeps track of the all the modifications done when you tried a value. And these mechanisms must work recursively.

And if you are looking for very long chains, you don't need a mechanism to keep track of all the links? This mechanism might be your own memory, or a sheet of extra paper. Now, what is the difference if the solver starts writing:

[r2c7]-5-[r8c7]=5=[r7c9]=4=[r7c2]...

or

if r2c7=5 => r8c7<>5 => r7c9=5 => r7c2=4...

or if the solver just makes a mental picture of the situation with the digits inserted in the cells like in the second chain?

I believe the only real difference between T&E eliminations and other chains is the way you look for them. Any T&E elimination may be traced back and then written as a chain. How does that make it any more logical/valid? Take for example the XY-wing. You say "A={12}, B={13}, C={23} => D <> 3", I say "if D=3 => B=1 & C=2 => no possible candidate in A => D<>3". All eliminations we make, using any technique, are because "if that candidate is true, then there would be a contradiction elsewhere in the puzzle". The cells we need to consider to reach that contradiction may be defined as a pattern. Isn't this then the most basic logic in sudoku solving? The one simple rule from which all other techniques can be derived.

Did you try to find xyt or nrct chains this way? I think, with such good memory, it'd be an interesting exercise and I'd like to have your opinion on how easy it is for you to find them.

XY-chains are the hardest to find for me. I'm not trying to memorize all possible candidates for all cells, so I cannot see it as a chain of cells with only two candidaes. For me it would be a chain of nothing but naked singles (if A=x => NS => NS => NS => ... => contradiction), which are a lot harder than hidden singles to spot. I suspect xyt chains would belong in this same category. Haven't studied your other chains yet, cannot say whether I've used them or not. In general I've found that the chains I use are very different from those who use pencilmarks. My chains usually use more hidden singles, locked candidates and hidden subsets than naked singles.

RW