On the Confluence of Uniqueness Theories

Advanced methods and approaches for solving Sudoku puzzles

Postby David P Bird » Thu Sep 18, 2008 9:38 am

Colin, right, I see what you are about. You're using a "plug and flail" solving method which I won't allow in my repertoire.

All I'm saying is that an Avoidable Rectangle must contain three different digits so that if we have

a b
b axyz

we can immediately exclude (a) from the fourth cell without assuiming overall uniqueness.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Postby Allan Barker » Thu Sep 18, 2008 10:41 am

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


Champagne, your observations are quite good and I think the overall feeling may be common, I would probably say the same. Such feedback, Don's as well, is obviously valuable. And yes, my short example explanations are truly sink or swim. !! I have thought about your tutorial path idea, and I should do something just like that, and/or develop a formal method, which so far I have avoided, not because of the time as it is fun, but because there is also a bigger commitment to users that just proving an idea works. However, maybe the time has come.

More relevant here, is how the set solver I use relates to what I call set logic rules. These are somewhat separate things. The solver uses only sets, no T&E, and uses only one rule to determine eliminations, e.g., all sets must have exactly one candidate, the Sudoku rule itself. Even rules for AICs or alternating strong/weak sets are unknown to the solver and therefore, it finds a broken wing pretty much the same way it finds an AIC. There is nothing otherwise special about the solver, except perhaps how it tries to deal with the enormous computational complexity.

Set logic rules, like rank 0, rank N, or triplets, are rules that try to explain the kinds of logic that come out of the solver. The solver does not implement the specific set logic rules rather, its generalized output verifies the relevance of such rules. In the same way, I can say that I see a lot of logic in the form of nrctz chains and conclude that such chains represent a significant percentage of Sudoku logic. Of course, this more of an experimental approach. Currently, it cannot find uniqueness based eliminations because it implements only the one Sudoku rule.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby ronk » Thu Sep 18, 2008 11:21 am

David P Bird wrote:All I'm saying is that an Avoidable Rectangle must contain three different digits so that if we have

a b
b axyz

we can immediately exclude (a) from the fourth cell without assuiming overall uniqueness.

1) Most of us only work puzzles from sources which guarantee unique solutions, so occasionally being able to not assume overall uniqueness doesn't seem helpful. The placement or elimination(s) are the same, are they not:?:

2) Most everyone on this forum already uses the term "deadly pattern" in lieu of your "Avoidable Rectangle". Do we really need another new term:?:
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby David P Bird » Thu Sep 18, 2008 12:16 pm

Ronk, to answer your Q2 first: As I explained earlier in this thread, Avoidable Rectangles (coined by Andrew Stewart) are what AURs become when one of the cells has been solved. The term isn't equivalent to "deadly pattern" at all.

Now to Q1: I was conducting an academic exercise to try to help your discussions with DB. In doing this I proved that uniqueness doesn't need to be assumed with ARs so AR deductions are still available to the minority of solvers who won't assume uniqueness, although, as you say, these deductions amount to the same as AUR ones.

DB's response to you isn't the first time he's requested chapter and verse on some point or other, and then refused "to waste his time" following up the answer when it isn't to his liking. I take this attitude if his into account when I decide how to waste my time, and I suggest you do the same.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Postby Allan Barker » Thu Sep 18, 2008 9:18 pm

Hi David,

David P Bird wrote:........so that if we have

a b
b axyz

we can immediately exclude (a) from the fourth cell without assuming overall uniqueness.

Perhaps I am missing something but I don't understand the assertion "... without assuming overall uniqueness". It seems the excluion of 'a' must still (perhaps indirectly) rely on Sudoku rule 2 (every valid game must have only 1 solution) and that 'a' cannot be excluded based only on Sudoku rule 1 (every cell, row, column, box must have only 1 digit). One reason is that (a b / b a) as well as (b a / a b) could both be solutions according to rule 1.

To me, rule 1 and rule 2 divide what is based on uniqueness and what is not.
Allan Barker
 
Posts: 266
Joined: 20 February 2008

Postby Myth Jellies » Thu Sep 18, 2008 9:37 pm

David P Bird wrote:All I'm saying is that an Avoidable Rectangle must contain three different digits so that if we have

a b
b axyz

we can immediately exclude (a) from the fourth cell without assuiming overall uniqueness.


My initial reaction was, "What? Are you nuts?" but I held off. Then after thinking about it for awhile, I see that you have a point.

Correct me if I am wrong, but I have the logic going...

If we had multiple solutions with a's and b's forming a deadly pattern in those four cells then there is no way that we could correctly determine that any of those cells did not contain an a or b

Thus, using the contrapositive, if we determine that one of those cells does not contain an a or b then we know that those four cells do not contain an unavoidable set with a and b.

Therefore we can eliminate the a from that cell without ever assuming the puzzle has a unique solution.

so if you have (without using uniqueness to this point)...
Code: Select all
abc | abc
ab  | ac


Then you can eliminate c's from any cell seeing the three c's without assuming uniqueness. Like ronk, I would never worry about the distinction, but it is an interesting observation nonetheless.

A long time ago, RW had a thread about uniqueness without assuming uniqueness. I'm wondering if it was similar to this.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby David P Bird » Fri Sep 19, 2008 3:18 am

Allan, hello again.
The logical approach I applied localised the question of uniqueness to the position of two digits in four AUR cells.
If we can eliminate one of the digits from one of the cells, we have proved that there is a unique way to fill the four cells with just those two digits.
We therefore know that one of the givens breaks the dual solution possibility with respect to these digits and cells.
It's easy to show that, if the rectangle were occupied only by our two digits, that given would have to be in one of the four cells.
As the rectangle has a uniqe two-digit solution but doesn't contain a given, we therefore know it must contain a third digit.

As you know I'm no mathematician, so I may not have expressed that very succinctly, but in my view we have used a proven localised uniqueness, not assumed it.

Myth, you've just broken a MJ/DPB all time record because that's two things we've managed to agree on in succession!

Now I've got a bit more adept at the mental manipulations involved, it's clear that we don’t need a completely solved cell to apply this logic (the case I originally addressed) but as in your example, simply one cell where one of a digit pair has been eliminated.

It's probably possible to extend this non-assumptive line of reasoning to other uniqueness based deductions.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Postby Myth Jellies » Sat Sep 20, 2008 11:07 pm

David, I found RW's post, and it is the same thing. Guess I didn't really understand it back then. Here is the link from over two years ago.

http://forum.enjoysudoku.com/viewtopic.php?t=3967
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby David P Bird » Sun Sep 21, 2008 6:28 am

Myth, Thanks for the link, and yes I've just followed in the same footsteps. It will take me a while to work through how RW & Co. extended the concept back then.

Idly thinking about this on one of my walks, the conditions required to eliminate one of the rival candidates in an individual AUR cell are pretty tricky to set up, which I think explains why the situation is so uncommon. I was trying to track back the requirements to a pattern of givens, but it's all far too complex for that.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Postby RW » Sun Sep 21, 2008 6:46 am

Well well well... I was reading through this thread and thinking that I'll probably have to add a link to that ancient thread, but you beat me to it MJ!:) This is a subject I've had time to think over several times since then, so if you have any questions, feel free to ask.

I'd like to add one thing:
David P Bird wrote:Avoidable Rectangles (coined by Andrew Stewart) are what AURs become when one of the cells has been solved.

You don't even need a solved cell, it's enough is one of the candidates in the potential deadly pattern is eliminated:
Code: Select all
ab   ab
ab   axy

Candidate 'b' is already eliminated from cell 'axy' => we may eliminate 'a' as well without assuming uniqueness.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby ronk » Sun Sep 21, 2008 7:27 am

RW wrote:You don't even need a solved cell, it's enough is one of the candidates in the potential deadly pattern is eliminated:
Code: Select all
ab   ab
ab   axy

Candidate 'b' is already eliminated from cell 'axy' => we may eliminate 'a' as well without assuming uniqueness.

I get it but IMO ... not assuming uniqueness while using a uniqueness technique will be perpetually confusing to many.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby RW » Sun Sep 21, 2008 12:01 pm

ronk wrote:
RW wrote:You don't even need a solved cell, it's enough is one of the candidates in the potential deadly pattern is eliminated:
Code: Select all
ab   ab
ab   axy

Candidate 'b' is already eliminated from cell 'axy' => we may eliminate 'a' as well without assuming uniqueness.

I get it but IMO ... not assuming uniqueness while using a uniqueness technique will be perpetually confusing to many.

I'm well aware about that. That's why we shouldn't even talk about "using a uniqueness technique" in these cases. When you are not assuming uniqueness, you are not using a uniqueness technique. If one deadly candidate is removed, you cannot make an uniqueness elimination anymore. You can make the same elimination that a similar uiqueness pattern makes, but it is not based on the basic principles of uniqueness technique. It is a basic elimination based on standard numeral logic: "if C=X, then the puzzle has no solutions", as opposed to uniqueness logic: if C=X, then the puzzle has either 0 or >1 solutions. When you eliminated the deadly candidate, you already ruled out the possibility of >1 solutions.

I think it could be a good idea to have an own name for these patterns. "Avoidable Rectangle" is one option, but that only describes basic UR patterns with removed candidates. The same logic applies to all uniqueness patterns, BUG-lites, BUGs and so on. What should these be called?

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby udosuk » Sun Sep 21, 2008 1:18 pm

ronk wrote:
RW wrote:You don't even need a solved cell, it's enough is one of the candidates in the potential deadly pattern is eliminated:
Code: Select all
ab   ab
ab   axy

Candidate 'b' is already eliminated from cell 'axy' => we may eliminate 'a' as well without assuming uniqueness.

I get it but IMO ... not assuming uniqueness while using a uniqueness technique will be perpetually confusing to many.

Like RW said this is not an uniqueness technique, but a "pure logic" technique, albeit applied to a puzzle with possible multiple solutions.

The "pure logic" goes like this:

We have 2 possible scenarios. Scenario 1: the puzzle has one solution. Then the 4 cells can't have the pattern [ab]+[ba] because [ba]+[ab] would make an alternative solution. Therefore the 4th cell can't be a.

Scenario 2: the puzzle has multiple solutions. However suppose the 4 cells are in the pattern [ab]+[ba]. And this pattern exists in one of the possible solutions, let's call it solution grid S1. Without changing the other 77 cells of S1, we change these 4 cells into [ba]+[ab]. With regard to the original given clues, this new solution grid, S2, must also be a legitimate solution to the original puzzle.

But remember earlier we have used other logical means to eliminate candidate b from the 4th cell. Thus S2 must not be a legal solution to the original puzzle.

A contradiction has been reached. Hence the initial premise, i.e. the 4 cells being in the pattern [ab]+[ba], must not be allowed in any meaningful solution, and candidate a can be eliminated from the 4th cell if our goal is to reach one of the (possibly many) valid solutions.

In practice, if you can eliminate candidate b from the 4th cell, candidate b must also be eliminated from either the 2nd or 3rd cell (or both), turning one or both of these 2 cells into a, thus eliminating candidate a from the 4th cell.

Note that this whole process is very easy to go wrong if you're careless about how to spot an "avoidable rectangle". For example, in a diagonal (Sudoku X) puzzle, if the b in the 4th cell is eliminated from one of the diagonals, then these 4 cells no longer form an "avoidable rectangle", and you can't eliminate a from the 4th cell.

I'm recently doing a lot of work on emerald puzzles, which make heavy use of the uniqueness assumption, therefore I have a lot of interest on related theories like this.:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby ronk » Sun Sep 21, 2008 5:39 pm

Code: Select all
ab   ab
ab   axy

Can this pattern be the sole reason for multiple solutions:?:
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby RW » Sun Sep 21, 2008 9:38 pm

ronk wrote:
Code: Select all
ab   ab
ab   axy

Can this pattern be the sole reason for multiple solutions:?:

Depends on how b is eliminated.

If you have showed that b in cell 4 cannot lead to a solution, then a cannot either, and the only candidates that may give a valid solution are x or y.

If you have eliminated b by using another uniqueness pattern and it turns out that the puzzle is invalid and has multiple solutions, this pattern still cannot be the sole reason for these. The uniqueness pattern used to eliminate b must also give further solutions.

If you have eliminated b by using the same uniqueness pattern (for example as a UR type 6 at an earlier stage), then the pattern can be the sole reason to multiple solutions.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

PreviousNext

Return to Advanced solving techniques