A reducer transforms an attempt by eliminating possible values without guessing. In graph coloring, it removes a color from every neighbor of a node whose remaining possibilities have narrowed to one. section 8.5.2
A reducer fits between an attempt and a backtracking search:
- Accept an attempt: a multidictionary from nodes to their possible colors. section 8.5.2
- Find nodes with exactly one remaining value and remove that value from their neighbors. section 8.5.2
- Repeat reductions while new single-value nodes appear, stopping when no further progress is possible. section 8.5.2
Graph coloring and Sudoku
GraphColorReducer<N, C> implements IReducer<N, C> and receives a graph describing which nodes constrain one another. The same reducer structure solves Sudoku by treating cells as nodes and digits as possible colors; reduction propagates fixed digits before recursive guesses explore the remaining possibilities.
