Locked Candidates

With all of the value-setting strategies covered, it is now time to delve into the candidate exclusion strategies. The most basic candidate exclusion strategy that the program will utilize is Locked Candidates, which has two flavors. Rather than simply call the strategy Locked Candidates, sometimes the individual cases, Block-Row/Column interactions and Block-Block interactions, are named.

fig5The Block-Row/Column Interactions strategy concerns itself with pinpointing a certain candidate to a single row or column of a block. If this candidate can only appear in this row or column, then outside of the block in that row or column one can eliminate that candidate. Figure 5 depicts a Block-Column/Row interaction. Because in the middle block, 5 may only occur in the blue spots, and these spots are in the same column, it follows that 5 cannot be a candidate for any of the highlighted squares.

To program this strategy, a slightly different approach can be taken. For each number 1-9, one can look at each block. By finding all cells that contain the number in that block, and determining if all of these cells share a row or column by comparing the cells’ positions, the strategy can be applied. If a Block-Row/Column interaction is found, then the program searches through all of the cells in the row or column the rule is being applied to, and if the cell is not in the block and contains the candidate, the candidate is removed. If no candidates are removed, despite having found a Block-Column/Row interaction, it will not count as an application of the strategy because no headway has been made, and solving will continue.

The next form of Locked Candidates, Block-Block interactions will then be used. This is a very similar strategy,fig6 except that it deals with two blocks. The idea behind the strategy is that if between two of three blocks in the same row or column, a certain candidate only occurs in two rows or columns, it can be eliminated from those rows or columns in the third block. Figure 6 demonstrates this for the candidate 5. In the first two blocks, 5 can only be a candidate in the cells with blue circles, which are limited to two rows, so this means 5 cannot be a candidate in these yellow columns in the third block. One can describe the strategy using an alternate method as well. If in any row or column, a certain candidate may only appear in one block, then in that block the candidate cannot occur anywhere but in that row or column (Armstrong). Looking at figure five again, one can see that in the third row, the only cells where 5 may occur are the red cells, which all share the same block. This means that being in the same block, the yellow cells cannot have 5 as a candidate.

With this new description of Block-Block Interactions, it becomes somewhat easier to program. The program need only look through every number x 1-9 and in every row and column, check to see if x occurs as a candidate only in a single block. This is accomplished by comparing the position of all cells in a given row or column able to contain x and verifying that they are in the same block. If no removals are able to be made from that block, then the strategy continues until it can remove a candidate or has exhausted all possible row/column, and candidate combinations. If it exhausts all possibilities, then it is time to move on to a more difficult strategy.

Posted in Sudoku Solving Strategies and Techniques at April 26th, 2009. Trackback URI: trackback

No Responses to “Locked Candidates”

Comments are closed.