Uniqueness Question

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

Re: Uniqueness Question

Postby Leren » Thu Jul 30, 2015 11:15 pm

Thanks David, I think your post is the definitive answer to my question. I particularly like your use of the term survivor (as opposed to my working term "unique" in inverted commas).

So using your terminology, on another forum I solved a puzzle with a uniqueness move and found the one survivor of a puzzle that actually had three solutions. Another solver pointed out that the other two solutions existed and criticized the puzzle maker for creating a puzzle with multiple solutions.

My understanding is that on this forum all puzzles have one solution, unless the puzzle provider says something to the contrary.

Leren
Leren
 
Posts: 2706
Joined: 03 June 2012

Re: Uniqueness Question

Postby m_b_metcalf » Tue Aug 11, 2015 8:10 am

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


All this is true. However, there is one context in which puzzles, individually, have multiple solutions but, collectively, only one: that is for samurai. A technique there is to use brute force to find all the solutions to an individual puzzle, and to retain the cells with common values as an advance in the solution. This typically helps a neighouring puzzle also to advance, etc.

Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8093
Joined: 15 May 2006
Location: Berlin

Re: Uniqueness Question

Postby keith » Tue Oct 20, 2015 7:48 am

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

I asked a similar question years ago, and got no responses. I was interested in puzzles that had no solutions, or that had countable solutions. I was looking for new uniqueness arguments. It turned out, no one was interested in studying "invalid" puzzles.

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

Re: Uniqueness Question

Postby eleven » Tue Oct 20, 2015 1:57 pm

keith wrote:I asked a similar question years ago, and got no responses. I was interested in puzzles that had no solutions, or that had countable solutions. I was looking for new uniqueness arguments. It turned out, no one was interested in studying "invalid" puzzles.

I can't see any sense in studying uniqueness patterns in non-unique puzzles.
If you find one, all you can say is that either all resolutions of the pattern are part of a solution or none of them.
eleven
 
Posts: 1444
Joined: 10 February 2008

Re: Uniqueness Question

Postby keith » Sat Oct 24, 2015 7:14 pm

eleven wrote:
keith wrote:I asked a similar question years ago, and got no responses. I was interested in puzzles that had no solutions, or that had countable solutions. I was looking for new uniqueness arguments. It turned out, no one was interested in studying "invalid" puzzles.

I can't see any sense in studying uniqueness patterns in non-unique puzzles.
If you find one, all you can say is that either all resolutions of the pattern are part of a solution or none of them.

If you understand what makes a puzzle not unique, you then have a criterion to apply to solve unique puzzles. No?

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

Re: Uniqueness Question

Postby champagne » Sun Oct 25, 2015 8:57 am

keith wrote:If you understand what makes a puzzle not unique, you then have a criterion to apply to solve unique puzzles. No?

Keith


endless question.

The simplest answer is in the facts. If you find 2 solutions, the puzzle does not have a unique solution. Quick, easy to check.

Years ago, one underlying reason has been shown. If you consider one solution grid, you can define many unavoidable sets, cells groups where at minimum one cell must be given to have a unique solution.

The simplest unavoidable set is a four cells rectangle in one band/stack with only 2 digits, but all unavoidable sets with 12 or less cells have been described. The simplest 18 cells unavoidable set is made or 2 rows/columns in the same band/stack.

That property has been used by the team checking that a 16 clues puzzle can not exist.

If you find another property easy to use, you are welcome.

EDIT: the unavoidable sets property has been used as solving technique. The most common are UR's and UL's
champagne
2017 Supporter
 
Posts: 5572
Joined: 02 August 2007
Location: France Brittany

Re: Uniqueness Question

Postby eleven » Sun Oct 25, 2015 6:46 pm

It's my impression too, that there is nothing relevant left in the investigations of, how uniqueness patterns could be used.
We have unique rectangles, MUGs, BUGs and reversed BUGs, digit symmetries and the studies and applications of unavoidable sets (those in computer calculations).
AFAIK for many years now there was not the slightest new idea, what else could be useful.
eleven
 
Posts: 1444
Joined: 10 February 2008

Re: Uniqueness Question

Postby David P Bird » Wed Dec 14, 2016 5:46 pm

Here's a corker from < The current Sysudoku blog>.
John Welch wrote:No, Denis [Berthier]. Unique Rectangle methods don’t assume uniqueness. Instead they assume there is no uniqueness failure of this simple deadly rectangle form. That’s all. The same common sense defense can be offered for extended rectangles and other defined patterns of multiple solution. Unique rectangle is simply not based on the general assumption of uniqueness.

What does the sentence in red mean? My interpretation is that the UR pattern is localised in a sub-puzzle and only that sub-puzzle is assumed to be unique.
But it's a fallacy to say that assuming local uniqueness doesn't count! If a local sub-puzzle isn't unique then neither is the entire puzzle.

Consider when that local assumption is wrong and the puzzle has two possible solutions, one for each way of placing the member digits in a particular UR, then using a uniqueness method to force a non-member digit into it will render the whole puzzle unsolvable and this may not be apparent until much later.

Effectively therefore using a uniqueness based method assumes that the puzzle has an odd number of solutions. If it has more than one then any way of completing the grid is enough to meet the challenge.

See <my earlier post>.

DPB
David P Bird
2010 Supporter
 
Posts: 939
Joined: 16 September 2008
Location: Middle England

Re: Uniqueness Question

Postby blue » Wed Dec 14, 2016 9:05 pm

David P Bird wrote:
John Welch wrote:No, Denis [Berthier]. Unique Rectangle methods don’t assume uniqueness. Instead they assume there is no uniqueness failure of this simple deadly rectangle form. That’s all. The same common sense defense can be offered for extended rectangles and other defined patterns of multiple solution. Unique rectangle is simply not based on the general assumption of uniqueness.

What does the sentence in red mean?

Hi David,

I think he's saying that it isn't necessary to go "all the way" and assume that the puzzle has one and only one solution -- that the only thing that's "really necessary", is that for the particular UR, however many solutions the puzzle has (if any), none of them has only the two UR digits in the UR cells.

P.S.: I don't know what his bottom line goal would be -- to not make an elimination (or placement) that reduces the solution list in any way ... or to not make one that reduces it from a non-empty list, to an empty list. If it's the latter, then he could replace "however many solutions the puzzle has (if any), none of them has only the two UR digits in the UR cells", with "if the puzzle has solutions, then at least one of them doesn't have only the two UR digits in the UR cells". Either way, it seems like a silly "assumption" to make -- especially if you were reluctant to make the "full" uniqueness assumption.
blue
 
Posts: 572
Joined: 11 March 2013

Re: Uniqueness Question

Postby StrmCkr » Wed Dec 14, 2016 11:20 pm

no, hes flat out saying that uniqueness patterns are not based on the assumption of its "one solution" , and that they can remove clues regardless of the grid holding 1 or more more solutions even though the deduction its self is based on avoiding a multi solution state.

Unique rectangle is simply not based on the general assumption of uniqueness.


which is utter bs, really wish this author would actually join this forum so we can refute his large claims readily before he publishes further catastrophic blog post like that one.

how the duck is a muti solution state avoidance not based on a muti solution state? its like he's never seen a 3 solution puzzle where any of the uniqueness arguments reduce it down to 1 solution completely disregarding the other 2 solutions.

even worse is that he tries to claim a bunch of stuff is all thanks to Denis's book instead of the collaborated efforts of this very forum, whom his book is based off of.

funnier yet is the exclusion of the UR type 1.1, which shatters his entire post.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 604
Joined: 05 September 2006

Re: Uniqueness Question

Postby David P Bird » Wed Dec 14, 2016 11:46 pm

Blue,
As a player of the old school I believe we should avoid making blind leaps of faith in crafting our solutions. We should be confident that the inferences we draw must be sound whatever the surrounding circumstances. The use of pattern theorems makes this much easier. But the uniqueness theorems are conditional on a puzzle having a unique solution and can't be proved otherwise.

It then follows that a player who says that he's assuming a sub-puzzle to be unique without assuming the same for the whole puzzle, wants to have his cake and eat it. In one part of the puzzle he will be making a leap of faith contrary to his standpoint! He won't be able to prove his assumption but only sometimes disprove it if the rest of the puzzle can't be solved later on.

David
David P Bird
2010 Supporter
 
Posts: 939
Joined: 16 September 2008
Location: Middle England

Re: Uniqueness Question

Postby ghfick » Fri Dec 16, 2016 12:41 pm

So, for any puzzle, we first wish to have a solution count, call it C, and a complete list of all C of the solutions. There are algorithms that guarantee such a complete list. I believe that Andrew Stuart's solver contains such an algorithm implementation. Next, we would like to see the puzzle with its givens and solved cells that are a part of each of the solutions in the list. Such a display will show all the completed cells and the incomplete cells. For each incomplete cell, there would be a list of the candidates. The lists of candidates for the incomplete cells determine the constraints on the set of solutions. Again, Andrew's solver can [in principle] be used to reach such a display by unchecking the uniqueness strategies [4 of them?] and taking the solver through to where the solver says 'Run out of known strategies. Use 'Solution Count' to check to see if the puzzle has only one solution'. I say 'in principle' because his solver does not guarantee to solve all puzzles. In any case, one could compare the reached puzzle display with the list of puzzles to study the nature of the constraints. Next comes the part of the process of most interest to the Sudoku community. We then examine and debate the various paths to this reached puzzle display. What is possible by a human? What is logical? What is elegant? What is guessing? etc... The new wrinkle when C>1, is that a path may only lead to a portion of the complete list. One or more strategies in such a path implicitly conceals some of the solutions. Such a path would be judged inferior to a path that leads to all C solutions. We might wish, in principle, to require our paths always yield all the solutions or at least do not conceal any of them. So, can paths which include strategies based on uniqueness conceal some solutions? I believe the answer is yes. Can paths which include strategies based on uniqueness give incorrect solutions? On this matter, I am not sure. Can paths which include strategies based on uniqueness still yield all C solutions with some puzzles? I think the answer here is yes. In part, John is pointing this out. Can paths which do not include strategies based on uniqueness still fail to yield the complete list of C solutions? Here is the answer is clearly yes for both C=1 and C>1. It would be good to have a set of example puzzles for all of these contingencies. Maybe they could be gleaned from the many puzzles in the 'Sudokus of Shame' thread.
ghfick
 
Posts: 15
Joined: 06 April 2016

Re: Uniqueness Question

Postby JasonLion » Fri Dec 16, 2016 1:11 pm

ghfick, it would be helpful if you would clarify what it is you are trying to explore. None of that is required when working on puzzles with only one solution, which most of us limit ourselves to. I expect you probably could restate the uniqueness techniques so they help enumerate possible solutions, but why would you bother to do so? There are far simpler ways to enumerate solutions using brute force.
User avatar
JasonLion
2017 Supporter
 
Posts: 620
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: Uniqueness Question

Postby champagne » Fri Dec 16, 2016 2:49 pm

Hi ghfick,

Another way to comment your post.

If the puzzle is a sudoku (one and only one solution), the very old sudoku explainer can solve it without any use of uniqueness assumption. You always find chain nets with imbricated subchains clearing candidates. Some of them are so complex that you would not like them, but they exist and the program can find them (sometimes after hours).

Using the uniqueness assumption just gives you faster ways to come to the solution.

If the puzzle is not a sudoku, then the process fails.

And as writes JasonLion, the easiest way to check uniqueness is the brute force.
champagne
2017 Supporter
 
Posts: 5572
Joined: 02 August 2007
Location: France Brittany

Re: Uniqueness Question

Postby David P Bird » Fri Dec 16, 2016 3:13 pm

Hi Gordon, - a third response for you.
What you want is a brute force solver that can list all the available solutions for a non-unique puzzle. Perhaps other contributors can advise you of any that are available and how to use them (they are likely to require DOS command lines). However they will be based on brute force algorithms.

Solvers that use a restricted repertoire of strategies won't be able to completely solve all puzzles, but will be able to make a sub-set of eliminations that must be common to all solutions provided that uniqueness based methods are turned off.

If uniqueness methods are activated then for any sub-pattern that has two ways of being completed these solvers will use the inference that one of the possible ways of preventing that must be true and make the consequential eliminations. They may therefore eliminate candidates that are true in the different solutions for a non-unique puzzle even for the complex ones that can't be resolved completely.

For the simpler puzzles these solvers will produce a single solution if the number of solutions is odd, or a 'no solution (invalid puzzle)' if the number of solutions is even.

To help understand that, suppose that there are three independent UR patterns producing 8 possible solutions. Preventing all three of them will leave no solution at all.
Now suppose that there is a ninth solution. The solver will find the one solution that exists where none of the URs is filled using just two digits.

Therefore using uniqueness methods for puzzles with more than one solution runs the risk of failing to find any solution at all when the number of solutions is even. To do this without the assurance that the puzzle is unique is therefore no better than using a trial and error approach hoping that the puzzle has an odd number of solutions.

David

PS I don’t know of any puzzles with an even number of solutions. I suspect that this is because the examples in the hall of shame were produced with the help of a checker that included uniqueness methods.
David P Bird
2010 Supporter
 
Posts: 939
Joined: 16 September 2008
Location: Middle England

PreviousNext

Return to Help with puzzles and solving techniques