Uniqueness Question

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

Uniqueness Question

Postby Leren » Tue Jul 28, 2015 10:49 pm

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.
Leren
 
Posts: 2618
Joined: 03 June 2012

Re: Uniqueness Question

Postby JasonLion » Wed Jul 29, 2015 12:57 am

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.
User avatar
JasonLion
2017 Supporter
 
Posts: 604
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: Uniqueness Question

Postby Leren » Wed Jul 29, 2015 1:21 am

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
Leren
 
Posts: 2618
Joined: 03 June 2012

Re: Uniqueness Question

Postby daj95376 » Wed Jul 29, 2015 1:52 am

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.

_
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Uniqueness Question

Postby Leren » Wed Jul 29, 2015 3:55 am

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
Leren
 
Posts: 2618
Joined: 03 June 2012

Re: Uniqueness Question

Postby JasonLion » Wed Jul 29, 2015 12:05 pm

"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.
User avatar
JasonLion
2017 Supporter
 
Posts: 604
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: Uniqueness Question

Postby daj95376 » Wed Jul 29, 2015 3:44 pm

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

_
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Uniqueness Question

Postby Leren » Wed Jul 29, 2015 9:43 pm

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).
Leren
 
Posts: 2618
Joined: 03 June 2012

Re: Uniqueness Question

Postby daj95376 » Thu Jul 30, 2015 5:45 am

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

_
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Uniqueness Question

Postby JC Van Hay » Thu Jul 30, 2015 9:12 am

Leren, have a look again at this puzzle where I used "UR(18)r25c56=9r5c6" twice to determine its number of solutions.
JC Van Hay
 
Posts: 618
Joined: 22 May 2010

Re: Uniqueness Question

Postby Leren » Thu Jul 30, 2015 10:01 am

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
Leren
 
Posts: 2618
Joined: 03 June 2012

Re: Uniqueness Question

Postby champagne » Thu Jul 30, 2015 11:42 am

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)
champagne
2017 Supporter
 
Posts: 5496
Joined: 02 August 2007
Location: France Brittany

Re: Uniqueness Question

Postby daj95376 » Thu Jul 30, 2015 2:52 pm

Leren wrote: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.

_
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Uniqueness Question

Postby David P Bird » Thu Jul 30, 2015 5:19 pm

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]
Last edited by David P Bird on Wed Dec 14, 2016 5:48 pm, edited 1 time in total.
David P Bird
2010 Supporter
 
Posts: 935
Joined: 16 September 2008
Location: Middle England

Re: Uniqueness Question

Postby blue » Thu Jul 30, 2015 8:21 pm

David P Bird wrote: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 :!:
blue
 
Posts: 572
Joined: 11 March 2013

Next

Return to Help with puzzles and solving techniques