A deduction from uniqueness

Advanced methods and approaches for solving Sudoku puzzles

Postby PaulIQ164 » Tue Sep 06, 2005 3:38 pm

So, are you saying that using this sort of tactic on a puzzle that has multiple solutions could lead you to more than one solution depending on what order you make these false eliminations in?
PaulIQ164
 
Posts: 533
Joined: 16 July 2005

Postby Big Blue » Tue Sep 06, 2005 3:38 pm

I think this is a perfectly valid deduction step if you really know it is a valid sudoku.

I recall that I used it once for the so-called "toughest puzzle" where I excluded a possibility by trial and error in this way: before encountering a contradiction I quickly found a pair appearing in an x-wing (like in your example the 48) - so by appealing to uniqueness I was able to throw away this possibility without having to establish a contradiction (which would have taken much longer).

BTW, if you do "trial and error" and you guess correctly then you are also appealing to uniqueness (unless you try also the other possibility to establish a contradiction - but honestly, who does that? normally you are HAPPY when you guess correctly), so I don't see why such a reasoning should not be allowed.

So in short, it may help for very difficult puzzles where you have to resort to trial and error. It is also a neat trick for simpler puzzles, just for extra style points:)
Big Blue
 
Posts: 28
Joined: 01 August 2005

Postby tso » Tue Sep 06, 2005 3:53 pm

Agreed. It's silly not to include all the rules of the game as part of the given information.

See:


http://www.mountainvistasoft.com/t-uniq.htm

and

http://forum.enjoysudoku.com/viewtopic.php?t=890
tso
 
Posts: 798
Joined: 22 June 2005

Postby RickM » Tue Sep 06, 2005 5:34 pm

I was under the impression that one of the basic requirements was a unique solution. There would seem to be some disagreement on this even among the most experienced players...:)

Does Hoyle publish an "Offical Rules of Sudoku?":)
RickM
 
Posts: 22
Joined: 18 August 2005

Postby PaulIQ164 » Tue Sep 06, 2005 5:45 pm

I don't think there's any question that a valid sudoku has to have a unique solution. The question is, what if a sudoku has multiple solutions, but if you assume it has a unique solution and using techniques based on that assumption you can arrive at a unique answer? Alright, it's not exactly a speific question, more just a thing to think about.
PaulIQ164
 
Posts: 533
Joined: 16 July 2005

Postby stuartn » Tue Sep 06, 2005 6:48 pm

Tso - as I roared back through Gatwick this evening I had exactly the same thought - this can't be valid as it's self contradictory.

If a grid is unique it must be unique throughout the solving process. If alternative end options arise during the process it clearly cannot be unique - even if a solution exists where all cells are filled correctly at the end. It'll help find a solution, but not necessarily the ONLY one.

A good thought exercise anyway.

stuartn
stuartn
 
Posts: 211
Joined: 18 June 2005

Postby RickM » Tue Sep 06, 2005 7:03 pm

Okay... this is getting a bit academic, I suppose, but....

There is a basic paradox in what you propose, Paul.

"if a sudoku has multiple solutions" and "you can arrive at a unique answer" are mutually exclusive. You can't have both.

If one says, "This puzzle has a unique solution only if RxCy = Z," then what that tells me is that there is one clue missing.

If it DOES have a unique answer and you use that knowlege in your logic, fine - valid technique in my book.

But if it DOES NOT have a unique answer, and you make an incorrect assumption that leads to a unique answer that only applies based on that incorrect assumption, then your logic is invalid.

This seems analagous to my geometry class back in high school. If it can be shown that an assumption is false, then any conclusion based on that false assumption is not valid. And in this case, a false assumption is a given, no?:)
RickM
 
Posts: 22
Joined: 18 August 2005

Postby PaulIQ164 » Tue Sep 06, 2005 7:36 pm

Yes, I suppose the second 'unique' could stand to be in inverted commas. But I mean, imagine if someone gave you some puzzle with multiple solutions, but they lied to you besause they were a sadistic liar, and told you it was a unique-solution puzzle. Then you might use this tactic (since in this case it's valid in your book) and arrive at (what you think is) the unique answer. I was simply wondering if there was a puzzle where this can happen. Someone claimed the puzzle under discussion a bit above had this property, but I couldn't see it.

PS: I agree, the whole discussion is largely academic. That's what makes it fun!
PaulIQ164
 
Posts: 533
Joined: 16 July 2005

Postby tso » Tue Sep 06, 2005 8:03 pm

The whole thing is a red herring. You are given a puzzle. It has multiple solutions. You assume it has a unique answer. You find one answer and assume it's the only one. I get the same information and arrive at a different solution. There's no "there" there.

Try this one instead:

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


There is a clue missing from this puzzle at r7c6. Put the wrong number there, the puzzle will either have NO solution or MULTIPLE solutions. Only one number will give a valid puzzle. Find that number then solve the puzzle.

http://forum.enjoysudoku.com/viewtopic.php?t=956
tso
 
Posts: 798
Joined: 22 June 2005

Postby PaulIQ164 » Tue Sep 06, 2005 8:08 pm

But I'm afraid I don't see how that answers my question. I realise you can't make a multiple-solution puzzle magically have a single answer, but all I'd like to know is, can you make a multiple-solution puzzle that arrives at a single solution puzzle if you treat it as a single-solution one ans use techniques dependent on that erroneous assumption. I know it would be the wrong thing to do, and I know it wouldn't stop the original puzzle being multiple-solutioned, but I just think it'd be an interesting puzzle to have.
PaulIQ164
 
Posts: 533
Joined: 16 July 2005

Postby tso » Tue Sep 06, 2005 8:49 pm

I understood you but I wasn't clear in my answer. I'm saying that it would be easy to construct such a puzzle. You could inforce all sorts of false assumptions in order to lead the solver where you want them. OR, instead of hoping they use a certain type of false assumption, you define them as additional stipulations to the puzzle.

For instance, consider Sudokus in which the two diagonals also contained the digits 1-9. You could also choose to describe them as Sudokus with multiple solutions -- but as long as we "lie" to the solver, tell them (truthfully) that the diagonals must be included, then they'll arrive at the same answer. The point is, if you add stipulations that insure the solver arrives at unique solution, then the puzzle no longer has multiple solutions.
tso
 
Posts: 798
Joined: 22 June 2005

Postby stuartn » Tue Sep 06, 2005 9:07 pm

My point. Succinctly put.

stuartn
stuartn
 
Posts: 211
Joined: 18 June 2005

Postby PaulIQ164 » Tue Sep 06, 2005 10:45 pm

Surely it's one thing though to add a constraint like the diagonals one to make a non-unique puzzle unique, but another thing when the constraint you're adding is to treat the puzzle as if it is unique? Well, whatever, I just think it'd be pretty neat to actually have one. Unfortunately, I have no idea how to even construct a regular sudoku, let alone a quasi-paradoxical non-unique-unique sudoku like that.
PaulIQ164
 
Posts: 533
Joined: 16 July 2005

Postby maria45 » Fri Jan 27, 2006 3:59 pm

I don't have proof for this assumption, but I think if a puzzle is unique, you can always solve it without the assumption of uniqueness, because there must be other logical steps to take.
The assumption is based on my experience with forcing chains, as I found until now no unique sudoku that I could not solve by forcing chains.

The logical point that follows if the above is correct, is: there can be no non-unique-puzzle which is made unique through assumption of uniqueness.
maria45
 
Posts: 54
Joined: 23 October 2005

Postby tso » Fri Jan 27, 2006 7:08 pm

maria45 wrote:I don't have proof for this assumption, but I think if a puzzle is unique, you can always solve it without the assumption of uniqueness, because there must be other logical steps to take.
The assumption is based on my experience with forcing chains, as I found until now no unique sudoku that I could not solve by forcing chains.

The logical point that follows if the above is correct, is: there can be no non-unique-puzzle which is made unique through assumption of uniqueness.


Yes, there will always be another way to find the solution -- I don't think this assumption requires a proof. Since brute force is logical and all puzzles can be solved this way, its just a matter of degree.

However, there are plenty of puzzles that you won't be able to solve by forcing chains. For example, the following puzzle is very nearly trivial to solve if one uses the unique rectangle tactic (nothing else but singles is needed), but very, very hard -- beyond what most would consider forcing chains and nishio -- without:

Code: Select all
8 . . | 2 . 5 | . . 1
. . . | 1 . 3 | . . .
. . 3 | . 7 . | 8 . .
------+-------+------
6 3 . | . . . | . 7 5
. . 8 | . . . | 2 . .
9 1 . | . . . | . 4 8
------+-------+------
. . 5 | . 9 . | 1 . .
. . . | 7 . 6 | . . .
3 . . | 5 . 2 | . . 9
tso
 
Posts: 798
Joined: 22 June 2005

PreviousNext

Return to Advanced solving techniques