Uniqueness

Advanced methods and approaches for solving Sudoku puzzles

Uniqueness

Postby Finlip » Thu Aug 31, 2006 12:26 pm

Talking about uniqueness not being taken by some as a valid method to solve sudokus, I have one question to ask you people.

If we are able to solve a sudoku even after using uniqueness conditions, won't we then prove that the solution is indeed unique?
Finlip
 
Posts: 49
Joined: 15 July 2005

Postby udosuk » Thu Aug 31, 2006 1:29 pm

I'm waiting for people to show us an example that using uniqueness moves you could work out a solution, but otherwise the puzzle has multiple solutions... I believe such an example should exist...

I have no problem to apply the uniquesness move if the puzzle is a vanilla (no additional properties) and you're guaranteed it's a valid puzzle... But I wouldn't use it on variant puzzles (e.g. diagonal, non-consecutive), even if on some occasions it could work...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby tarek » Thu Aug 31, 2006 1:38 pm

I don't have any example at hand.....

But I've seen several examples of puzzles with multiple solutions where Uniqueness (& other techniques based on a single solution outcome) has resulted in reaching ONE of the solutions......

So reaching a solution does not mean it is unique if Uniqueness was used....... if there is a way, I would like to know. I assume the same goes for BUGging, Almost UR,........

I would go for puzzles from reliable sources, or check validity of the puzzles using an online solver.

tarek
User avatar
tarek
 
Posts: 2610
Joined: 05 January 2006

Postby daj95376 » Thu Aug 31, 2006 6:32 pm

To me, order is everything. Which condition comes first determines the outcome.

If a puzzle has a unique solution, then I see Uniqueness as just another technique to solve it -- just like Chains. If a puzzle has multiple solutions, then Uniqueness (and probably Chains) may or may not lead you to one of the solutions. In any event, Uniqueness and Chains were never meant to guarantee that a puzzle has a unique solution!

If every solver had a backtracking uniqueness tester and used it first thing on every puzzle, then all of the negative arguments on Uniqueness as a technique would be mute.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Uniqueness is misleading?

Postby keith » Thu Aug 31, 2006 11:17 pm

The argument against Uniqueness techniques is usually that, if a puzzle has more than one solution, a uniqueness argument might lead to a solution, and not reveal the multiple soultions.

Except:

1. No one is interested in "solving" puzzles with multiple solutions. (See the "Sudokus of Shame" thread.)

2. There are computer algorithms that can check uniqueness.

In my own experience, it is usually clear that something is wrong in a multiple-solution puzzle, whether you use uniqueness arguments or not.

The thread I would like to start is: Sudokus with an even number of solutions < 8. And, sudokus with an odd number of solutions <7. The goal would be to find new uniqueness patterns and solution techniques.

Is anyone interested?

Keith
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

Yes!

Postby keith » Thu Aug 31, 2006 11:19 pm

daj95376 wrote:If every solver had a backtracking uniqueness tester and used it first thing on every puzzle, then all of the negative arguments on Uniqueness as a technique would be mute.


Sudoku Susser has such a tester.
keith
2017 Supporter
 
Posts: 209
Joined: 03 April 2006

Postby fermat » Fri Sep 01, 2006 6:06 am

udosuk wrote:I'm waiting for people to show us an example that using uniqueness moves you could work out a solution, but otherwise the puzzle has multiple solutions... I believe such an example should exist...



I have been down that road, here is a link to a 5 solution puzzle.
http://forum.enjoysudoku.com/viewtopic.php?t=3994


The problem is, there are 5 solutions. Uniqueness just picks one of them.
fermat
 
Posts: 105
Joined: 29 March 2006

Re: Uniqueness is misleading?

Postby udosuk » Fri Sep 01, 2006 6:09 am

keith wrote:Sudoku Susser has such a tester.

Ditto for Simple Sudoku.

keith wrote:No one is interested in "solving" puzzles with multiple solutions.

I was interested in "solving" the following puzzles:
Code: Select all
1....4...
.......9.
...6.....
..5.3....
.......29
.6.......
.....6...
.........
.38...5..

....5....
..8...7..
.5.....9.
.........
5...6...7
.........
.1.....4.
..9...2..
....4....

.........
.....6..3
...9....2
.........
.2....8..
.......7.
........6
9..18.5..
....5....

.........
.1......3
.....8...
.....9.4.
.6.......
..5......
8.43.....
.......2.
.........

Can you guess why?:?:

PS: Thanks for the link fermat... Very interesting story...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Re: Uniqueness is misleading?

Postby fermat » Sat Sep 02, 2006 6:09 am

udosuk wrote:I was interested in "solving" the following puzzles:

Can you guess why?:?:


Um, less than 17 givens?

PS: Thanks for the link fermat... Very interesting story...


You are welcome!
fermat
 
Posts: 105
Joined: 29 March 2006

Re: Uniqueness is misleading?

Postby udosuk » Sat Sep 02, 2006 9:04 am

fermat wrote:Um, less than 17 givens?

Yes they're... But even if I know Simple Sudoku tells me they have many solutions, I still use the program to work out a unique solution for each of them... How and why?

Perhaps this could be a riddle posted in the Off-Topic forum...:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby RW » Sat Sep 02, 2006 3:08 pm

udosuk wrote:I was interested in "solving" the following puzzles:

Can you guess why?:?:


The first one is an unique diagonal puzzle, bet the other once are unique with some other extra constraints.

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

Postby udosuk » Sat Sep 02, 2006 4:12 pm

RW wrote:The first one is an unique diagonal puzzle, bet the other once are unique with some other extra constraints.

Right! But what other extra constraints? For a normal pearson having never seen those grids, would he/she be able to find out the extra constraints on his/her own?

Sounds like a hard challenge - you're given a sudoku puzzle which would give multiple solutions under normal rules. You're required to find the extra constraint that would give it a unique solution...:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Ruud » Sat Sep 02, 2006 4:32 pm

#1 is indeed a Sudoku-X
#3 is a DG Sudoku
#4 is a Windoku

These can all be solved by my program.

#2 could be a non-consecutive Sudoku, but I cannot fully solve it.

Ruud
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby r.e.s. » Sat Sep 02, 2006 9:15 pm

fermat wrote:I have been down that road, here is a link to a 5 solution puzzle. [...]

The problem is, there are 5 solutions. Uniqueness just picks one of them.

Just to dispel any notion that unique-solution strategies can be relied upon to "pick one of them" when there are multiple solutions ...

Here's a puzzle with 4 solutions, but UR methods miss all of them, and instead reduce the candidate grid to one with *no* solutions. (I'm sure someone can find a nicer example, as this is just the first one I ran across.) ...

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


+-------------------+-------------------+-------------------+
| 1348  345   45    | 1479  189   4789  | 6     34579 2     |
| 146   46    7     | 5     1269  3     | 8     49    149   |
| 13468 9     2     | 1467  168   4678  | 147   3457  13457 |
+-------------------+-------------------+-------------------+
| 469   8     3     | 69    7     2     | 4     1     456   |
| 2679  2567  569   | 169   4     569   | 7     3567  35678 |
| 467   1     456   | 8     3     56    | 9     2     4567  |
+-------------------+-------------------+-------------------+
| 24679 2467  469   | 24679 2569  45679 | 3     8     14679 |
| 24679 2467  8     | 3     269   1     | 5     4679  4679  |
| 5     23467 1     | 24679 2689  46789 | 247   4679  4679  |
+-------------------+-------------------+-------------------+

Simple moves lead to the first of two UR ...

Code: Select all
+-------------+-------------+---------------+
| 3   4   5   | 79  1   789 | 6   79    2   |
| 1   6   7   | 5   2   3   | 8  *49   *49  |
| 8   9   2   | 47  6   47  | 1   5     347 |
+-------------+-------------+---------------+
| 69  8   3   | 69  7   2   | 4   1     5   |
| 2   5   69  | 1   4   69  | 7   3     8   |
| 7   1   4   | 8   3   5   | 9   2     6   |
+-------------+-------------+---------------+
| 469 7   69  | 2   5   46  | 3   8     1   |
| 46  2   8   | 3   9   1   | 5   467   47  |
| 5   3   1   | 467 8   467 | 2  *4679 *479 |
+-------------+-------------+---------------+


R2C89, R9C89 form a Type-4 Unique Rectangle on <49>:
R9C8 - can remove <4> from <4679> leaving <679>
R9C9 - can remove <4> from <479> leaving <79>

This leads to a second UR ...

Code: Select all
+-------------+-------------+-------------+
| 3   4   5   | 79  1   789 | 6   79  2   |
| 1   6   7   | 5   2   3   | 8   49  49  |
| 8   9   2   |*47  6  *47  | 1   5   347 |
+-------------+-------------+-------------+
| 69  8   3   | 69  7   2   | 4   1   5   |
| 2   5   69  | 1   4   69  | 7   3   8   |
| 7   1   4   | 8   3   5   | 9   2   6   |
+-------------+-------------+-------------+
| 469 7   69  | 2   5   46  | 3   8   1   |
| 46  2   8   | 3   9   1   | 5   467 47  |
| 5   3   1   |*467 8  *467 | 2   679 79  |
+-------------+-------------+-------------+


R3C46, R9C46 form a Type-2 Unique Rectangle on <47>:
R7C6 - can remove <6> from <46> leaving <4>
R9C8 - can remove <6> from <679> leaving <79>

But the resulting <4> in R7C6 eliminates the only remaining possible positions for a 4 in R9, producing a grid with no solution ...

Code: Select all
+-------------+-------------+-------------+
| 3   4   5   | 79  1   789 | 6   79  2   |
| 1   6   7   | 5   2   3   | 8   49  49  |
| 8   9   2   | 47  6   47  | 1   5   347 |
+-------------+-------------+-------------+
| 69  8   3   | 69  7   2   | 4   1   5   |
| 2   5   69  | 1   4   69  | 7   3   8   |
| 7   1   4   | 8   3   5   | 9   2   6   |
+-------------+-------------+-------------+
| 469 7   69  | 2   5   4   | 3   8   1   |
| 46  2   8   | 3   9   1   | 5   467 47  |
| 5   3   1   | 67  8   67  | 2   79  79  |
+-------------+-------------+-------------+


So the blanket use of unique-solution strategies (i.e. when it isn't known whether there's a unique solution) is a kind of guessing -- it doesn't always lead to one of multiple solutions, even though it may just happen to do so for no legitimate reason.
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby RW » Sat Sep 02, 2006 9:56 pm

r.e.s wrote:Just to dispel any notion that unique-solution strategies can be relied upon to "pick one of them" when there are multiple solutions ...


That should be quite obvious. The logic behind uniqueness reductions is:

Code: Select all
If cell C=a gives a valid solution, then there will be at least one other valid solution to the puzzle.


If we are sure that the puzzle has only one solution, we may eliminate 'a' from 'C'. If it is possible that the puzzle actually has multiple solutions, then the information is totally useless.

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

Next

Return to Advanced solving techniques