1. Sudoku (2)

06/02/23

A basic solver

Function Composition

-- Defined by
(f.g)x = f(g x)
-- Or clever way
f . g = \x -> f (g x)

solve :: Grid -> [Grid]
solve = filter valid . collapse . choices

filter - library function that keeps all elements of a list that satisfy a given property. filter even [1..10] = [2,4,6,8.10]

Making Choices

type Choices = [Value] -- List of values 1-9
choices :: Grid -> Matrix Choices
choices g = map (map choice) g
            where 
                choice v = if v == '.' then
                    ['1'..'9']
                    else
                        [v]

or as choices = map (map choice

Making Collapse

cp [[1,2],[3,4],[5,6]] = [[1,3,5],[1,3,6],[1,4,5],..] -- Chooses all the possible combinations as a list
cp :: [[a]] -> [[a]]
cp [] = [[]]
cp (xs:xss) = [y:ys | y <- xs,ys <- cp xss] 

collapse :: Matrix [a] -> [Matrix a]
collapse m = cp (map cp m) -- Collapse each row | cp.. will collapse each col

This Sudoku solver will solve, but is incredibly slow. We will be dead by then

Pruning the search space

Check this section again (30 mins)

prune :: Matrix Choices -> Matrix Choices-- Prune out any choices which are single entry in the column
prune = pruneBy boxes . proneBy cols . pruneBy rows where proneBy f = f . map reduce . f

reduce :: Row Choices -> Row Choices
> reduce ["1234","1","34","3"]
> ["24","1","4","3"]

solve2 = filter valid . collapse . prune . choices

Can keep reducing to make the choice list smaller. Can keep iterating to remove repeated choices. Will end up reaching a fixed point

Recursive Pruning

solve3 = filter valid . collapse . fix prune . choices

fix :: Eq a => (a -> a) -> a -> a
fix f x = if x == x' then x else fix f x'
        where x' = f x