The New Sudoku Players' Forum

[Myth Jellies]

Some rather strong statements regarding the confluence properties of theories involving the axiom of Uniqueness. Needless to say, I think they are quite misleading.

One unpleasant property of the rules based on the axiom of Uniqueness is that any theory which contains any of them looses the confluence property.

Unfortunately, this proclamation may be based on an incomplete picture of what the Uniqueness assumption really brings to the table. Lets look at Denis's definition of confluence...

Definition: a resolution theory T has the confluence property if any two partial resolution paths can be completed to meet at a same knwoledge state.
Consequence: if a resolution theory T has the confluence property, then for any puzzle P there is a single final state and all the resolution paths lead to this state. In particular, if T solves P, you can't miss the solution by choosing the "wrong" rule at any time.

There is nothing wrong with Denis's definition and consequences. In fact I will use them to show that Uniqueness preserves the confluence property.

Many experts know that you cannot "destroy" a uniqueness deduction. In order to understand why that is, you have to understand what it is that Uniqueness is bringing to the table. Consider a UR in cells r12c34 which haven't been given as initial solved cells in the puzzle. What uniqueness actually tells you is that for any two digits, a & b, you cannot have a total of four a's and b's in those four cells. This is a prescription for a "weak link" for any two situations that together would imply four a's and b's in the cells. For example, there is a weak link between two a's in the cells and two b's in the cells. There is also a weak link between three a's and b's in three particular cells and either an a or b in the remaining cell. This is quite similar to two candidates representing the same digit inhibiting each other if they lie in the same house. Thus, uniqueness should be treated in the same way pattern-wise or theory-wise as the weak links in an xy-chain, etc.

These weak links are all that uniqueness is bringing to the party. So if these weak links exist both at the initial state of the puzzle and at the single final state of the puzzle then one has to conclude that uniqueness preserves the confluence property. The fact is that a puzzle with a unique solution must obey those weak links every step of the way, up to and including the final solution; and we must therefore conclude that theories using the Uniqueness axiom can preserve confluence (i.e. it won't be the uniqueness axiom that is responsible for any lack of confluence.)

[denis_berthier]

I can see that you start using my concepts. Good.

But confluence is defined as a property for a resolution theory, not for a rule.

Which resolution theory are you discussing? Which logical formulation of UR are you using in this theory?
Indeed, I'm not interested by uniqueness. I've just once given the example of a BUG that disappeared after some rule had been applied before it.

And about misleading anybody, why are you still unable to provide the example of an AIC built on non existent candidates - as requested in this thread: http://forum.enjoysudoku.com/viewtopic.php?t=6321

Do you think you can evade this question just by opening a new thread on the same underlying topic?

[champagne]

we must therefore conclude that theories using the Uniqueness axiom can preserve confluence (i.e. it won't be the uniqueness axiom that is responsible for any lack of confluence.)

I would not spend to much time on that topic, but I will temperate your statement.

Either the puzzle is valid (one solution) and, if the confluence means you find the solution, which is more or less the final wording of Denis, you'll get it with or without uniqueness,

or the puzzle is not valid and you change your supplier.

Another point is what you want to do. If you are dreaming of a pure construction (which criteria??) your can forget all forms of Uniqueness.

If you claim to approach in a solver what a human player can easily do, you are better off using the most common forms of UR patterns, what my solver does.

But I would feel as confortable without UR.

[champagne]

Hi Myth,

I forgot to notice a trivial point

Code: Select all

{1 2} --------- {1 2}
  :               :
{1 2} --------- {1 2 3}

(all 4 cells in exactly two rows, two columns and two blocks)

and by the conclusion that 3 can be asserted in the rightmost bottom cell.

Suppose we add UR1 to T.
Suppose this patterns appears at some point in the resolution process of a puzzle P but, for any reason, rule UR1 is not applied immediately (e.g. because you haven't seen it). If any candidate in any of the other 3 cells is eliminated by any other rule in T, then, using ECP and NS, these 3 cells are reduced to one candidate and the 4th cell is reduced to {1 3} or {2 3}.
What remains is the mere pattern of bivalue cell, for which there can exist no resolution rule able to eliminate 1 or 2.
q.e.d.

This is completely FALSE, but Denis will dislike the reason.

The UR is reduced to something as

Code: Select all

1    2
2    13  that's fine

.

One rule still apply to kill 1 in the cell 13. . . Uniqueness.

This is still a UR pattern. Nobody told a cell having only one candidate can't contribute to the logic.

If one dislike adding candidates, you get the same result defining downgraded URs.

The generic rule in URs is that any move that put you in a UR configuration (only the two digits remaining as candidates) is not valid.

Here '1' in the cell 13 would create the forbidden pattern.

That's it.

champagne

[David P Bird]

Suppose in a partially solved grid we have a rectangle of cells in two boxes containing
a b
b axyz
where none of the singles is a given. The final cell can't hold (a)

We can say with certainty that there is only one way this rectangle can be resolved with respect to (a) and (b), because if it were non-unique, no other method would have been able to resolve the singles we've already got.

Applying the concept that the same final solution will be reached regardless of order in which deductions are implemented, we can then say given another route we could have reached a classic AUR configuration. At that point, had we assumed a unique solution for these cells, we could have eliminated that (a). However now we've proved its uniqueness, we don't have to assume it, we know it, and can make the elimination anyway.

Note that this line of logic makes no assumptions about whether there is a unique solution for the puzzle as a whole, but just concentrates on (a) and (b) in the four cells in question.

See the "Avoidable Rectangle" entry in Sudopedia

[champagne]

Hi David,

I like very much your point.

It is still implicitely using Uniqueness as background. The major difference as you say is that unicity has been established thru prior fixings ;

(single candidates could be given as well).

champagne

[champagne]

why are you still unable to provide the example of an AIC built on non existent candidates -?

I don't know if Myth has examples, but if you have a look on some solutions given by my solver, you'll have plenty of them.

The reason is very simple (and has been seen long ago by ronk).

My solver locate all clearing chains appearing at the same time.

The solution delivers clearings in a specific order, so it comes frequently that an AIC is using a candidates (a tag) cleared just above.

champagne

[coloin]

Yes David.

We are not assuming uniqueness at all.

We are saying that it cant be "x" because if the pattern produced is a UR pattern [unavoidable set] this needs a given clue in one of the relevant cells - to define which "iteration " it is. It hasnt [got a clue in it], therefore it cant be "x".

This "proof" is no differnt from hidden single logic, to X-wing to long double region chains [whatever they are] logic.

ie it cant be "x" because it would give an invalid solution therefore it has to be "y".

The invalid solution would be produced by the subsequent insertions I think you will find. [I doubt many would bother but if you were denis you could ! and it would be completly "logical"]

If we were able to know what unavoidable sets WERE NOT in our solution grid then we could make clue insertions everywhere in the puzzle - but we dont tend to know this. Only simple unavoidable sets tend to be visable to most.

These unavoidable sets ARE NOT in the solution grid to our puzzle. If they were they would have a clue in them. [which they dont]

C

[ronk]

Code: Select all

{1 2} --------- {1 2}
  :               :
{1 2} --------- {1 2 3}

(all 4 cells in exactly two rows, two columns and two blocks)

and by the conclusion that 3 can be asserted in the rightmost bottom cell.

But Denis didn't post that in this thread. Why in the world would you post a response over here

[champagne]

But Denis didn't post that in this thread. Why in the world would you post a response over here

to avoid any pollution in Denis's thread as he asked me

[ttt]

Hi champagne,
I’m studying your Full Tagging…
As Denis’s NRCZT, most (or all) of Solver programmer can solve most (or all) puzzles but all solutions that elegant solved by HUMAN… Please, think about that.

BTW, Myth… that is one of my MENTORs…

ttt

[champagne]

Hi ttt,

I’m studying your Full Tagging…

If you are already user of AICs, you should not face difficulties. I hope you'll find thru it ways to improve your skills.

I'll help you if you have difficulties understanding any point.

most (or all) of Solver programmer can solve most (or all) puzzles

This is far from being true if your exclude T&E.

Some days ago, I would have claimed that mine could solve all known puzzles. To-day 2 are missing. Happily Allan Barker have clues to pass that diffculty.

but all solutions that elegant solved by HUMAN… Please, think about that.

Yes you are right and I follow as much as possible what they are doing to catch new ideas. This is for the time being my main field of investigations. (I have also now to work on Allan logic)

As I wrote recently, human players have an unlimited set of rules and it would be a huge investment to introduce them in a solver.

But don't underestimate what solvers can propose. I have examples of nice moves found by my solver. Each one can learn from the other.

Happily for the players, they should stay far in advance of solvers capabilities.

champagne

[DonM]

But don't underestimate what solvers can propose. I have examples of nice moves found by my solver. Each one can learn from the other.

Okay, you lost me there. That statement seems to infer that your solver came up with some 'nice moves' on its own as if it has some sort of 'learning AI' going on, or in other words, has come up with some sort of innovative use of a technique unknown to the human solver which now can be learned by the human solver. AFAIK, any 'moves' that present computer solvers come up with are still a product of the programmer. ttt's premise is, in so many words, pointing out that it is the innovation of the human solver, still relatively impossible with present computer sudoku solvers, that makes human solutions so elegant.

I mention this because, although apparently a lone voice in the wilderness, while the discussions of computer solver output are useful, I have already seen how, with one particular individual, there is the inference that the advanced sudoku theory using massive computer output as examples is relevant to the typical day-to-day human solver. This premise can be particularly misleading and/or confusing to a newer human solver who doesn't yet have the knowledge to distinguish methods that are realistically useful to learn vs. those that aren't.

[David P Bird]

Thanks for the for the reception everyone (I feel a bit like an interloper here)

Champagne I'm pretty certain the logic fails if any of the singles is a given because that’s part of their raison d’être - if a puzzle contains such a rectangle, one of its cells must be a given.

Colin, at first I thought your explanation was better than mine, but an unavoidable set can be roughly defined as the minimum set clues needed to reduce a puzzle to a single solution and lo and behold we're back to uniqueness!

Therefore I've had another stab at this:

1. An AUR is a rectangle of four cells contained in two boxes which contains no given, and which can possibly be fully occupied by two digits in two ways.

2. As soon as one of the cells of an AUR is assigned, this ambiguity is broken and it becomes an "Avoidable Rectangle" (Ugh!).

3. In an AR, we can eliminate any candidate which would lead it to being reduced to holding just two digits.

Proof: If the AUR has alternative solutions there would be no way to prove an assignment to any of its cells. The assignment in the AR proves that this is false, which requires a third candidate to be involved.

This reasoning doesn't depend on any assumptions regarding uniqueness elsewhere in the puzzle.

[champagne]

But don't underestimate what solvers can propose. I have examples of nice moves found by my solver. Each one can learn from the other.

Okay, you lost me there. . . .

Hi DonM,

Difficult subject, especially for me, non native English speaker, having an additionnal risk of having misunderstood your points(and ttt's).

I will start from the end:

New players have for sure difficulties compared to first players. Is it a solver issue? I don't believe that. Newspapers, forums are proposing tougher and tougher puzzles because most players are requesting such puzzles. Newcomers have to fill the gap quickly and to find the way to do it.

If you visit my web site, you'll see that the main part of the methodology (especially in the french version) is a learning tool for beginners in tagging. Most of them will not pass my level one and a very small number will reach levels 2 and 3.

I will keep out of that post higher levels which are not (for the time being) in the field of players out of a small number of experts.

The corresponding set of rules is very limited and very simple. Finding AICs and nets of AICs remain difficult and there the computer brings something. No need for AI. The quality of the solver is to cover the entire field and to bring in some examples of use.

For sure, my solver does what I ask him to do. He is much more reliable than I can be, so I learn a lot from what he finds,

To meet you on some limitations, Human have produced a lot of sophisticated way to fight again puzzles. If I am right, the "fish" thread has some 100 pages and I have been lost after ten. Same with nearly every way to clear candidates. I limited strictly my solver to basic patterns.

This already more than I wanted to write on that topic. But I could not just ignore your post

champagne