<< sudoku_findtwocolors Algorithms sudoku_findxwing >>

Sudoku Toolbox >> Algorithms > sudoku_findxcycle

sudoku_findxcycle

Search for pairs.

Calling Sequence

[ X , C , L ] = sudoku_findxcycle ( X , C , L )
[ X , C , L ] = sudoku_findxcycle ( X , C , L , stopatfirst )
[ X , C , L ] = sudoku_findxcycle ( X , C , L , stopatfirst , verbose )

Parameters

X:

a 9-by-9 matrix, with 0 for unknown entries

C:

a 9 x 9 cell of candidates

L:

the 9 x 9 matrix of number candidates

stopatfirst:

if %t, then stop when one or more candidates have been removed. (default = %t)

verbose:

a boolean. Set to %t to display the state of the matrix. (default = %f)

Description

Find Alternating Inference Chains.

The algorithm searches for chains of cells with the same candidate d. The link between cells are either strong or weak, depending on the number of cells having candidate d in the same row, column or block. If there are only 2 cells having candidate d, the link is strong (symbol "="). If there are more than two cells, the link is weak (symbol "-"). A chain is represented by a list of cells, separated with the type of link, e.g. the link associated with candidate 8 : 8(3,1)=8(2,2)-8(2,8)=8(6,8)-8(6,1)=8(3,1) This is indeed a chain, since the last element is the same as the first. (In many texts, it is implicitely written). Once the chain is computed, we can make deductions. * Rule #1 : if the chain is made of strictly alternating links i.e. weak, strong, weak, strong, etc..., then the candidate d in the same row, column or block as a weak link can be removed. This is a continuous X-Cycle. * Rule #2: if candidate d in cell (i,j) in the chain follows and is followed by a strong link, it can be confirmed. This is a discontinuous X-Cycle. The length of the chain must be odd. The chain must alternate weak and strong links, except at the discontinuity. * Rule #3 : if candidate d in cell (i,j) in the chain follows and is followed by a weak link, it can be removed. This is a discontinuous X-Cycle. The length of the chain must be odd. The chain must alternate weak and strong links, except at the discontinuity.

The X-Wing, Swordfish and 2-colors strategies are superseded by the X-Cycle strategy.

The first algorithm searches for all the locations of the candidate d in the sudoku. The result is stored in the arrays rows and cols with length len: (rows(i),cols(i)) are row and column indices of the i-th cell which contains d as candidate. This gives an ordered list of cells containing d, numbered from 1 to len. This list of cells can be displayed with printlocations.

Then we compute the list of all conjugate pairs of the candidate d. This list is computed as a sub-list of the previous list, that is, it is made of integers in the [1,len] interval. The result of the algorithm is an array conjugate where the number of rows nconj is the number of conjugate pairs and conjugate(i,1) and conjugate(i,2) are the i-th conjugate pairs where 1 <= conjugate(i,1) <= len and 1 <= conjugate(i,2) <= len.

Then the list of all chains is searched. A chain is represented by a matrix chain where the number of rows is the length of the chain: chain(i,1): the first element of the link #i chain(i,2): the type of the link #i, equals 0 for a strong link, equal 1 for a weak link. The element chain(i,1) is linked to chain(i+1,1) by the link of type chain(i,2). The link type chain($,2) is -1, which stands for undefined. The chain2str function allows to convert a chain into a string.

Examples

X = [
0 2 4   1 0 0   6 7 0
0 6 0   0 7 0   4 1 0
7 0 0   9 6 4   0 2 0
..
2 4 6   5 9 1   3 8 7
1 3 5   4 8 7   2 9 6
8 7 9   6 2 3   1 5 4
..
4 0 0   0 0 9   7 6 0
3 5 0   7 1 6   9 4 0
6 9 7   0 4 0   0 3 1
];
[C,L] = sudoku_candidates(X);
X = sudoku_findxcycle ( X , C , L , %f , %t );

Authors

Bibliography

Angus Johnson, http://www.angusj.com/sudoku/hints.php


<< sudoku_findtwocolors Algorithms sudoku_findxwing >>