dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Unique Rectangles
Goto page Previous  1, 2
 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Solving techniques, and terminology
View previous topic :: View next topic  
Author Message
tlanglet



Joined: 17 Oct 2007
Posts: 2461
Location: Northern California Foothills

PostPosted: Sat Nov 20, 2010 10:45 pm    Post subject: Reply with quote

daj95376 wrote:
tlanglet wrote:
I like your finned or almost approach, but do not see how it adds to viewing the pattern. To me the strong analysis that determined r1c3<>1 is correct but incomplete. The internal SIS is r1c3=4 & r3c3=349 which can also be used to perform an additional deletion:
(4)r1c3-(4=2)r5c3-(2=6)r4c3; r3c3<>6
||
(349)r3c3-(6)r3c3

Yes Ted, what I described is essentially identical to what you described. The only difference is in motivation. I'm much more likely to examine URs that are almost a know pattern with known eliminations before examining URs for eliminations based on analyzing the internal SIS. Similar to a finned X-Wing where no one takes the time to analyze which eliminations are associated with the X-Wing.

As for the elimination r3c3<>6, it leads to r1c3<>1, which exposes a Naked Triple as the final step before Singles. The Naked Triple would have performed r3c3<>6 as well.

Regards, Danny


Danny, until recently I also looked at known patterns with known eliminations and then moved on, but recently I have looked at known patterns AND also analyzed both internal and external SIS. Several/numerous times I have obtained additional deletions for Type 4 & Type 6 URs; a couple of times I have even found more deletions by treating a finned x-wing as a Kraken x-wing; it is time consuming but fun and rewarding when you get a hit. I like to work a pattern for all it is worth.......

Ted
Back to top
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3136
Location: near Detroit, Michigan, USA

PostPosted: Sat Feb 12, 2011 11:05 pm    Post subject: Reply with quote

Danny wrote:

Quote:
I've heard that using uniqueness might lead to a solution in a multi-solution puzzle, but I don't recall seeing it demonstrated. Even so, I have found a solution and the puzzle can be tossed. I don't care if someone else finds a different solution. That simply means that it's a multi-solution puzzle!!!


I don't buy this. How can assuming uniqueness allow you to arrive at a particular solution of a multi-solution puzzle?

Also, a multi-solution puzzle has no logical solution path. To arrive at a particular solution, at some point you have to make one or more arbitrary choices.

The fact is, no one is interested in "solving" puzzles that have multiple solutions. Danny, you can test this by posting a few. Please do not say up front that there are multiple solutions.

A few years ago, I tried to find examples of puzzles with (just a few) multiple solutions. I was looking to help define non-uniqueness strategies and patterns. I found that, aside from some mathematical theorists, no one cares to bother with non-unique puzzles.

Keith
Back to top
View user's profile Send private message
daj95376



Joined: 23 Aug 2008
Posts: 3855

PostPosted: Sun Feb 13, 2011 12:51 am    Post subject: Reply with quote

I can now claim the existence of a premise that I thought was incorrect.

Code:
 Puzzle 11/02/12 Difficult ?
 +-----------------------+
 | 2 . . | . . 5 | . 3 . |
 | . 3 . | . . . | . . . |
 | . . 5 | . . 3 | 1 6 . |
 |-------+-------+-------|
 | . . . | 3 . . | . 8 . |
 | . . . | . 5 . | . 7 1 |
 | 9 . 1 | . . . | . 5 3 |
 |-------+-------+-------|
 | . . 6 | . . . | . . . |
 | 8 . 3 | 6 1 7 | . . 2 |
 | . . . | . 2 4 | . 1 . |
 +-----------------------+   # 1x solution

Givens Alterations: r3c3<>5, r1c3=4, r6c6=6

Code:
 +-----------------------+
 | 2 . 4 | . . 5 | . 3 . |
 | . 3 . | . . . | . . . |
 | . . . | . . 3 | 1 6 . |
 |-------+-------+-------|
 | . . . | 3 . . | . 8 . |
 | . . . | . 5 . | . 7 1 |
 | 9 . 1 | . . 6 | . 5 3 |
 |-------+-------+-------|
 | . . 6 | . . . | . . . |
 | 8 . 3 | 6 1 7 | . . 2 |
 | . . . | . 2 4 | . 1 . |
 +-----------------------+   # 3x solutions

Code:
 after basics: perform <57> UR Type 1 in r39c13  =>  r3c3=9
 *---------------------------------------------------*         *-----------*
 |  2    1    4    | 7    6    5    | 9    3    8    |         |214|765|938|
 |  6    3    59   | 1    49   8    | 7    2    45   |         |635|198|724|
 | *57   8   *57+9 | 2    49   3    | 1    6    45   |         |789|243|165|
 |-----------------+----------------+----------------|         |---+---+---|
 |  4    5    2    | 3    7    1    | 6    8    9    |         |452|371|689|
 |  3    6    8    | 9    5    2    | 4    7    1    |         |368|952|471|
 |  9    7    1    | 4    8    6    | 2    5    3    |         |971|486|253|
 |-----------------+----------------+----------------|         |---+---+---|
 |  1    2    6    | 5    3    9    | 8    4    7    |         |126|539|847|
 |  8    4    3    | 6    1    7    | 5    9    2    |         |843|617|592|
 | *57   9   *57   | 8    2    4    | 3    1    6    |         |597|824|316|
 *---------------------------------------------------*         *-----------*

Alternately:

Code:
 after basics: perform <459> MUG in r23c359  =>  r3c3=7
 *--------------------------------------------------*          *-----------*
 | 2    1    4    | 7    6    5    | 9    3    8    |          |214|765|938|
 | 6    3   *59   | 1   *49   8    | 7    2   *45   |          |639|148|725|
 | 57   8   *59+7 | 2   *49   3    | 1    6   *45   |          |587|293|164|
 |----------------+----------------+----------------|          |---+---+---|
 | 4    5    2    | 3    7    1    | 6    8    9    |          |452|371|689|
 | 3    6    8    | 9    5    2    | 4    7    1    |          |368|952|471|
 | 9    7    1    | 4    8    6    | 2    5    3    |          |971|486|253|
 |----------------+----------------+----------------|          |---+---+---|
 | 1    2    6    | 5    3    9    | 8    4    7    |          |126|539|847|
 | 8    4    3    | 6    1    7    | 5    9    2    |          |843|617|592|
 | 57   9    57   | 8    2    4    | 3    1    6    |          |795|824|316|
 *--------------------------------------------------*          *-----------*

Alternately:

Code:
 after basics: perform BUG+1  =>  r3c3=5
 *--------------------------------------------------*          *-----------*
 | 2    1    4    | 7    6    5    | 9    3    8    |          |214|765|938|
 | 6    3    59   | 1    49   8    | 7    2    45   |          |639|148|725|
 | 57   8   (5)79 | 2    49   3    | 1    6    45   |          |785|293|164|
 |----------------+----------------+----------------|          |---+---+---|
 | 4    5    2    | 3    7    1    | 6    8    9    |          |452|371|689|
 | 3    6    8    | 9    5    2    | 4    7    1    |          |368|952|471|
 | 9    7    1    | 4    8    6    | 2    5    3    |          |971|486|253|
 |----------------+----------------+----------------|          |---+---+---|
 | 1    2    6    | 5    3    9    | 8    4    7    |          |126|539|847|
 | 8    4    3    | 6    1    7    | 5    9    2    |          |843|617|592|
 | 57   9    57   | 8    2    4    | 3    1    6    |          |597|824|316|
 *--------------------------------------------------*          *-----------*

I've just reduced a multi-solution puzzle to 3x different solutions through the use of uniqueness tests.

Bottom Line: it doesn't matter which of the three candidates you choose for r3c3, you're going to get a solution.

Regards, Danny
Back to top
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3136
Location: near Detroit, Michigan, USA

PostPosted: Sun Feb 13, 2011 3:40 am    Post subject: Reply with quote

Danny,

WOW!! Shocked

I've learned something today.

Thank you,

Keith
Back to top
View user's profile Send private message
ronk



Joined: 07 May 2006
Posts: 397

PostPosted: Mon Feb 14, 2011 5:12 pm    Post subject: Reply with quote

daj95376 wrote:
I can now claim the existence of a premise that I thought was incorrect.
...
...
I've just reduced a multi-solution puzzle to 3x different solutions through the use of uniqueness tests.

I recall cases where use of a uniqueness technique leads to no solution, so I doubt that "premise" can be generalized.
Back to top
View user's profile Send private message
daj95376



Joined: 23 Aug 2008
Posts: 3855

PostPosted: Mon Feb 14, 2011 8:27 pm    Post subject: Reply with quote

ronk wrote:
I recall cases where use of a uniqueness technique leads to no solution, so I doubt that "premise" can be generalized.

Yes, until this example, I thought zero solutions were the only possible outcome if a uniqueness test was applied to a multi-solution puzzle. Live and learn!!!
Back to top
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3136
Location: near Detroit, Michigan, USA

PostPosted: Mon Feb 14, 2011 9:11 pm    Post subject: Reply with quote

Sorry, I am a little slow.

Case 1. The puzzle is valid, it has a single solution. Applying a uniqueness test is completely valid.

Case 2. The puzzle is invalid: It has multiple solutions.

a. Applying a uniqueness test may select a subset, or even one, of the multiple solutions. This is Danny's example.

b. Applying a uniqueness test may transform the puzzle into Case 3. (Really?)

Case 3. The puzzle is invalid. It has no solutions. I do not see how any test can change this state.

Keith
Back to top
View user's profile Send private message
daj95376



Joined: 23 Aug 2008
Posts: 3855

PostPosted: Tue Feb 15, 2011 2:06 am    Post subject: Reply with quote

keith wrote:
Sorry, I am a little slow.

Case 1. The puzzle is valid, it has a single solution. Applying a uniqueness test is completely valid.

Case 2. The puzzle is invalid: It has multiple solutions.

a. Applying a uniqueness test may select a subset, or even one, of the multiple solutions. This is Danny's example.

b. Applying a uniqueness test may transform the puzzle into Case 3. (Really?)

Case 3. The puzzle is invalid. It has no solutions. I do not see how any test can change this state.

Keith

This is not a good example, but I believe it qualifies as an example of my statement about zero solutions.

If you apply the Naked Pair r7c57=36, then you are left with a BUG+0 and 2x solutions.

However, if you apply BUG+1 and examine [r7] closely:

Code:
 BUG+1  =>  r7c4=3  =>  r7c5=6 and r7c7=6  =>  zero solutions!
 *--------------------------------------------------*
 | 5    4    3    | 2    1    6    | 7    8    9    |
 | 19   19   8    | 45   7    45   | 2    6    3    |
 | 6    7    2    | 8    9    3    | 4    15   15   |
 |----------------+----------------+----------------|
 | 4    6    1    | 7    5    9    | 8    3    2    |
 | 7    3    5    | 6    8    2    | 1    9    4    |
 | 8    2    9    | 34   34   1    | 5    7    6    |
 |----------------+----------------+----------------|
 | 2    19   4    | 359  36   7    | 36   15   8    |
 | 19   5    67   | 39   2    8    | 36   4    17   |
 | 3    8    67   | 1    46   45   | 9    2    57   |
 *--------------------------------------------------*

RonK will immediately recognize the originating puzzle as a failed attempt at the current Patterns Game! _ Laughing _

Code:
 *-----------*
 |..3|..6|..9|
 |...|.7.|.6.|
 |6..|8..|4..|
 |---+---+---|
 |..1|7..|..2|
 |.3.|...|.9.|
 |8..|...|5..|
 |---+---+---|
 |..4|..7|..8|
 |.5.|.2.|...|
 |3..|1..|9..|
 *-----------*

My example was derived by examining two neighboring solutions for the above, illegal puzzle.
Back to top
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3136
Location: near Detroit, Michigan, USA

PostPosted: Tue Feb 15, 2011 3:43 am    Post subject: Reply with quote

Danny,

According to Sudoku Susser, the puzzles you posted have multiple solutions. So, they may be examples of Case 2b?
Quote:

Case 3. The puzzle is invalid. It has no solutions. I do not see how any test can change this state.


If a puzzle has no solutions, that must be inherent in the initial state. There is no way the puzzle can become valid by adding information, in my view.

Here is an invalid puzzle with no solutions:
Code:
+-------+-------+-------+
| 9 . . | . 6 . | . . 1 |
| . . 1 | . 8 9 | 4 . . |
| . . . | . . . | . 6 3 |
+-------+-------+-------+
| 5 . . | . . . | . 9 . |
| . 2 . | 5 3 1 | . 7 . |
| . 7 . | . . . | . . 5 |
+-------+-------+-------+
| 1 8 . | . . . | . . . |
| . . 4 | 2 5 . | 3 . . |
| 2 . . | . 4 . | . . 8 |
+-------+-------+-------+
Making a selection of a value in an unsolved cell cannot change that.

On the other hand, if a puzzle has multiple solutions, making a selection of a value in an unsolved cell can change its number of solutions, or make it invalid with no solutions.

Keith
Back to top
View user's profile Send private message
daj95376



Joined: 23 Aug 2008
Posts: 3855

PostPosted: Tue Feb 15, 2011 4:44 am    Post subject: Reply with quote

keith wrote:
Sorry, I am a little slow.

Case 1. The puzzle is valid, it has a single solution. Applying a uniqueness test is completely valid.

Case 2. The puzzle is invalid: It has multiple solutions.

a. Applying a uniqueness test may select a subset, or even one, of the multiple solutions. This is Danny's example.

b. Applying a uniqueness test may result in a puzzle with zero solutions. See Danny's subsequent example.

Case 3. The puzzle is invalid. It has no solutions. I do not see how any test can change this state.

I misunderstood your Case 2b. I've re-written it to where it makes sense to me.

Regards, Danny
Back to top
View user's profile Send private message
ronk



Joined: 07 May 2006
Posts: 397

PostPosted: Tue Feb 15, 2011 11:57 am    Post subject: Reply with quote

keith wrote:
On the other hand, if a puzzle has multiple solutions, making a selection of a value in an unsolved cell can change its number of solutions, or make it invalid with no solutions.

Thought that's what Danny and I said, with no less lack of clarity. Smile
Back to top
View user's profile Send private message
wapati



Joined: 10 Jun 2008
Posts: 472
Location: Brampton, Ontario, Canada.

PostPosted: Wed Feb 16, 2011 2:06 am    Post subject: Reply with quote

ronk wrote:
keith wrote:
On the other hand, if a puzzle has multiple solutions, making a selection of a value in an unsolved cell can change its number of solutions, or make it invalid with no solutions.

Thought that's what Danny and I said, with no less lack of clarity. Smile


This is a new one to me, but there is lots I don't know.

Clearly there is no method to solve a puzzle with no solution.

Puzzles with multiple solutions may be played with, if one cares.
I am not clear that using uniqueness on a multi can render it solutionless.

Thanks for any insight.
Back to top
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3136
Location: near Detroit, Michigan, USA

PostPosted: Wed Feb 16, 2011 8:08 am    Post subject: Reply with quote

wapati wrote:

This is a new one to me, but there is lots I don't know.

I am not clear that using uniqueness on a multi can render it solutionless.

Thanks for any insight.

Danny, do you have an example of this?

Thanks for the lessons.

Keith
Back to top
View user's profile Send private message
daj95376



Joined: 23 Aug 2008
Posts: 3855

PostPosted: Wed Feb 16, 2011 5:01 pm    Post subject: Reply with quote

keith wrote:
Danny, do you have an example of this?

Thanks for the lessons.

I thought the BUG+1 in my second example demonstrated this scenario.

You're welcome for the lessons. It was by pure accident that I managed to select test puzzles that provided easily recognizeable examples.

Regards, Danny
Back to top
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3136
Location: near Detroit, Michigan, USA

PostPosted: Wed Feb 16, 2011 8:34 pm    Post subject: Reply with quote

daj95376 wrote:
I thought the BUG+1 in my second example demonstrated this scenario


I am not entirely convinced, since the 36 pair in R7 makes it into a BUG+0.

Keith
Back to top
View user's profile Send private message
daj95376



Joined: 23 Aug 2008
Posts: 3855

PostPosted: Wed Feb 16, 2011 9:08 pm    Post subject: Reply with quote

keith wrote:
I am not entirely convinced, since the 36 pair in R7 makes it into a BUG+0.

Which makes the puzzle have 2x solutions!

Thus, the puzzle has two solutions ... or else the BUG+1 (mis)use reduces it to zero solutions.
Back to top
View user's profile Send private message
ronk



Joined: 07 May 2006
Posts: 397

PostPosted: Wed Feb 16, 2011 10:19 pm    Post subject: Reply with quote

daj95376 wrote:
Thus, the puzzle has two solutions ... or else the BUG+1 (mis)use reduces it to zero solutions.

An example where the uniqueness move was the "simplest" move available would be better ... but yours is an acceptable example to me.
Back to top
View user's profile Send private message
Pat



Joined: 23 Feb 2010
Posts: 162

PostPosted: Thu Feb 17, 2011 1:21 pm    Post subject: Reply with quote

keith wrote:
wapati wrote:

This is a new one to me, but there is lots I don't know.

I am not clear that using uniqueness on a multi can render it solutionless.


Danny, do you have an example of this?


we observe these 4 cells --
    Code:

             |
         12  | 12
         12  | 123
     --------+---------
             |

-- and we decide to assume the puzzle has 1 answer;

we conclude the 3 must be forced in that cell
( else there's an even number of answers -- 0,2,... );

continuing to solve the puzlle, we reach a contradiction --
the puzzle seems to have 0 answers;

but in fact it has perhaps 2 answers,
both removed by our wrong assumption
( none of the answers has 3 in that cell )


.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.
that's the lucky case,
we run into trouble so at least we realize there's a problem
.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.


in another case,
the puzzle starts with say 3 answers,
our wrong assumption removes 2 of them
and the puzzle seems to have one answer --
we end up imagining we've properly solved the puzzle
Back to top
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3136
Location: near Detroit, Michigan, USA

PostPosted: Sat Feb 19, 2011 10:10 am    Post subject: Reply with quote

Pat wrote:

in another case,
the puzzle starts with say 3 answers,
our wrong assumption removes 2 of them
and the puzzle seems to have one answer --
we end up imagining we've properly solved the puzzle

Actually, Danny's example above is exactly that!

Keith
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Solving techniques, and terminology All times are GMT
Goto page Previous  1, 2
Page 2 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group