The concept of a RESOLUTION RULE and its applications

Advanced methods and approaches for solving Sudoku puzzles

Postby StrmCkr » Fri Nov 07, 2008 11:27 pm

removed
Last edited by StrmCkr on Sat Dec 24, 2016 3:19 am, edited 1 time in total.
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1417
Joined: 05 September 2006

Postby denis_berthier » Fri Nov 07, 2008 11:55 pm

StrmCkr,
What I want is a proof, it is not to be flooded by pages and pages of unformated text.
No list of examples or randomly assembled claims will ever prove a general rule.

If you want to prove that no obvious elimination can eliminate the 3 in the UR1.1, then this is rather obvious.
But there are so convoluted chain patterns that can lead to eliminations that this proves nothing.
Last edited by denis_berthier on Fri Nov 07, 2008 8:05 pm, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Postby StrmCkr » Fri Nov 07, 2008 11:57 pm

removed
Last edited by StrmCkr on Sat Dec 24, 2016 3:19 am, edited 1 time in total.
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1417
Joined: 05 September 2006

Postby Red Ed » Sat Nov 08, 2008 12:13 am

denis_berthier wrote:No, StrmCkr,
what I want is a proof of exactly what RedEd stated as an obvious fact

Wow, it's that basic is it? OK: take any solution grid with that 1/2/2/1 pattern in it. Swap 1s for 2s in the pattern to make 2/1/1/2. The 3 sudoku rules of no repeats in any - (a) box; (b) row; (c) column - still hold; so you've still got a valid solution grid.

The 1/2/2/1 pattern is an unavoidable - originally known as an exchangeable set.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby denis_berthier » Sat Nov 08, 2008 12:15 am

StrmCkr,

In addition to my previous remarks, as your example is a case of a standard UR1, and 3 could be concluded before the UR1.1 was found, it doesn't even qualify as an example.

Do you have any example of a UR1.1 which doesn't derive from a UR1?
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Sat Nov 08, 2008 12:23 am

Red Ed wrote:
denis_berthier wrote:No, StrmCkr,
what I want is a proof of exactly what RedEd stated as an obvious fact

Wow, it's that basic is it?

Sorry, RedEd. You're missing the point.
I'm not asking explanations about standard UR1 which has been in existence for years and which is completely obvious:
Code: Select all
12   12
12   123

I'm asking you if you have a proof of your statement about the different UR1.1 pattern:
RedEd wrote:Fact: if a puzzle has a unique solution grid then it cannot contain the following pattern on four unclued cells:
Code: Select all
 .  .  . | .
 1  .  . | 2
 2  .  . | 1
---------+---
 .  .  . | .

Are you suggesting that any UR1.1 is always derived from a UR1 (in which case all this discussion is pointless, as UR1.1 doesn't bring any new elimination)?
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Postby David P Bird » Sat Nov 08, 2008 12:52 am

denis_berthier wrote:Sudoku is a logic game. I'm dismayed to see how easily some players with no logical or mathematical background get stucked in incantations based on undefined notions.
Thanks for the compliment! It's much what I was expecting and why I choose to avoid you by and large.

If we're presented with a Sudoku puzzle in which the givens only contain seven of the nine digits, we know for sure that it can't have a unique solution. If we can place the seven given digits in each house, we'll be left with 18 cells which can be filled in one of two ways. These cells have become isolated from the rest of the puzzle and we need one more given to be able to resolve them.

This observation is based on logic applied to the requirements for the givens necessary to produce a solvable Sudoku. Taken down to the minimum set of cells where this can happen and we get an orthogonal rectangle of cells contained in two boxes.

I previously wrote:
If you tried to compose a set of givens that would be sufficient to solve a particular puzzle you would find there are rules that must be followed - eg a minimum of eight digits must be in the set of givens. You seem oblivious to these requirements, but they're the basis of the logic here.
Which you chose to ignore, but there is additional information to be deduced from the distribution of the givens to be gleaned if you want it.

There is a lot of information on this subject to be found in this forum (and still much to do), but if I wasted my time finding the references for you, I'm sure you wouldn't waste your time following them up.
David P Bird
2010 Supporter
 
Posts: 1043
Joined: 16 September 2008
Location: Middle England

Postby Red Ed » Sat Nov 08, 2008 1:01 am

denis_berthier wrote:Sorry, RedEd. You're missing the point.

No, Denis, you are. Read the link I posted and see if the lightbulb goes on:idea:
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby denis_berthier » Sat Nov 08, 2008 1:19 am

Red Ed wrote:
denis_berthier wrote:Sorry, RedEd. You're missing the point.

No, Denis, you are. Read the link I posted and see if the lightbulb goes on:idea:

Which link?

Oops, I found it: http://forum.enjoysudoku.com/viewtopic.php?t=605&postdays=0&postorder=asc&start=52
Unfortunately, I don't find in it the answer to my questions about UR1.1
Last edited by denis_berthier on Fri Nov 07, 2008 9:58 pm, edited 2 times in total.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Sat Nov 08, 2008 1:24 am

David,
I know there are obvious requirements for a puzzle to be valid and/or to have a unique solution.
AFAIK, none of them is enough to prove UR1.1.
Or, if it is so obvious, why has no one posted a proof yet?
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Postby Red Ed » Sat Nov 08, 2008 3:13 am

Do I have to spell it out mechanically?

Theorem: if a puzzle has a unique solution grid then it [the solution grid] cannot contain the following pattern on four unclued cells:
Code: Select all
 .  .  . | .
 1  .  . | 2
 2  .  . | 1
---------+---
 .  .  . | .

Proof: suppose to the contrary that puzzle P has unique solution grid G that contains that pattern on four unclued cells (i.e. P has no values in those cell locations). Extend P to an easier puzzle Q that has all cells of G - except those four - filled in. Obviously Q has two solutions. But then P cannot have a unique solution - contradiction!
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby denis_berthier » Sat Nov 08, 2008 3:24 am

RedEd, thanks for your efforts. Apologies for the little manipulation, but, yes, after all the complex pseudo-reasons and the false claims (non-dependence on uniqueness) given by others in previous posts, I wanted you to state it explicitly and as simply as possible.
It is now clear that UR1.1:
- depends on the assumption of uniqueness,
- depends on an assumption on clues (which amounts to fixing the names of some digits).
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Postby coloin » Sat Nov 08, 2008 3:32 am

Red Ed wrote:if a puzzle has a unique solution grid ..... suppose to the contrary that puzzle P has unique solution...............

I think denis doesnt want to assume uniqueness........

If you really want to - it is possible to add 1 clue of the U4 - and hence complete the U4 and then go on to show that the puzzle has a contradiction. You can do this both ways. Then you can insert your clue which prevents the formation of the U4

But Denis has indicated - along with many others, that this is unpalatable, despite the sound logic.

C
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Postby denis_berthier » Sat Nov 08, 2008 3:39 am

coloin wrote:[I think denis doesnt want to assume uniqueness........

What I want is clearly defined and correctly proven resolution rules.
It's true I usually don't use uniqueness but I prove it instead while solving the puzzle. But I deny no one the right to use it.

coloin wrote:If you really want to - it is possible to add 1 clue of the U4 - and hence complete the U4 and then go on to show that the puzzle has a contradiction. You can do this both ways. Then you can insert your clue which preevents the formation of the U4

I can't get what you're referring to. What's the U4?
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Postby denis_berthier » Sat Nov 08, 2008 3:45 am

The above discussion on UR inspires me some remarks on non-uniqueness.

The non-uniqueness on which the usual rules (UR or BUG) rely is some kind of artificial non-uniqueness: it amounts only to permuting the names of the digits.
We could have a similar kind of artificial non-uniqueness (and associated uniqueness rules) if we allow permutations of blank rows in a floor and of blank columns in a tower.

Open question: apart from such artificial pseudo-non-uniqueness, can we find rules for cases of real, non artificial, non-uniqueness - i.e. of puzzles having 2 or more non isomorphic solutions?
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to Advanced solving techniques