The New Sudoku Players' Forum

[DanO]

In my opinion, this technique should at least be defined and given a name. It took me less time to discover it from the uniqueness principle than it did to locate somewhere it was being discussed. Wether or not you use it is a personal decision.

If you are on the side that believes that uniqueness isn't a given then a modification of this technique should be able to show when the solution is not unique and will provide required information for logically finding the sets of solutions.

For a better view of the basic patterns involved, it is easier to start from a solved board and work backwards. Take any solved board and highlight all the 1's and 2's. Now look at the patterns of the buddy chains between the 1's and 2's. Most often these will form a single chain. Occasionally there will be 2 or more separate chains. Every chain must have at least one exposed number to prevent the chain from flipping into an alternate solution.

[Lummox JR]

In my opinion, this technique should at least be defined and given a name. It took me less time to discover it from the uniqueness principle than it did to locate somewhere it was being discussed. Wether or not you use it is a personal decision.

It does have a name: the uniqueness test. Or rather, tests. It's now a family of tests at this point, with variants 1-4 and 2b-4b. In theory the logic of these can also extend to higher-order forms 3x3, 4x4, and 6x6.

If you are on the side that believes that uniqueness isn't a given then a modification of this technique should be able to show when the solution is not unique and will provide required information for logically finding the sets of solutions.

That doesn't really make sense. This technique relies on uniqueness as one of its base premises; you can't simply modify it to prove the premise is wrong. And if it is wrong, what's the point in looking for all the solution sets anyway? A multi-solution grid is broken; it is not a valid sudoku. The only point in exploring multiple solutions is to count them or just confirm multiples exist.

For a better view of the basic patterns involved, it is easier to start from a solved board and work backwards. Take any solved board and highlight all the 1's and 2's. Now look at the patterns of the buddy chains between the 1's and 2's. Most often these will form a single chain. Occasionally there will be 2 or more separate chains. Every chain must have at least one exposed number to prevent the chain from flipping into an alternate solution.

There are some other constraints known for the givens as well:

1) At most only one digit can be missing from the givens.
2) At most only one column can be missing from the givens.
3) At most only one row can be missing from the givens.

Multiple boxes may be missing, which is clear if you take a solution grid and remove boxes 1, 5, and 9. You do however need at least 6 of the boxes to contain givens. This provides some support for the theory that no fewer than 17 givens are possible in a valid sudoku. If you arrange 8 givens diagonally you will satisfy the three constraints above, and if you add a few more you can be sure to have enough givens to fill in three missing boxes. I suspect that if 17 really is the minimum, it's to provide just enough more positional information for the 16 other givens to be of any use at all.

[Moschopulus]

For a better view of the basic patterns involved, it is easier to start from a solved board and work backwards. Take any solved board and highlight all the 1's and 2's. Now look at the patterns of the buddy chains between the 1's and 2's. Most often these will form a single chain. Occasionally there will be 2 or more separate chains. Every chain must have at least one exposed number to prevent the chain from flipping into an alternate solution.

Just to try and share terminology, since you've rediscovered something.

Over on the minimum clues thread we call things like this "unavoidable sets".
An unavoidable set in a completed grid is any set of cells such that some permutation of the digits in those cells results in another valid completed grid.
Any puzzle made from that grid must have at least one clue from every unavoidable set. (hence the name)

Example of an unavoidable set of size 4:
12.......
.........
.........
21.......
.........etc

Given any two digits, the set of 18 cells consisting of all the cells containing those two digits is an unavoidable set. The chains you are describing are subsets of this set that are unavoidable.

There are some other constraints known for the givens as well:

1) At most only one digit can be missing from the givens.
2) At most only one column can be missing from the givens.
3) At most only one row can be missing from the givens.

Yes, these are other unavoidable sets. They translate into:

1) as said above, the 18 cells for any two digits is unavoidable
2) Any two columns in a given stack form an unavoidable set. (not correct as stated)
3) Any two rows in a given band form an unavoidable set (again not correct as stated)

[Lummox JR]

Ah, I see the logic in that now. If the two columns missing are in different towers, you still have horizontal position information for each digit. That clarifies a lot for me. Also based on my observation that three boxes on a diagonal (or offset diagonal) could be missing, I suspect it's also true that two boxes in a tower or floor may not be missing. Very handy piece of information, that.

[Moschopulus]

Is this what you meant?

Code: Select all

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


[dhanunjaya]

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 are some other constraints known for the givens as well:

1) At most only one digit can be missing from the givens.
2) At most only one column can be missing from the givens.
3) At most only one row can be missing from the givens.

Multiple boxes may be missing, which is clear if you take a solution grid and remove boxes 1, 5, and 9. You do however need at least 6 of the boxes to contain givens.

Only 5 boxes need contain givens for a validity.

Up to 3 columns, 3 rows and 3 boxes can all be at once empty and still give a valid puzzle:

Easy:

Code: Select all

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

Hard:

Code: Select all

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

Harder:

Code: Select all

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

These three puzzles are from:
http://www.csse.uwa.edu.au/~gordon/sudokupat.php

... based on this thread:

http://forum.enjoysudoku.com//viewtopic.php?t=1180