Relaxation Labeling

A Sudoku puzzle can be considered as a problem to be solved by relaxation labeling (Zucker, 1976).  In relaxation labeling, sets of possible labels are available at different locations.  For instance, at the start of any Sudoku puzzle the possible labels at every blank cell are “1 2 3 4 5 6 7 8 9”.  The task of relaxation labeling is to iteratively eliminate extra labels at ambiguous locations, so that at the end of processing only one label remains.  This is done by propagating constraints.  Once a label has been assigned to one location, the presence of this label can be used to remove incompatible labels from neighboring locations.  Many such constraints can be used to solve Sudoku problems (Delahaye, 2006).  For instance, assume that the digit “9” has been assigned to one cell in a Sudoku problem.  One can propagate the “there can be only one” constraint to remove this as a possible label from any cells in the labeled cell’s cage, row, or column.

References:

1. Delahaye, J. P. (2006). The science behind Sudoku. Scientific American, 294(6), 80-87.
2. Zucker, S. (1976). Relaxation labeling and the reduction of local ambiguities. In C. H. Chen (Ed,), Pattern Recognition And Artificial Intelligence (pp. 852-861). New York: Academic Press.

(Added March 2011)