The New Sudoku Players' Forum

[flagitious]

This method is a logic step that can reduce canidates of unknown squares. It works by making the assumption that the puzzle only has 1 solution, which should be true for any published puzzle.

The basic idea is if you have something looks this:

Code: Select all

+---+---
|437|596
|852|317 ...
|961|824
+---+---


The 2's and 1's can be switched and the result is still a valid sudoku solution regardless of the rest of the puzzle. Therefore at least one of those four spots must be a given or there would be more than 1 solution.

You can take advantage of this when solving a puzzle. Take this example:

Code: Select all

+---+---
|...|...
|..a|.b. ...
|..c|.d.
+---+--


In this example lets assume you deduced:
a is either 1,2, or 5
b is either 1 or 2
c is either 1 or 2
d is either 1 or 2

Then a has to be 5 because if it weren't then the result imply that the puzzle has multiple solutions.

I am sure that there are plenty of different circumstances besides this where you can take advantage of the knowledge that the puzzle is valid. Not sure how often they occur in real puzzles, but I thought I would throw this out there and see if anyone knew of it already or finds it useful.

[tso]

There was a debate about this technique in solving Battleship puzzles sometime ago. Some of the arguments were somewhat similar to those in this forum recently regarding "T&E", "Proof by Contradiction", "look ahead".

I've used the tactic in dozens of different types of logic puzzles, though I can't recall coming across it in a Sudoku.

[PaulIQ164]

Yes, I've used this technique before too, in the Times 'super-fiendish' a week last Tuesday, I think. It can be highly useful.

[sudokubill]

i combine this w/ marking up and sometimes guess and check and have been able to solve all ive tried ;) (gentle to diabolical)

Although i didnt think about the possibility of the puzzle having more than one solution.

Would the possibility of more than one solution be an issue for all solving techniques?

[Hans]

I have also discoved this before reading the post and used it a few timess (and even tried to post yesterday but it got lost).

However, I would like to point out that there are two variations of it starting from the same setup:

Code: Select all

+---+---
|...|...
|..a|.b. ...
|..c|.d.
+---+--


1.
Assume you deduce that a is {1,2,5,6}, whereas b,c,d are {1,2}. You can then cross out {1,2} from a leaving you with {5,6}. I had this situation yesterday (but it didn't solve anything - but then I found I found a simpler uniqueness-pattern and could go from that).

2. Assume you deduce that is a and c are both {1,2,5}, and whereas b, and d are {1,2}.

Since 5 must be placed either in a or c you can remove 5 as candidate from other squares in the same box and column.
(I used this last week).

[Lummox JR]

I believe I've stumbled onto a new variant of this test. I found a case similar to Hans's 2nd variation, but with 4 candidates instead of 3.

Code: Select all

---+---
.e.|...
..a|.b.
..c|.d.
---+---

If a and c are both {1,2,5,6}, and b and d are both {1,2}, then either 5 or 6 (or both) must appear in either a or c. If e is {5,6}, then whichever value does not appear in e must appear in either a or c. Thus, {5,6} can be constrained to cells a, c, and e within that box. (If e is aligned with ac, you can also eliminate {5,6} in the common column or row they share.)

The same logic can be extended to even more extra candidates using more cells, just like a weird form naked subset. It is required that a and c have the exact same list of candidates. Where N is the number of "extras" (e.g., {5,6} means N=2), you only need those extra candidates to appear in N-1 other cells. Thus to use a more complicated example, consider ac={1,2,5,6,9}, bd={1,2}, e={5,6}, f={5,9}:

Code: Select all

---+---
.e.|...
f.a|.b.
..c|.d.
---+---

If e is 5, f must be 9 and the 6 must appear in a or c. If e is 6, this degenerates into the case above where whichever digit is not in f must be in a or c. This acts very much like a standard subset because the cells a and c function as a single cell in which {5,6,9} must appear.

I've posted more on this here, with an example partial board.

[ab]

This method is a logic step that can reduce canidates of unknown squares. It works by making the assumption that the puzzle only has 1 solution, which should be true for any published puzzle.

I'm not happy about using that technique! Suppose the puzzle composer was careless and posted a puzzle that doesn't have a unique solution.

You're supposed to be able to solve sudoku using logic, but this technique makes an extra assumption, that there is a unique solution. Logic alone does not lead to that conclusion.

[Lummox JR]

I'm not happy about using that technique! Suppose the puzzle composer was careless and posted a puzzle that doesn't have a unique solution.

Corollary: Suppose a composer was careless and posted a puzzle whose solution puts a digit twice in a box/column/row. This may not be clear from the outset either.

You're supposed to be able to solve sudoku using logic, but this technique makes an extra assumption, that there is a unique solution. Logic alone does not lead to that conclusion.

The fact that you're supposed to be able to solve sudoku using logic alone also requires it to have one solution. For it to have multiple solutions, logic alone would not be able to fill in all the cells; it would be necessary at some point to abandon logic and make a guess. Moreover, if your guess turned out right, you'd still have to go back and make other guesses just to verify that there weren't other correct guesses--not just for that cell but for all others that were not previously filled in. You could only trust the guesses that turned out wrong, since they'd be wrong for all solutions, so eventually you'd be left with a set of cells that could not be conclusively filled. Therefore there's nothing "extra" to the assumption of a unique solution; it's as valid as assuming the puzzle maker didn't misplace one of the clues causing a completely insoluble board.

This technique will not, as tso correctly pointed out elsewhere, verify the solution is unique. In a multi-solution grid it will either reduce the number of possible solutions or render the result insoluble, either of which is equivalent because at the end of the day you're still working on a broken puzzle. And this is where the philosophical "Well, you just can't trust that it's unique" argument derails: A puzzle that does not have a unique solution is broken. It's just as broken as one that doesn't fit the placement constraints. Finding a solution is useless, because the goal is to find the solution; if you've found one possible solution out of two, you've merely completed a broken puzzle by guessing.

There's literally no logic in distrusting the uniqueness of the solution. You can trust it every bit as well as you can trust anything else about the initial board. Either it's a valid puzzle or it's not. If the initial conditions are wrong, the result will be wrong. If multiple solutions exist, even brute force will at some point fail to eliminate more candidates.

[Moschopulus]

I go along with Huang's thoughts on the battleship link given above.
It's a matter of personal taste whether one uses the uniqueness assumption while solving. There's no logic to that, just a matter of taste.
Similarly, some people use forcing chains (or whatever) while solving, and some don't. That is also a matter of personal taste.

[ChrisT]

I would have thought that, although this technique might prove useful, it could never be REQUIRED in order to solve a puzzle. That is, in itself, putting in a "non-unique" combination such as the 1,2 2,1 combinations discussed above does not break the "one rule" of sudoku. However in a unique puzzle it must, presumably, lead to a contradiction elsewhere in the puzzle. It should therefore, at least in theory, be possible to arrive at the same conclusion about the squares under scrutiny WITHOUT using the assumption that the puzzle is unique, but through logical progress in other areas of the puzzle.

Chris

[Brendan]

I think that unique solutions are more elegant, and gives you that satisfying "I've done it" feel at the end, but it is not illogical to have more than one solution. Anyone that has studied quadratic equations, quantum mechanics or fuzzy logic would be quite ok with non-unique logical solutions. Also, you don't have to guess to find the answer to multiple solution puzzles.

Brendan

[stuartn]

Anyone that has studied quadratic equations, quantum mechanics or fuzzy logic would be quite ok with non-unique logical solutions.

In those contexts - yes. In the context of a legitimate Sudoku - absolutely not. The topics you mention are KNOWN to have multiple solutions. A legitimate Sudoku is KNOWN to have a single solution.

If a quadratic had a single solution it wouldn't be a quadratic would it?

stuartn

[DanO]

Here are 2 examples where simple rules plus the uniqueness rule can solve an otherwise "super hard" problem requireing tableing or other advanced techniques.
Menneske no. 5460770

Code: Select all

+-------+-------+-------+
| . . 2 | . 8 . | . . . |
| 4 . . | 2 . . | . . . |
| 7 . 5 | . . 6 | . 4 . |
+-------+-------+-------+
| 1 . . | 8 . . | 6 9 . |
| 8 . . | . . . | . . 5 |
| . 7 6 | . . 9 | . . 8 |
+-------+-------+-------+
| . 2 . | . . 4 | 8 . 7 |
| . . . | 3 . . | . . 6 |
| . . . | . 2 . | 3 . . |
+-------+-------+-------+

Menneske no. 1411849

Code: Select all

+-------+-------+-------+
| . . . | 4 3 . | . . . |
| 3 . . | . . . | 7 . . |
| . 7 . | . . 2 | . . 8 |
+-------+-------+-------+
| . 8 7 | . . . | . . 4 |
| . . 5 | 3 4 . | . . . |
| . . 9 | 8 . 6 | . 2 . |
+-------+-------+-------+
| 8 5 . | . . 9 | . . . |
| . . . | . . . | 1 9 . |
| . . 1 | 6 . . | . . 5 |
+-------+-------+-------+


[Lummox JR]

I think that unique solutions are more elegant, and gives you that satisfying "I've done it" feel at the end, but it is not illogical to have more than one solution. Anyone that has studied quadratic equations, quantum mechanics or fuzzy logic would be quite ok with non-unique logical solutions. Also, you don't have to guess to find the answer to multiple solution puzzles.

What you're saying is only logical in the sense that if you wanted to find all solutions and had some mathematical means for doing so, you could. However, sudoku isn't about finding all solutions; it's about finding the solution. A grid with more than one solution is invalid. It is not illogical, but neither is it sudoku. A sudoku with multiple solutions does not have enough givens, just like a word problem that expects one answer but several will fit.

In sudoku, two players should both be able to arrive at the exact same conclusion independently, whether they guessed or not. It should also be possible to arrive at a solution using strictly logical methods, which is not possible with multiple solutions. Guesing is required, or else you must know the solution set and arbitrarily choose which one to pursue. An arbitrary choice between solutions is just the same as a guess, though, except it's not blind. In quadratic problems you usually either need both solutions for whatever reason, or can eliminate one of them because it does not agree with a constraint of the original problem.

Oh, and stuartn, it is possible for a quadratic to have a single solution; it's just repeated. This is quite common.

[stuartn]

Oh, and stuartn, it is possible for a quadratic to have a single solution; it's just repeated.

and that's single is it?