The New Sudoku Players' Forum

[Leren]

This might seem like an odd question from an experienced solver but here goes anyway.

Can a puzzle with a uniqueness pattern actually have more than one solution that fits the clues ?

Just to make the question more concrete consider a puzzle with a 4 cell UR plus one guard digit (that prevents the UR from being exposed).

Is it possible, that if the guard digit is eliminated, the UR pattern would fit the clues (so that the puzzle would in fact have 3 solutions that fit the clues), or is that regarded as cheating by the puzzle creator ?

As a solver, whether this is true or not makes no difference to me. If the puzzle did have 3 solutions I know that the solution that is being looked for is the one where the guard digit is true, so I ignore the 2 other possible solutions and place the guard digit.

It doesn't bother me what the answer is, but the question came up in another forum where a contributor commented that a puzzle with 3 solutions (2 UR solutions plus one with the guard digit True) was a badly constructed puzzle, and I'd like to be able to reply to their comment.

[JasonLion]

Nearly everyone considers the definition of a valid puzzle to include a requirement that there only be one solution. However, that position is not universal.

[Leren]

To spice up this topic a bit you can have look at this old thread on the BUG principle :

http://forum.enjoysudoku.com/the-bug-bivalue-universal-grave-principle-t2352.html

where it says : (my underlining)

Theorem:
BUG grids can have either zero or more than one solution, and so are incompatible with a unique solution puzzle. Hence the puzzle solution must come from the non-BUG candidates. (proof)

This strongly suggests to me that a puzzle may have more than one solution that fits the clues and still be regarded as a valid puzzle, at least where a a BUG + n position is reached.

I don't know enough about the history of this topic to find out whether this statement was subsequently overturned.

Leren

[daj95376]

To me, Uniqueness Testing only applies to puzzles with unique solutions. The second you mention that a puzzle can have zero/multiple solutions, then uniqueness patterns become non-existent. The puzzle also becomes of interest to a select few.

Note: BUG falls under uniqueness testing. I suggest that you review the BUG theorem. I have a feeling that you are coming to an inaccurate conclusion. It says what can and what can not happen in a unique solution puzzle. What can not happen is the BUG pattern!

The use of the term valid is an oxymoron when it comes to Sudoku. Either a puzzle has a unique solution ... or it doesn't. Validity only comes into consideration if the puzzle doesn't have any solutions.

_

[Leren]

On further reflection I can now see that, if a puzzle did have 3 solutions, you would be forced to use a "uniqueness" argument to "solve" the puzzle - the puzzle would not be solvable if you didn't. That doesn't sound right. Uniqueness arguments should at best be elegant shortcuts, but a puzzle should always be solvable by other means, even if they are longer and less elegant.

Leren

[JasonLion]

"Uniqueness" argument only have logical validity if you know in advance that the puzzle only has one solution. If you can't guarantee that in advance, there is no point in even considering uniqueness based techniques as they are meaningless.

[daj95376]

At the risk of hijacking the thread, I think you are putting the cart before the horse with your question. What I've asked myself in the past over a puzzle with an unknown number of solutions: Which techniques are guaranteed to produce eliminations that are common to all possible solutions for the puzzle?

Uniqueness Testing Techniques would be the first to go!!! For all I know, they may be the only ones to go.

Maybe someone has a puzzle with 3-6 solutions that can be examined. Something like:

Code: Select all

 *-----------*
 |..8|3.4|1.2|
 |4..|2.5|..3|
 |...|.9.|...|
 |---+---+---|
 |98.|...|.64|
 |..3|...|2..|
 |24.|...|.19|
 |---+---+---|
 |...|.2.|...|
 |8..|9.3|..1|
 |5.2|7.1|4.6|
 *-----------*

 July 25 ... sans r1c1=6


_

[Leren]

Hi Danny, what I'd be looking for is a puzzle that has, say, 3 solutions : 2 of these solutions should be different only in 4 cells in a UR pattern with the 2 UR digits being swappable in the UR cells in the usual way. The third solution should have the same digits in 3 of the UR cells of one of the first 2 solutions and a different digit in the 4th UR cell. The rest of the third solution may or may not be different in some or all of the non UR cells (except for the clues of course).

[daj95376]

Leren, good luck on finding your desired example. As for the puzzle that I posted:

Code: Select all

  first solution:
  698374152471265983325198647987512364153649278246837519719426835864953721532781496
  +-----------------------------------+
  |  6  9  8  |  3  7  4  |  1  5  2  |
  |  4  7  1  |  2  6  5  |  9  8  3  |
  |  3  2  5  |  1  9  8  |  6  4  7  |
  |-----------+-----------+-----------|
  |  9  8 *7  |  5  1  2  | *3  6  4  |
  |  1  5  3  |  6  4  9  |  2  7  8  |
  |  2  4  6  |  8 *3  7  |  5  1  9  |
  |-----------+-----------+-----------|
  |  7  1  9  |  4  2  6  |  8  3  5  |
  |  8  6  4  |  9  5  3  |  7  2  1  |
  |  5  3  2  |  7  8  1  |  4  9  6  |
  +-----------------------------------+

  second and third solutions:
  758364192469215873321897645985132764613479258247658319134526987876943521592781436
  758364192469215873321897645987152364613479258245638719134526987876943521592781436
  +-----------------------------------+
  |  7  5  8  |  3  6  4  |  1  9  2  |
  |  4  6  9  |  2  1  5  |  8  7  3  |
  |  3  2  1  |  8  9  7  |  6  4  5  |
  |-----------+-----------+-----------|
  |  9  8 57  |  1 35  2  | 37  6  4  |
  |  6  1  3  |  4  7  9  |  2  5  8  |
  |  2  4 57  |  6 35  8  | 37  1  9  |
  |-----------+-----------+-----------|
  |  1  3  4  |  5  2  6  |  9  8  7  |
  |  8  7  6  |  9  4  3  |  5  2  1  |
  |  5  9  2  |  7  8  1  |  4  3  6  |
  +-----------------------------------+


The first solution matches the solution for the original puzzle where r1c1=6 was supplied. The second and third solutions result from r1c1=6 not being present. The first solution matches the third solution in three of the six DP cells. It doesn't match any of the DP cells in the second solution.

Here are the cells common to all three solutions. Basics will generate some eliminations, but not nearly enough to be useful.

Code: Select all

..83.41.24..2.5..332..9.64.98...2.64..3..92.824.....19....26...8..9.3.215.27814.6


_

[JC Van Hay]

Leren, have a look again at this puzzle where I used "UR(18)r25c56=9r5c6" twice to determine its number of solutions.

[Leren]

Hi Danny. Actually, this isn't such a bad example. This is as far as my solver got.

Code: Select all

*--------------------------------------------------------------*
| 67    59    8      | 3     67    4      | 1     59    2      |
| 4     67    19     | 2     16    5      | 89    78    3      |
| 3     2     15     | 18    9     78     | 6     4     57     |
|--------------------+--------------------+--------------------|
| 9     8    *57     | 15   *135   2      |*37    6     4      |
| 16    15    3      | 46    47    9      | 2     57    8      |
| 2     4    *567    | 68   *35    78     |*357   1     9      |
|--------------------+--------------------+--------------------|
| 17    13    49     | 45    2     6      | 89    38    57     |
| 8     67    46     | 9     45    3      | 57    2     1      |
| 5     39    2      | 7     8     1      | 4     39    6      |
*--------------------------------------------------------------*

I can see that there is a six cell 357 DP in r46c357. Following normal "uniqueness" practice I can say that either r4c5 = 1 or r6c3 = 6 to avoid the DP being exposed. It's easy to show that r4c5 = 1 => r6c3 = 6 and vice versa, so I can place those digits in those cells and I get the "unique" first solution. So if I'd had that particular uniqueness move in my solver I would have completely solved the puzzle to the "unique" first solution and not been aware that there are 2 other "non-unique" solutions that fit the clues (and are related to each other by swapping the 3's, 5's and 7's around in the six DP cells).

So, is this a well designed puzzle? Did the puzzle creator "want" me to find the "unique" first solution and ignore the second and third "non-unique" solutions ?

Leren

[champagne]

Hi leren,

May be a late comment.

If you have a puzzle with more than one solution, you can't solve it using logical rules.

The best you can do is to end with one or more unavoidable sets that you recognize. (UR is the simplest, but any unavoidable set can be the end for a puzzle with 2 solutions).

So unless you are prepared to look for such UAs, you are better off solving puzzles with only one solution, what is on my side the requirement for a sudoku.

Then, you can use the uniqueness rules, otherwise, don't use it.

moreover, don't forget that for hardest puzzle, the UR threat is often a very efficient shortcut (abi loop for example). Then again, you must check before that the puzzle has a unique solution (is a true sudoku)

[daj95376]

So, is this a well designed puzzle? Did the puzzle creator "want" me to find the "unique" first solution and ignore the second and third "non-unique" solutions ?

As I mentioned in my post, this is Dan's July 25th puzzle where I removed the given r1c1=6. It was a lucky stab at creating a puzzle with multiple solutions for you to examine.

I'm still not sure how far logical steps would reduce the puzzle. Your results show reasonable advancement. As champagne indicated, logical steps must run into a wall before reaching a single solution. I almost modified my solver to see how far it would get on reducing the puzzle. Mostly because I'd like to see if any of the non-uniqueness techniques would produce an erroneous elimination. The more I think about it, the less likely I think it will happen. This is based upon results from people who refused to use Uniqueness Testing in their solutions.

_

[David P Bird]

All this is rather old hat. It's generally accepted that a good puzzle will only have one solution while a badly composed one may have multiple solutions. So the challenge for a good puzzle is to find the single solution and for a bad one it is to find any solution.

If the composer of a bad puzzle rejects a valid solution because it wasn't the one he wanted the onus is on him to demonstrate why and also where in the puzzle description is any mention made of his determining rule.

If the puzzle has an odd number of solutions then using uniqueness methods will never prevent a sole survivor being found. It could be that the composer of a bad puzzle considers that this is the correct solution but if so he should have said so in the puzzle description. Only solvers who haven't employed all the uniqueness deductions open to them will ever find him out though.

However, if a puzzle turns out to be unsolvable after using uniqueness methods, perhaps repeatedly, it must have an even number of solutions - remembering that zero is an even number. It is then the solver's choice whether to bother restarting the puzzle having identified this.

TAGdpbUniqueness

[Edit TAG added]

[blue]

All this is rather old hat. It's generally accepted that a good puzzle will only have one solution while a badly composed one may have multiple solutions. So the challenge for a good puzzle is to find the single solution and for a bad one it is to find any solution.

If the composer of a bad puzzle rejects a valid solution because it wasn't the one he wanted the onus is on him to demonstrate why and also where in the puzzle description is any mention made of his determining rule.

Bravo