On the Confluence of Uniqueness Theories

Advanced methods and approaches for solving Sudoku puzzles

Postby coloin » Wed Sep 17, 2008 1:29 pm

I think we are saying the same thing !
except
David P Bird wrote:an unavoidable set can be roughly defined as the minimum set clues needed to reduce a puzzle to a single solution
I think you are mistaken
a set of clues all of which are essential to define a grid solution is called a [minimal] puzzle

An example of an Unavoidable Rectangle with 4 clues is an example of a 4 clue unavoidable set.

If a solution grid has one of these unavoidable rectanges with 4 clues you can bet your mortgage on the fact that every valid puzzle from that grid solution has one of those 4 clues as a given.

This is an unavoidable set.

There are thousdands of unavoidables in a solution grid- its a wonder that we ever get puzzles with less than 20 clues - but there are so many puzzles in any one grid- that it happens quite often.

A potential UR is an unavoidable set that occurs in any of the grid solutions revealed if you removed a clue from a minimal puzzle. [not recommended] These unavoidable sets will directly conflict with the removed clue and cannot be part of the solution grid of the original minimal puzzle.

So if you see a UR there will be a conflict, you are not assuming that the puzzle is unique, if the 4 clues of the UR are inserted [any of the 2 ways]there will be an invalid grid solution if you try to complete the puzzle.

C
coloin
 
Posts: 1629
Joined: 05 May 2005

Postby DonM » Wed Sep 17, 2008 1:42 pm

champagne wrote:
DonM wrote:
champagne wrote: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)...

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

champagne


Appreciate the response. I think you're right when you suggest that a language difference may make it difficult for each of us to understand each other's points, given the nature of the subject.
Last edited by DonM on Wed Sep 17, 2008 4:52 pm, edited 1 time in total.
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby David P Bird » Wed Sep 17, 2008 2:15 pm

Colin, there's no doubt were in accord on the main idea but I had worries about pinning down a tight definition.

I accept I've misused the "unavoidable set" term but I think my reasoning is still sound but badly described:

Assume we have a solution which contains a UR, and we want to compose the givens to turn it into a puzzle. To make it reduce to a unique solution we must provide one of the 4 cells (its "unavoidable set") in the "minimal puzzle" givens right? (Just to confirm that I've got into step with you on these terms.)

Now suppose we don't do this, and leave that given out. We end up with a puzzle with two solutions. Now Denis doesn't want to assume that the set of givens is sufficient to produce a unique solution which is exactly this scenario, and the one I was trying to steer around. Sorry that I didn't express that properly.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Postby coloin » Wed Sep 17, 2008 2:33 pm

Fine, I think you are right and we are addressing the same issue.

A solution grid is actually a unique set of at very large number of unavoidable sets [4-60 clues]

Red Ed found a "megaclue" which uniquely covered 82543 unavoidable sets.......

If the solution grid has a simple or big unavoidable set - there has to be at least one given clue in those 4-60 cells.


OK


lets turn this upside down:idea:

Lets say the puzzle maker / or printer in a magazine misses out a clue in a puzzle.

Ok by definition we cant solve it using simple techniques:( .

We insert our 4 clues in a UR which we have spotted.......and lo and behold we are able [without making any mistakes of course] to make a valid " 9*9 sudoku rules " puzzle solution.

What:!: we have a puzzle solution and we can see a UR/ unavoidable set - AND the blighter puzzle hasnt even got a given clue in any of the relevant cells..........

Not only have we solved the "puzzle" we have demonstrated that it wasnt a unique puzzle.

How does this change things denis:D:?:

C
coloin
 
Posts: 1629
Joined: 05 May 2005

Postby Allan Barker » Wed Sep 17, 2008 10:36 pm

DonM wrote: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 ....


Hi Don,

I do not know to whom you refer but I will at least wear the shirt since I definitely have suggested that there are things to learn from the output of my solver. The second part, that novices might benefit from advanced and complex solver output is not, or should not, be me. If I have left such an impression, please help me to correct it. Other than that, I agree with each and every point in the above quote, particulary about the elagance of human solutions. This seems to come in part from a grasp of the overall solution path that most solvers ignore.

As for my solver, its reason d'etre is quite different from what Denis and chanapgne are doing and perhpas most other solvers. It was designed to provide logical soultions that can use almost any logical form and it is therefore not restrictred by the kinds of rules that most solvers use. This is not a good or recommended way to make a solver however it is an excellent way to look for logic and principles that even humans may not have thought of. This is its purpose.

While agreeing completely about human solutions, I also support the idea that things can be learned from computer output indeed, this is what I have been doing for over 20 years. Even the workings of simple life are now discovered from computer output and in principle, from a single rule, Schrödinger's equation.

The recent example of Fata Morgana is not only a mirage but a mystery as well. How can a puzzle stump at least one powerful solver and be 3 to 4 times more difficult than GN for both backtracking and even Algorithm X, yet be solved easily using general second order logic and the anything solver? Algorithm X does not impliment basic Sudoku methods, it is a cover problem. It won't be easy to find the answer but it must be in the computer output.

Allan
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby DonM » Wed Sep 17, 2008 10:59 pm

Allan Barker wrote:
Hi Don,

....As for my solver, its reason d'etre is quite different from what Denis and chanapgne are doing and perhpas most other solvers. It was designed to provide logical soultions that can use almost any logical form and it is therefore not restrictred by the kinds of rules that most solvers use. This is not a good or recommended way to make a solver however it is an excellent way to look for logic and principles that even humans may not have thought of. This is its purpose.

While agreeing completely about human solutions, I also support the idea that things can be learned from computer output indeed, this is what I have been doing for over 20 years....
Allan


Allan, thanks for the reply. I actually agree with most of what you wrote including the last part above. IMO, it's all about balance. It is at the point where an over-reliance on a computer solver & it's output to the point where one has lost the perpective of what manual solving is all about and doesn't seem to be aware of it, that I have a problem. But, fwiw, I wasn't referring to you or Champagne.:)
DonM
2013 Supporter
 
Posts: 475
Joined: 13 January 2008

Postby Myth Jellies » Wed Sep 17, 2008 11:16 pm

Wow, take a couple days off and come back to an explosion.

Denis wrote:...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?


You are still missing the point, Denis. If you are going to make a proclamation about all resolution theories containing the uniqueness rule, you have to show how the rule invariably leads to a lack of confluence. Obviously you can't do that because, as I've shown, the uniqueness rule is invariant with regard to the solution state.

champagne, yes I was taking it as a given that the puzzle in question was a valid single-solution sudoku, otherwise the uniqueness rule would not apply. It certainly doesn't hurt to re-mention it, though.

David & champagne, yes one can use solved cells in a deduction. One could equivalently use the absence of candidates 3-9 in three originally unsolved cells to eliminate 1&2 from the fourth.
Code: Select all
UR+1 (any four originally unsolved cells lying in two rows, columns, and boxes--also applies to jigsaw sudoku)

~{3456789} ------ ~{3456789}
    .                 .
    .                 .
~{3456789} ------    {*}

conclusion: 1&2 can be eliminated from the star cell.

This also falls in line with an observation or proof that I mentioned elsewhere which shows that a candidate elimination deduction cannot depend on the presence of a candidate in an unsolved cell.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby StrmCkr » Wed Sep 17, 2008 11:57 pm

Code: Select all
This also falls in line with an observation or proof that I mentioned elsewhere which shows that a candidate elimination deduction cannot depend on the presence of a candidate in an unsolved cell.


first of denise is on the asusmption uniquness should be proven. not as a given state of a grid.

but any vaild sudoku must avoid all palindronic line of code (muti soltuion algorithic arangments) to form 1 solution. there is no other way to limit a soltuion count to 1, you can only avoid all these situations to do so.

if hes building a confluence theory he should assert that "mathmatically"

uniqueness algoriths should be discounted only due to there nature of removing a soltuion count pattern. thus altering the final count of solutions.

he is not recognizing a constructed pattern that has mutiple outcomes and deconstructing it to make it have only a single pattern given that a single square is the only option that destroys that arrangment = 1 soltuion.

ok now for the quote.

hidden single.

a hidden single removes n many candidates from a given cell.

what proof do you give that the other candiates listed in that space are not acutally true. this is exactly the same thing as above

how is that not proff of this contrary statment.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 624
Joined: 05 September 2006

Postby champagne » Thu Sep 18, 2008 3:04 am

Allan Barker wrote:
DonM wrote:....


Hi Don, …

The second part, that novices might benefit from advanced and complex solver output is not, or should not, be me.

As for my solver, …. It was designed to provide logical solutions that can use almost any logical form and it is therefore not restricted by the kinds of rules that most solvers use. This is not a good or recommended way to make a solver however it is an excellent way to look for logic and principles that even humans may not have thought of. This is its purpose.
Allan


As Allan joins us in this post, I would give my preliminary feeling towards it’s method in line with Don’s remarks.

Undoubtedly there are entry barriers in Allan logic approach. The main one is surely the brilliant probe for “rank 0 logic” . Far above what most players can catch. (I have to confess that over rank 0 it is still foggy in my mind) .

I entered the logic with the first example, a double loop rank 0:( . I felt being two or three years back when I tried to find equivalent form in AICs to a swordfish.

Swordfish and higher degree fishes seem to me the obvious form of “rank 0” logic. Despite my background, I had difficulties to accept “rank 0” rule before I discovered the “very simple” probe:) .

If, as I feel, that rule is the pillar sustaining all the building, I would not say the solver is opened to any logic. What is true I guess is that this global view of a “set of candidates” gives results difficult to catch (but difficult to match as well) with other methods.

The way Allan expalin it is somehow learning swimming directly in a deep pound. Either you learn or you sink.

I am convinced Allan could find a tutorial path to ease acceptance of rank 0 rule, but it is time consuming to build it.

champagne
champagne
2017 Supporter
 
Posts: 5612
Joined: 02 August 2007
Location: France Brittany

Postby David P Bird » Thu Sep 18, 2008 6:19 am

Colin, I think you've got yourself into a flummox! Let me try to put this in another way.

When we find a UR in a puzzle there are two possible cases:

Case 1.There are two possible solutions because the composer hasn't provided sufficient givens: Here the two digits are logically equivalent in the UR and no matter what we do, we'll never be able to distinguish one from the other.

Case 2. There is one solution and the composer has supplied sufficient givens: In this case there will be a deduction path stemming from a given somewhere which will prove that one of the digits is false in one of the UR cells to distinguish it from the other.

When we make an assignment to convert a UR into an Avoidable Rectangle we can discount case 1 as we've found way to distinguish the digits in the assigned cell. From this, without assuming uniqueness, we can safely say that there will be at least three different digits in the four cells as otherwise that assignment just wouldn't have been possible.

In terms of unavoidable sets: In case 1 the unavoidable set for the UR is just four cells and no given has been provided from it, but in case 2 the unavoidable set is wider ranging and contains the UR cells. Now the necessary given can be selected from any number of cells external to the UR. Being able to make any assignment in the rectangle therefore proves when this is the case.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Postby coloin » Thu Sep 18, 2008 7:36 am

Possibly !

But Case1 and Case2 are correct.

I am only trying to show that using a UR to perform an elimination - doesnt have to rely on an assumption that the puzzle is unique.

Place the 2 different digits [4 in total ] both ways - there will be a constraint found both times. Therefore the UR cannot be in the valid puzzle solution . Therefore you can place the clue which prevents the UR.

If you dont get a constraint then the puzzle had multiple solutions in the first place.

You would have to do this every time though.

Isnt this what you are saying ? [and myth too ?]

C
coloin
 
Posts: 1629
Joined: 05 May 2005

Postby champagne » Thu Sep 18, 2008 7:59 am

coloin wrote:Possibly !

But Case1 and Case2 are correct.

I am only trying to show that using a UR to perform an elimination - doesnt have to rely on an assumption that the puzzle is unique.

It is possible to confirm it is not unique [if this was the case].

Isnt this what you are saying ? [and myth too ?]

C


Hi coloin,

Just imagine you have a puzzlle proposed with two solutions (forming a UR)

If you have the opportunity to apply the UR rule, you will kill both solutions in once.

OK, you will not solve an unsolvable puzzle, but the conclusion you will make is not the right one. It is not a puzzle with no solution, it is a puzzle with 2.

Anyway, if it comes twice, you will change your supplier.

champagne
champagne
2017 Supporter
 
Posts: 5612
Joined: 02 August 2007
Location: France Brittany

Postby coloin » Thu Sep 18, 2008 8:32 am

champagne wrote:Anyway, if it comes twice, you will change your supplier.


I am a supplier:D

I'm suggesting that to logically apply the UR rule you confirm that the UR will cause a conflict [both ways]. That way you dont make the "no solution conclusion" - because you know it is a puzzle with at least 2 solutions.

Having said that if you apply a UR and [without other error] you get a constrained grid or no solution.......doesnt this mean that there was something wrong with the puzzle in the first place ?
C
coloin
 
Posts: 1629
Joined: 05 May 2005

re: assuming Uniquesness-Of-Answer

Postby Pat » Thu Sep 18, 2008 8:45 am

champagne wrote:
coloin wrote:I am only trying to show that using a UR to perform an elimination - doesnt have to rely on an assumption that the puzzle is unique.


Just imagine you have a puzzlle proposed with two solutions (forming a UR)

If you have the opportunity to apply the UR rule, you will kill both solutions in once.

OK, you will not solve an unsolvable puzzle, but the conclusion you will make is not the right one. It is not a puzzle with no solution, it is a puzzle with 2.



yes

and here's a scary thought --
    we have a "puzzle" with 3 answers

    assuming Uniquesness-Of-Answer may kill 2 answers,
    leaving us with the illusion of a single answer
User avatar
Pat
 
Posts: 3423
Joined: 18 July 2005

Postby champagne » Thu Sep 18, 2008 9:04 am

coloin wrote:I am a supplier:D


I know that:D but most players including me are not:(

coloin wrote:... because you know it is a puzzle with at least 2 solutions.


A common player doesn't know anything about a puzzle he is trying to solve.



But this was just an example, I agree with pat remark that there are other possibilities. Many have already been published.



Again, if we consider SUDOKU is solved for fun, nothing serious anyway.

champagne
champagne
2017 Supporter
 
Posts: 5612
Joined: 02 August 2007
Location: France Brittany

PreviousNext

Return to Advanced solving techniques