Forcing chain and a few questions about Sudoku matrix

Advanced methods and approaches for solving Sudoku puzzles

Forcing chain and a few questions about Sudoku matrix

Postby Addlan » Wed Jul 20, 2005 1:07 pm

The more I study Sudoku, the more I realize I don't know about it. I am impressed by its strikingly beauty. Every Sudoku looks the same yet very different (very hard to be tranformed from one to another), every digit is perfectly located yet has so much freedom to swap with others (local swaps and global swaps). The structure is so simple yet the inner relation is so complicated. I admit that I don't know Sudoku, but I love it.

Regarding the forcing chain technique, I feel personally it will play an important role in solving hard Sudoku (surely it should be encouraged to use hand solving without computers by focusing on sensitive numbers). I presume that people have known about double forcing chain, yet I don't know if the following double forcing chain is already known or not or if it has already been used. I will only describe it using an example.

.3.|12.|.8.
1.9|..5|3.2
72.|..4|1.5
-----------
21.|64.|539
9..|.1.|.28
..3|.92|.1.
-----------
..2|...|..1
..1|4..|2.3
36.|251|...


[456] [3] [45] [1] [2] [79] [479] [8] [467]
[1] [48] [9] [78] [678] [5] [3] [467] [2]
[7] [2] [68] [389] [368] [4] [1] [69] [5]
[2] [1] [78] [6] [4] [78] [5] [3] [9]
[9] [457] [4567] [357] [1] [37] [467] [2] [8]
[4568] [4578] [3] [578] [9] [2] [47] [1] [467]
[458] [45789] [2] [3789] [378] [36789] [4678] [4567] [1]
[58] [5789] [1] [4] [78] [6789] [2] [567] [3]
[3] [6] [478] [2] [5] [1] [4789] [479] [47]

Look at the Sudoku matrix above and the possible numbers matrix. You will find that only two '8's and two '9' in the 9th row in the possible numbers matrix. 9th row is a sensitive row and it is very sensible to choose '8' or '9' to form a forcing chain. There are lots of '8', we may find something there either to eliminate the possibility of '8' or to confirm a digit '8' (make it more objective). We can either put an '8' in r9c3 or in r9c7, and they produce something as following.

Put an '8' in r9c3, we have r9c3 = 8 -> r4c3 = 7 -> r4c6 = 8 and their matrixes are as below:
.3.|12.|.8.
1.9|..5|3.2
72.|..4|1.5
-----------
217|648|539
9..|.1.|.28
..3|.92|.1.
-----------
..2|...|..1
..1|4..|2.3
368|251|...


[456] [3] [45] [1] [2] [79] [479] [8] [467]
[1] [48] [9] [78] [678] [5] [3] [467] [2]
[7] [2] [6] [389] [368] [4] [1] [69] [5]
[2] [1] [7] [6] [4] [8] [5] [3] [9]
[9] [45] [456] [357] [1] [37] [467] [2] [8]
[4568] [458] [3] [57] [9] [2] [47] [1] [467]
[45] [4579] [2] [3789] [378] [3679] [4678] [4567] [1]
[5] [579] [1] [4] [78] [679] [2] [567] [3]
[3] [6] [8] [2] [5] [1] [479] [479] [47]


If we put an '8' in r9c7, we have r9c7 = 8 -> r1c7 = 9 -> r1c6 = 7 -> r4c6 = 8 and their matrixes are as below:

.3.|127|98.
1.9|..5|3.2
72.|..4|1.5
-----------
21.|648|539
9..|.1.|.28
..3|.92|.1.
-----------
..2|...|..1
..1|4..|2.3
36.|251|8..


[456] [3] [45] [1] [2] [7] [9] [8] [46]
[1] [48] [9] [8] [68] [5] [3] [467] [2]
[7] [2] [68] [389] [368] [4] [1] [6] [5]
[2] [1] [7] [6] [4] [8] [5] [3] [9]
[9] [457] [4567] [357] [1] [3] [467] [2] [8]
[4568] [4578] [3] [57] [9] [2] [47] [1] [467]
[458] [45789] [2] [3789] [378] [369] [467] [4567] [1]
[58] [5789] [1] [4] [78] [69] [2] [567] [3]
[3] [6] [47] [2] [5] [1] [8] [479] [47]

We can confirm that r4c6 = 8. Sometimes we can only eliminate the possibility of some digits, but can't confirm one. I find that this forcing chain is quite common to eliminate some probability of a digit. Actually X wing can be considered as a special case of this forcing chain.

I have a few questions that I am very interested to know about. What is the minimum number of digits required in the initial Sudoku matrix leading to a unique solution? Give the reasons and an example if it is known. And what is the total numbers of Sudoku matrixes with or without renumbering, rotating and transfoming (local number swaps count as different Sudoku matrixes)? Does local number swaps have to appear in a Sudoku matrix? If not, give an example. And what is the maximum number of local swaps in a Sudoku matrix?

Thanks.

Note: local number swaps (don't konw if it is the right term). You can swap '3' and '5' in the first two rows and swap '8' and '9' in the first two columns in the following examples (generated using software Simple Sudoku). Some other swaps: if you swap a couple of them, you will have to swap all digits of them.

169|72.|.48
728|64.|.91
543|918|672
-----------
351|487|926
..6|251|437
472|396|815
-----------
..4|162|753
617|539|284
235|874|169
Addlan
 
Posts: 62
Joined: 15 July 2005

Postby Nick70 » Wed Jul 20, 2005 3:17 pm

You double forcing chain would be represented in my notation this way:

Code: Select all
(9,3)=8 => (9,3)<>7 => (4,3)=7 => (4,6)<>7 => (4,6)=8
(9,7)=8 => (9,7)<>9 => (1,7)=9 => (1,6)<>9 => (1,6)=7 => (4,6)<>7 => (4,6)=8


with two branches of different length. They can be made of the same length this way:

Code: Select all
(9,7)<>8 => (9,3)=8 => (9,3)<>7 => (4,3)=7 => (4,6)<>7 => (4,6)=8
(9,7)<>9 => (1,7)=9 => (1,6)<>9 => (1,6)=7 => (4,6)<>7 => (4,6)=8


But there is a shorter chain to move forward from the position:

Code: Select all
(3,8)=6 => (8,8)<>6 => (8,6)=6 => (8,6)<>9 => (8,2)=9
(3,8)=9 => (1,7)<>9 => (1,6)=9 => (8,6)<>9 => (8,2)=9
Nick70
 
Posts: 156
Joined: 16 June 2005

Postby Addlan » Wed Jul 20, 2005 3:43 pm

Thanks, Nick. They are the same indeed. But in term of hand solving, what is the objective of the double forcing chain? or one has to try many chains?

I just read something about the total number of Sudoku matrix, so people don't need to reply this question any more. However, I am still interested in other questions. If you can provide the threads, that will be very helpful.
Addlan
 
Posts: 62
Joined: 15 July 2005


Return to Advanced solving techniques