Skip to main content

2. Sudoku (3)

09/02/23

choices - takes your easy grid, replaces each blank cell with 1-9 (all possible choices) collapse - takes all the possible values filter - no duplicates in any row, column, box etc prune - removes any choices which occur in single entries fix prune -

Blocked Matrices​

Choice matrix being void and safe

Void​

If at least one cell has no choices

void :: Matrix Choices -> Bool
void m = any (any null) m -- any - will take predicate and check to see if it holds true for combination. In this case if true for any null

any :: (a -> Bool) -> [a] -> Bool

Safe​

If all the rows, columns, boxes are consistent

safe :: Matrix Choices -> Bool
safe m = all consistent (rows m) && all consistent (cols m) && all consisntent (boxs m)

consistent :: Row Choices -> Bool
blocked :: Matrix Choices -> Bool
blocked m = void m || not (safe m) -- empty cells || duplicated single cells

Solve4 & Search​

solve4 = search . prune . choices 

search :: Matrix Choices -> [Grid]
search m | blocked m = []
        | all (all single) m = collapse m
        | otherwise = [g | m' <- expand m, g <- search (prune m')] -- Expand will expand only the first cell which has more than one option. Prune will remove any 'silly choice' then do it again etc

single :: [a] -> Bool
single [_] = True
single _ = False