Unique, unique.

Post the puzzle or solving technique that's causing you trouble and someone will help

Unique, unique.

Postby fermat » Tue May 02, 2006 5:08 am

I generated a puzzle using optimize in Soduku Cue. <The original was made, by me, in Sudoku Assistant.>

The thing is, most (all) solvers reject it, yet it is easy for humans.
I suspect that the constraint, given to 'puters, that only two blocks may be involved, fails with some frequency.

Here are the goods. First, this puzzle that even I can solve, using uniqueness.
Code: Select all
2 . 5|. . .|6 . 1
3 . .|. 7 9|. . 5
. . .|. . .|. . .
-----+-----+-----
. . 4|2 8 3|5 . .
7 . .|. . .|. . 8
. . .|. 9 .|. . .
-----+-----+-----
. . .|5 . 8|. . .
. . 1|. . .|7 . .
. 2 .|. . .|. 9 .

Stop here if you just want a puzzle. <and most computer solvers reject this puzzle>

I make puzzles most days, my mom and my aunt like easy puzzles, they are what you make, usually. I feed them into Sudoku Cue using optimize, with settings low, except uniqueness, which is so easy to spot.

Now the puzzle that I ran into SQ, using optimize.
Code: Select all
2 . 5 | . . . | 6 . 1
3 . . | 1 7 9 | . . 5
. . . | . . . | . . .
---------------------
. . 4 | 2 8 3 | 5 . .
7 . . | . . . | . . 8
. . . | . 9 . | . . .
---------------------
. . . | 5 . 8 | . . .
. . 1 | . . . | 7 . .
. 2 . | . . . | . 9 .


Here is what most solvers get to and stop.
Code: Select all
Result, at the key point.

.------------------.------------------.------------------.
| 2     9     5    | 8     3     4    | 6     7     1    |
| 3     16    8    | 16    7     9    | 24    24    5    |
| 16    4     7    | 16    5     2    | 3     8     9    |
:------------------+------------------+------------------:
| 9     16    4    | 2     8     3    | 5     16    7    |
| 7     5     23   | 4     6     1    | 9     23    8    |
| 16    8     23   | 7     9     5    | 24    12346 36   |
:------------------+------------------+------------------:
| 4     7     9    | 5     2     8    | 1     36    36   |
| 8     3     1    | 9     4     6    | 7     5     2    |
| 5     2     6    | 3     1     7    | 8     9     4    |
'------------------'------------------'------------------'

Well, use uniqueness and get this...
.------------------.------------------.------------------.
| 2     9     5    | 8     3     4    | 6     7     1    |
| 3     16    8    | 16    7     9    | 24    24    5    |
| 16    4     7    | 16    5     2    | 3     8     9    |
:------------------+------------------+------------------:
| 9     16    4    | 2     8     3    | 5     16    7    |
| 7     5     23   | 4     6     1    | 9     23    8    |
| 16    8     23   | 7     9     5    | 24    1     36   |
:------------------+------------------+------------------:
| 4     7     9    | 5     2     8    | 1     36    36   |
| 8     3     1    | 9     4     6    | 7     5     2    |
| 5     2     6    | 3     1     7    | 8     9     4    |
'------------------'------------------'------------------'

Which is trivial.

I am thinking that this works for humans, computers all need an update.
fermat
 
Posts: 105
Joined: 29 March 2006

Postby re'born » Tue May 02, 2006 6:24 am

fermat,

Unless I am not seeing something, aren't all of the following five grids solutions to your puzzle?

Code: Select all
 *-----------*
 |295|834|671|
 |368|179|245|
 |147|652|389|
 |---+---+---|
 |914|283|567|
 |753|461|928|
 |682|795|413|
 |---+---+---|
 |479|528|136|
 |831|946|752|
 |526|317|894|
 *-----------*


Code: Select all
  *-----------*
 |295|834|671|
 |318|679|245|
 |647|152|389|
 |---+---+---|
 |964|283|517|
 |752|461|938|
 |183|795|426|
 |---+---+---|
 |479|528|163|
 |831|946|752|
 |526|317|894|
 *-----------*


Code: Select all
 
 *-----------*
 |295|834|671|
 |318|679|245|
 |647|152|389|
 |---+---+---|
 |964|283|517|
 |753|461|928|
 |182|795|436|
 |---+---+---|
 |479|528|163|
 |831|946|752|
 |526|317|894|
 *-----------*


Code: Select all
 
 *-----------*
 |295|834|671|
 |318|679|425|
 |647|152|389|
 |---+---+---|
 |964|283|517|
 |752|461|938|
 |183|795|246|
 |---+---+---|
 |479|528|163|
 |831|946|752|
 |526|317|894|
 *-----------*


Code: Select all
  *-----------*
 |295|834|671|
 |318|679|245|
 |647|152|389|
 |---+---+---|
 |964|283|517|
 |753|461|928|
 |182|795|463|
 |---+---+---|
 |479|528|136|
 |831|946|752|
 |526|317|894|
 *-----------*


When you use a uniqueness argument in a puzzle without a unique solutions, it will eliminate an even number of solutions.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby fermat » Tue May 02, 2006 6:35 am

rep'nA wrote:fermat,

Unless I am not seeing something, aren't all of the following five grids solutions to your puzzle?


When you use a uniqueness argument in a puzzle without a unique solutions, it will eliminate an even number of solutions.


I posted this because, using uniqueness I get one solution. You listed them all without using uniqueness.
fermat
 
Posts: 105
Joined: 29 March 2006

Re: Unique, unique.

Postby re'born » Tue May 02, 2006 8:06 am

fermat wrote:
I posted this because, using uniqueness I get one solution.


fermat,

I'm guess then that I'm not sure exactly what you are saying. In this particular puzzle, you may apply a uniqueness argument to eliminate 4 of the 5 solutions. However, mightn't there be another uniqueness argument (based on known or unknown patterns) that eliminates your solution and prefers one of the others? Can you prove that this is not the case in this situation? Are you suggesting that certain invalid puzzles have a 'canonical' solution, somehow better than the other solutions?

I think that I am missing your point entirely. Please elaborate.
re'born
 
Posts: 551
Joined: 31 May 2007

Postby Ruud » Tue May 02, 2006 9:51 am

Hi fermat,

This is not the SudoCue support forum. I already answered this question here: http://www.sudocue.net/forum/viewtopic.php?t=126

However, we can discuss this phenomenon:

It is possible to create a Sudoku that can be solved when using uniqueness methods, but that has multiple solutions when tested by a backtracking solver.

Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby RW » Tue May 02, 2006 1:21 pm

Code: Select all
.------------------.------------------.------------------.
| 2     9     5    | 8     3     4    | 6     7     1    |
| 3     16    8    | 16    7     9    | 24    24    5    |
| 16    4     7    | 16    5     2    | 3     8     9    |
:------------------+------------------+------------------:
| 9     16    4    | 2     8     3    | 5     16    7    |
| 7     5     23   | 4     6     1    | 9     23    8    |
| 16    8     23   | 7     9     5    | 24    12346 36   |
:------------------+------------------+------------------:
| 4     7     9    | 5     2     8    | 1     36    36   |
| 8     3     1    | 9     4     6    | 7     5     2    |
| 5     2     6    | 3     1     7    | 8     9     4    |
'------------------'------------------'------------------'


rep'nA wrote:However, mightn't there be another uniqueness argument (based on known or unknown patterns) that eliminates your solution and prefers one of the others? Can you prove that this is not the case in this situation? Are you suggesting that certain invalid puzzles have a 'canonical' solution, somehow better than the other solutions?


Here's my opinion on the puzzle (if I applied uniqueness technique):

UR in r56c38 => Eliminate 23 from r6c8
UR in r26c78 => Eliminate 4 from r6c8
BUG-lite in r2c24, r3c14, r4c28, r6c18 => Eliminate 16 from r6c8

=> r6c8=empty cell

In a multiple solution puzzle no solution can be better than the other, especially not solutions reached by uniqueness technique as that technique isn't valid when there is no unique solution. If you allow uniqueness technique in a multiple solution puzzle, you will always reach a contradiction (if you do it properly like I did).

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

Postby fermat » Tue May 02, 2006 2:19 pm

Ruud wrote:Hi fermat,

This is not the SudoCue support forum. I already answered this question here: http://www.sudocue.net/forum/viewtopic.php?t=126

However, we can discuss this phenomenon:

It is possible to create a Sudoku that can be solved when using uniqueness methods, but that has multiple solutions when tested by a backtracking solver.

Ruud.


I am missing your point still. I don't see what is wrong with this puzzle.
If it can be solved by people using a valid method, why does anyone care if backtracking fails?
fermat
 
Posts: 105
Joined: 29 March 2006

Re: Unique, unique.

Postby fermat » Tue May 02, 2006 2:24 pm

rep'nA wrote:
I think that I am missing your point entirely. Please elaborate.


I am just trying to find out why this puzzle is not a valid puzzle.

I don't know why I cannot use uniqueness patterns of the 36 23 and 24 pairs to remove all but the digit 1 and solve the puzzle.
fermat
 
Posts: 105
Joined: 29 March 2006

Postby fermat » Tue May 02, 2006 2:28 pm

RW wrote:[ If you allow uniqueness technique in a multiple solution puzzle, you will always reach a contradiction (if you do it properly like I did).

RW


I don't understand why the you don't just do the unique pairs all at once, 36 23 and 24 reulting in a 1. Why is it proper to do it one at a time, for two of the three, then switch methods?
fermat
 
Posts: 105
Joined: 29 March 2006

Postby fermat » Tue May 02, 2006 2:38 pm

RW wrote:[

Here's my opinion on the puzzle (if I applied uniqueness technique):

UR in r56c38 => Eliminate 23 from r6c8
UR in r26c78 => Eliminate 4 from r6c8
BUG-lite in r2c24, r3c14, r4c28, r6c18 => Eliminate 16 from r6c8

=> r6c8=empty cell

RW


I am thinking that many solving methods rely on the candidates having been properly simplified. Since the 6 should have been removed from r6c8 using uniqueness BUG-lite is not a valid method in this case.
fermat
 
Posts: 105
Joined: 29 March 2006

Postby ravel » Tue May 02, 2006 2:55 pm

fermat, i think your questions have been answered very clear:
Ruud wrote:It is possible to create a Sudoku that can be solved when using uniqueness methods, but that has multiple solutions when tested by a backtracking solver.

RW wrote:If you allow uniqueness technique in a multiple solution puzzle, you will always reach a contradiction (if you do it properly like I did).


This is a multiple solution puzzle, what means that it only can be solved (completely) by using trial&error for at least all remaining candidates of one (or more) cells. I dont know anyone who likes to do that.
Any application of the above uniqueness methods is invalid here and therefore leads you anywhere, but to nothing of worth (you could see, that different orders of applying that methods lead to different results - one solution or no solution).
All you can say, when you get a solution this way is that it solves the puzzle, but you know nothing, when the UR elimination leads to no solution .
ravel
 
Posts: 998
Joined: 21 February 2006

Postby fermat » Wed May 03, 2006 12:31 am

Ruud wrote:Hi fermat,

This is not the SudoCue support forum. I already answered this question here: http://www.sudocue.net/forum/viewtopic.php?t=126

However, we can discuss this phenomenon:

It is possible to create a Sudoku that can be solved when using uniqueness methods, but that has multiple solutions when tested by a backtracking solver.

Ruud.


This is a summation for those who wonder what the fuss is.

I was under the impression that uniqueness was a tool to find the single solution in a puzzle that had several possible solutions. This is not so and some extensive discussion threads were pointed out to me by David Bryant at the link provided by Ruud, a few lines above this statement.

Now that I understand I can see that Ruud's comment, again a few lines above, sums it all up perfectly.

The fact that uniqueness CAN be used to find a single solution in a puzzle with many "answers" does not make that puzzle a proper Sudoku.
If a puzzle has more than one valid solution it is not a Sudoku. If using a brute force (trial and error) method discovers multiple (or zero) ways to complete the 9X9 from the given clues the puzzle is invalid, whether or not any technique could produce a single answer.

Thanks to all who helped out here, I have learned from it.
fermat
 
Posts: 105
Joined: 29 March 2006


Return to Help with puzzles and solving techniques

cron