fig3 The next easiest strategy is Singles. This relies on logic similar to Simple Singles, except that instead of looking at the row, column or block separately, it looks at all three together. A blank cell can be any integer from one to nine. If another cell in its row, column, or block contains a certain value, you can remove that value from the empty cell’s set of candidates. This technique can be called simple candidate exclusion. If after simple candidate exclusion or another, more advanced candidate exclusion method to be covered later, only a single value x remains as a possible candidate for the cell, one can set that cell’s value to x. Figure 3 illustrates this. The highlighted cell cannot be a 5, 4, or 6 because these values are all in the same block as that cell. Furthermore, the cell cannot be an 8 or a 9 because those values are already in the same row as that cell. Finally, the highlighted cell cannot be a 2, 1, or 3 because these values are used in the same column. This leaves the only possible value to be 7, so the highlighted cell’s value is 7. Note that Simple Singles is actually a special case of this strategy.

It is in programming this strategy that the logical structure for a Sudoku grid’s representation emerges. First of all, the grid itself must contain 81 cells. It must have 9 rows, columns, and blocks, each containing 9 cells. Lastly, and most importantly, each cell must have a set of possible candidates and a position. With this structure set, the strategy can begin to be implemented. Once, when the program is first run, simple candidate exclusion should be applied to all empty cells. To do this, the program finds the row, column, and block a cell is a part of using the cell’s position, and then loops through every filled cell in that row, column, or block and keeps track of which values theses filled cells hold. Every unused value is added as a potential candidate of the cell in question. Now, with the simple candidate exclusion complete, each cells candidate set is filled. It is important that simple candidate exclusion is performed only once, because performing it again, as described above, will undo any candidate exclusion performed by more advanced methods.

With all of this back work done, it is time to perform the actual Single strategy itself, and it is pleasantly simple. If an empty cell’s candidate set contains only one value, then that cell will be given that value. In order to keep all empty cells’ candidate sets consistent, after setting the cells value, the cell’s value will be removed from all cells in the same row, column, or block’s candidate set. This candidate removal occurs whenever a cell’s value is set, be it by the Simple Single, Slicing and Slotting, Single, or Hidden Single strategy.

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

No Responses to “Singles”

Comments are closed.