## Uniqueness

Advanced methods and approaches for solving Sudoku puzzles
RW wrote:That should be quite obvious. The logic behind uniqueness reductions is [...]

Yes, it *should* be obvious. The example is intended for those for whom it isn't.
r.e.s.

Posts: 337
Joined: 31 August 2005

r.e.s. wrote:
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.) ...

.....
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.

When I use simple methods I come down to this grid with two contradictory UR type 1s. If you pick either you get to see the remaing two possible answers.

Code: Select all
`.------------.------------.------------.| 3   4   5  | 9   1   8  | 6   7   2  || 1   6   7  | 5   2   3  | 8   49  49 || 8   9   2  | 47  6   47 | 1   5   3  |:------------+------------+------------:| 9   8   3  | 6   7   2  | 4   1   5  || 2   5   6  | 1   4   9  | 7   3   8  || 7   1   4  | 8   3   5  | 9   2   6  |:------------+------------+------------:| 46  7   9  | 2   5   46 | 3   8   1  || 46  2   8  | 3   9   1  | 5   46  7  || 5   3   1  | 47  8   467| 2   469 49 |'------------'------------'------------'`

So, I am not sure if your premise was correct. Could I see a better example?
fermat

Posts: 105
Joined: 29 March 2006

RW wrote:
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

I respect your judgement but still have reservations about whether using UR can actually make the puzzle worse. Can it?
fermat

Posts: 105
Joined: 29 March 2006

fermat wrote:I respect your judgement but still have reservations about whether using UR can actually make the puzzle worse. Can it?

In the example I gave, it was exactly the use of UR that "made the puzzle worse". As I said, I'm sure better examples can be found -- I encourage you to try looking for some.
r.e.s.

Posts: 337
Joined: 31 August 2005

r.e.s.

Applying a technique on candidates that are not there will certainly fail.
That is what you did because you refused to simplify.

The second UR was already a destroyed when you acted on the first one. You had already found 2 of 4 solutions.
fermat

Posts: 105
Joined: 29 March 2006

fermat wrote:r.e.s.

Applying a technique on candidates that are not there will certainly fail.
That is what you did because you refused to simplify.

The second UR was already a destroyed when you acted on the first one. You had already found 2 of 4 solutions.

Both UR's were applied to existing candidates. I "refused to simplify" (i.e. remove some candidates by simple moves) because the purpose was to show that in a multi-solution puzzle, UR moves *could* be made that will produce a grid with no solution.
r.e.s.

Posts: 337
Joined: 31 August 2005

r.e.s. wrote:I "refused to simplify" (i.e. remove some candidates by simple moves) because the purpose was to show that in a multi-solution puzzle, UR moves *could* be made that will produce a grid with no solution.

I'm not sure I see that this only applies to UR. Is UR the only solving method that fails when candidates are not properly updated?
In this case I mean "update" changes made by the previous operation, I accept the position you started using UR.

I do see that UR can be dangerously applied, interesting example!
fermat

Posts: 105
Joined: 29 March 2006

It's not a matter of "not properly updating", as this somewhat better 2-solution example shows ...

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

Code: Select all
`+----------------+----------------+----------------+| 9    138  58   | 4    167  356  | 2    35   367  | | 6    34   45   | 357  8    2    | 1    3459 379  | | 2    134  7    | 135  16   9    | 8    345  36   | +----------------+----------------+----------------+| 3    9   *46   | 8    5    7    |*46   1    2    | | 48   2   *468  | 9    3    1    |*46   7    5    | | 7    5    1    | 2    46   46   | 39   8    39   | +----------------+----------------+----------------+| 14   47   9    | 6    1247 34   | 5    23   8    | | 458  4678 2    | 357  9    345  | 37   36   1    | | 15   67   3    | 157  127  8    | 79   269  4    | +----------------+----------------+----------------+`

At this point there *are* some "non-simple" moves possible (besides UR), but the UR would probably be considered the simplest (though invalid, since the puzzle has more than one solution) ...

R4C37, R5C37 form a Type-1 Unique Rectangle on <46>:
R5C3 - can remove <46> from <468> leaving <8>

which results in a grid with *no* solutions ...

Code: Select all
`+----------------+----------------+----------------+| 9    138  5    | 4    167  356  | 2    35   367  | | 6    34   45   | 357  8    2    | 1    3459 379  | | 2    134  7    | 135  16   9    | 8    345  36   | +----------------+----------------+----------------+| 3    9    46   | 8    5    7    | 46   1    2    | | 4    2    8    | 9    3    1    | 46   7    5    | | 7    5    1    | 2    46   46   | 39   8    39   | +----------------+----------------+----------------+| 14   47   9    | 6    1247 34   | 5    23   8    | | 458  4678 2    | 357  9    345  | 37   36   1    | | 15   67   3    | 157  127  8    | 79   269  4    | +----------------+----------------+----------------+`
r.e.s.

Posts: 337
Joined: 31 August 2005

Much better example.

UR is a shortcut, for me, I don't know of a case where it is the only solution. ( I am no expert. )

Is it a shortcut, in this case, to show that there is no solution?

At least, no valid Sudoku solution?
fermat

Posts: 105
Joined: 29 March 2006

fermat wrote:Much better example.

UR is a shortcut, for me, I don't know of a case where it is the only solution. ( I am no expert. )

Is it a shortcut, in this case, to show that there is no solution?

At least, no valid Sudoku solution?

The puzzle has two solutions, so the UR cannot be validly applied. If it's invalidly applied nevertheless, it leads to a grid with no solutions. I wouldn't call that a shortcut.
r.e.s.

Posts: 337
Joined: 31 August 2005

r.e.s. wrote:The puzzle has two solutions, so the UR cannot be validly applied. If it's invalidly applied nevertheless, it leads to a grid with no solutions. I wouldn't call that a shortcut.

? Hello??

It may be a shortcut to realizing an invalid puzzle.
fermat

Posts: 105
Joined: 29 March 2006

How could UR be "a shortcut to realizing an invalid puzzle"?
r.e.s.

Posts: 337
Joined: 31 August 2005

r.e.s. wrote:How could UR be "a shortcut to realizing an invalid puzzle"?

Well, if UR spots a candidate to remove and the result is a puzzle with no solution then the puzzle is invalid.
fermat

Posts: 105
Joined: 29 March 2006

You asked "Is it a shortcut, in this case, to show that there is no solution?" That clouded the issue, because the puzzle in this case has two solutions.

Of course, if UR produces a grid with no solution, then the puzzle doesn't have exactly one solution (is "invalid") -- it doesn't mean the puzzle has no solution. In any case I don't know how useful that would be as a shortcut.
r.e.s.

Posts: 337
Joined: 31 August 2005

r.e.s. wrote:How could UR be "a shortcut to realizing an invalid puzzle"?

Well, if UR is valid, it is used and gets a grid with no solution, we are done, invalid puzzle.

Not using UR and searching with other methods should be slower.
fermat

Posts: 105
Joined: 29 March 2006

PreviousNext