【正文】 grid is valid if it has no duplicate entries in any row, column or box: valid :: Grid ? Bool valid g = all nodups (rows g) ? all nodups (cols g) ? all nodups (boxs g) A direct implementation, without concern for efficiency. 18 Making Choices Replace each blank square in a grid by all possible numbers 1 to 9 for that square: choices :: Grid ? Matrix [Char] 1 2 3 4 5 6 3 7 8 9 1 2 3 4 4 5 6 7 8 9 3 4 19 Collapsing Choices Transform a matrix of lists into a list of matrices by considering all binations of choices: collapse :: Matrix [a] ? [Matrix a] 1 3 4 1 2 3 4 2 2 3 4 1 1 3 4 2 1 2 3 4 1 2 20 A Brute Force Solver solve :: Grid ? [Grid] solve = filter valid . collapse . choices Consider all possible choices for each blank square, collapse the resulting matrix, then filter out the valid grids. 21 Does It Work? solve easy ERROR: out of memory Simple, but impractical! The easy example has 51 blank squares, resulting in 951 grids to consider, which is a huge number: 4638397686588101979328150167890591454318967698009 22 Reducing The Search Space ? Many choices that are considered will conflict with entries provided in the initial grid。 ? Became popular in Japan in 1986, where it was renamed Sudoku (~ “single number”)。 gentle No solution after two hours we need to think further! For a gentle example, pruning leaves around 381 grids to consider, which is still a huge number: 443426488243037769948249630619149892803 30 Reducing The Search Space ? After pruning there may still be many choices that can never lead to a soluti