Uniqueness Strategies

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

Uniqueness Strategies

Postby yellowpig » Wed Jul 05, 2017 8:19 am

My apologies if this has been discussed to death in the past, but what is the current feeling amongst solvers about uniqueness strategies (such as uniqueness rectangles, and BUG)?

I must confess that I do not like these strategies, and in some ways they feel "wrong".

When one is using "standard" strategies, including the various "wings", "chains" and "fishes", then really you are just applying the basic Sudoku rule in more-or-less sophisticated ways. You are presented simply with a grid, and you analyse it until you find the solution array that fits it. If it turns out that there is no solution, or multiple solutions, then you curse the compiler (or perhaps feel superior), but you accept that there are such things as human error and typos.

With uniqueness strategies, though, there is another element. You are assuming that the puzzle is correct, in the sense that there is a unique solution, and then using this assumption to eliminate possibilities and so find this solution. You are relying on the infallibility of the puzzle compiler. This is a different kind of logic from the standard strategies - a different level of meta-logic really. For one thing, if the puzzle actually was wrong, then the technique would be invalid and might lead to errors - you might think you had found a solution when you hadn't.

I cannot decide whether I dislike these strategies more or less than using trial-and-error (which is, of course, yet a different form of logic - though perhaps more closely related to the "standard" strategies than the other).
User avatar
yellowpig
 
Posts: 3
Joined: 30 June 2017

Re: Uniqueness Strategies

Postby Leren » Sat Jul 08, 2017 12:58 am

You are right. This as been done to death for many years. You can read about the Uniqueness controversy here.

Leren
Leren
 
Posts: 2898
Joined: 03 June 2012

Re: Uniqueness Strategies

Postby champagne » Sat Jul 08, 2017 5:44 am

yellowpig wrote:With uniqueness strategies, though, there is another element. You are assuming that the puzzle is correct, in the sense that there is a unique solution, and then using this assumption to eliminate possibilities and so find this solution. You are relying on the infallibility of the puzzle compiler. This is a different kind of logic from the standard strategies - a different level of meta-logic really. For one thing, if the puzzle actually was wrong, then the technique would be invalid and might lead to errors - you might think you had found a solution when you hadn't.


As pointed leren , this is a endless discussion.

My own answer never changed

a) I don't recognize puzzles with more than one solution as sudokus.
b) any puzzle solved in my solver is first checked for a unique solution using brute force.

Then

c) uniqueness logic is one easy way to shorten the solution path
d) most of uniqueness rules are easy to apply without any help of a solver

so in my solver, uniqueness rules are used
and I use them as well when I don't use the computer

The population of guys having the same view seems to be a wide majority in that forum.
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Re: Uniqueness Strategies

Postby Serg » Sun Jul 09, 2017 5:30 pm

Hi, all!
I decided to post this message just to show - there are persons at this Forum who don't like uniqness strategies.

When I post a solution of puzzle (not only sudoku), I usually post

1. The confirmation that the puzzle is correct (i.e. it has unique solution).
2. The solution itself.

If your solution path includes uniqness strategies, you cannot be sure that the puzzle is correct, i.e. in this case solution is partial only.

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Uniqueness Strategies

Postby champagne » Sun Jul 09, 2017 7:33 pm

Serg wrote:Hi, all!
I decided to post this message just to show - there are persons at this Forum who don't like uniqness strategies.

When I post a solution of puzzle (not only sudoku), I usually post

1. The confirmation that the puzzle is correct (i.e. it has unique solution).
2. The solution itself.

If your solution path includes uniqness strategies, you cannot be sure that the puzzle is correct, i.e. in this case solution is partial only.

Serg


Hi Serg,

Nothing to object to your post but

using the brute force, you get the answer to both points
and brute force is clearly the shortest way to do it.

so I have difficulties to see clearly what you want to prove.

If the puzzle has more than one solution, no logical rule will bring you to the solution,
if it is a valid sudoku, you'll get the answer using an appropriate set of rules, but the path can be much longer than using the uniqueness properties.

what do you have in mind,,
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Re: Uniqueness Strategies

Postby Serg » Sun Jul 09, 2017 10:56 pm

Hi, champagne!

I treat uniqness strategies usage equivalent to hint usage. Each time you use uniqness strategy you use the hint "the puzzle has unique solution". Even when you check a puzzle by computer brute force solver, you get a hint from computer. Do you like to solve a puzzle with hints? I don't like.

This is my subjective point of view. I don't want to prove anything.

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: Uniqueness Strategies

Postby yellowpig » Mon Jul 10, 2017 8:16 am

Thanks, Leren, for the link.

That link includes:
the claim has been made that all logical deductions made by the Uniqueness family of solving techniques that assume a puzzle has a unique solution can be found by other means that do not require the Uniqueness assumption.

But again contrariwise, no rigorous mathematical proof of this assertion has been put forward.


Can I respectfully suggest that this is something that never could be proved mathematically. This is because the trial-and-error / brute force technique always will work in the end. It is profoundly unsatisfying for the player, but from the point of view of mathematical logic it is quite acceptable. (It is really a form of the "proof by contradiction" (sometimes called reductio ad absurdam) technique often used in mathematical proofs.) So a solution without using Uniqueness always is possible.

Whether a solution is always possible using other known strategies is a harder question - you would have to make a comprehensive list of what strategies you were going to allow, because you could never rule out somebody discovering another one that is not yet know.
User avatar
yellowpig
 
Posts: 3
Joined: 30 June 2017

Re: Uniqueness Strategies

Postby champagne » Mon Jul 10, 2017 8:55 am

yellowpig wrote:Whether a solution is always possible using other known strategies is a harder question - you would have to make a comprehensive list of what strategies you were going to allow, because you could never rule out somebody discovering another one that is not yet know.


As far as I know, all the called "logic techniques" not relying on the uniqueness property come to a contradiction clearing possible candidate (s) to the solution.
If you have several solutions, you will not find a contradiction in the corresponding field, so none of these techniques can solve a puzzle with more than one solution.

I am waiting for the counter example.
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Re: Uniqueness Strategies

Postby David P Bird » Mon Jul 10, 2017 10:36 am

yellow pig, on your uniqueness point Champagne is right. Non-unique puzzles contain a subset of cells that can be filled in more than one way. When the digits known to be true in the rest of the puzzle have been eliminated, they become completely isolated and there is no logical way of solving them.

On your other points, you will find that there is a range of opinions about what methods are acceptable in this forum. In my opinion the issue is how simply the route to to solution can be explained. The more complicated the logic of a method is, the less it should be favoured.

We then have puzzles that can be solved with a large number of simple deductions that may be solved far more quickly using more complex methods that need a trained eye to recognise. To guage which of the solutions is better, difficulty scores can be allocated to each of the steps and totals compared. However how different players rank the different methods varies considerably.

Many eliminations produced by simple steps prove to be insignificant in reaching a solution. Once a solution path has been found it is possible to shorten it by pruning these steps out, paticularly if the more advanced steps needed are promoted to be as early in the path as possible. To my knowledge no-one has yet coded a computer solver along these lines, however it more or less amounts to ranking a puzzle's difficulty according to the most complex step it needs.

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

Re: Uniqueness Strategies

Postby SteveG48 » Mon Jul 10, 2017 12:44 pm

yellowpig wrote:For one thing, if the puzzle actually was wrong, then the technique would be invalid and might lead to errors - you might think you had found a solution when you hadn't.


Hello, Yellowpig. I'll just add one thing to what has already been discussed. The concern that you express above is a non-starter. Sudoku solutions speak for themselves. You're not going to think that you've found a solution when you haven't. If you've filled the grid following the rules then you have a solution.

The problem with uniqueness techniques with puzzles that have multiple solutions is that having applied them you may find yourself facing a contradiction. The puzzle may appear to have no solution when it actually has more than one. You can also find a solution and believe that it's the only one when, in fact, there are others.
Steve
User avatar
SteveG48
2017 Supporter
 
Posts: 1991
Joined: 08 November 2013
Location: Orlando, Florida

Re: Uniqueness Strategies

Postby Kristoforus » Mon Jul 31, 2017 11:10 am

Hi
Champagne is wrong when seing that is no logical way to solve puzle with more than one solution. Sudoku with 2 solutions is solved when you khnow 2 possible solutions of that puzzle, sudoku with 3 solutions if you khnow all 3 possible solutions and etc. If champagne using uniquenes stratiegies in this diagrams he cant be able solving them, he meet contradiction and he will only khnow that these sudokus must heve some misteake or more than one solution but even that he cant be sure that his opinion is corect beacouse is always possible that he made somewhere misteake during solving. Using correctly logiical strategies always must leeds to true and using tricks not necesery and not only in sudoku:) Enjoyed
Kristoforus
 
Posts: 5
Joined: 13 July 2017

Re: Uniqueness Strategies

Postby m_b_metcalf » Mon Jul 31, 2017 3:46 pm

Kristoforus wrote:Hi
Champagne is wrong when seing that is no logical way to solve puzle with more than one solution. Sudoku with 2 solutions is solved when you khnow 2 possible solutions of that puzzle, sudoku with 3 solutions if you khnow all 3 possible solutions and etc. If champagne using uniquenes stratiegies in this diagrams he cant be able solving them, he meet contradiction and he will only khnow that these sudokus must heve some misteake or more than one solution but even that he cant be sure that his opinion is corect beacouse is always possible that he made somewhere misteake during solving. Using correctly logiical strategies always must leeds to true and using tricks not necesery and not only in sudoku:) Enjoyed


Please, how do I solve this puzzle:
Code: Select all
+---+---+---+
|...|...|.38|
|2..|..5|...|
|...|...|...|
+---+---+---+
|.5.|...|4..|
|4..|.3.|...|
|...|7..|..6|
+---+---+---+
|..1|...|.5.|
|...|.6.|2..|
|.6.|..4|...|
+---+---+---+
?

Regards,

Mike Metcalf

P.S. Or, to make it easier, this:
Code: Select all
 . . . . . . . 3 8
 2 . . . . 5 . 6 4
 . . . . . . . 2 5
 . 5 . . . . 4 . 3
 4 . . 5 3 . 8 . 2
 . 2 . 7 4 . 5 . 6
 . 4 1 . . . 6 5 .
 . . . . 6 . 2 4 .
 . 6 2 . 5 4 3 8 .
Last edited by m_b_metcalf on Tue Aug 01, 2017 8:21 am, edited 1 time in total.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8355
Joined: 15 May 2006
Location: Berlin

Re: Uniqueness Strategies

Postby eleven » Mon Jul 31, 2017 7:00 pm

Kristoforus,

you are right, that using uniqueness techniques in multi solution puzzles can lead to contradictions (or one of the solutions). That's why you must not use them, if the puzzle is not unique (as the name says).
But as Mike's sample might show you, you cannot solve them with classical (non uniqueness) techniques either. All classical techniques i am aware of, finally depend on the assumption, that exactly one of the candidates in each cell/unit must be true (singles). In other words, that the puzzle is unique. If it is not, they are stuck earlier or later (e.g. they never can resolve a unique rectangle with 2 solutions).
However in multi solution puzzles one candidate can be true in one solution and the other in another solution.

btw uniqueness techniques are not a trick, but a lovely feature.
eleven
 
Posts: 1563
Joined: 10 February 2008

Re: Uniqueness Strategies

Postby champagne » Tue Aug 01, 2017 1:37 am

Kristoforus wrote:Hi
Champagne is wrong when seing that is no logical way to solve puzle with more than one solution. Sudoku with 2 solutions is solved when you khnow 2 possible solutions of that puzzle, sudoku with 3 solutions if you khnow all 3 possible solutions and etc. If champagne using uniquenes stratiegies in this diagrams he cant be able solving them, he meet contradiction and he will only khnow that these sudokus must heve some misteake or more than one solution but even that he cant be sure that his opinion is corect beacouse is always possible that he made somewhere misteake during solving. Using correctly logiical strategies always must leeds to true and using tricks not necesery and not only in sudoku:) Enjoyed



but as wrote champagne earlier he does not recognize Sudoku with 2 solutions as a valid sentence.

As all other wrote, the only way that I know to check that we have a sudoku (unique solution) is to apply to the puzzle a brute force (trial and error) and to count the valid solutions (in fact, the process is halted when the second solution is seen).
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany


Return to Help with puzzles and solving techniques