Upgrade to Pro — share decks privately, control downloads, hide ads and more …

A Simple Sudoku Solver in Haskell

A Simple Sudoku Solver in Haskell

Bucharest FP

June 28, 2017
Tweet

More Decks by Bucharest FP

Other Decks in Programming

Transcript

  1. Welcome Implement a Sudoku solver as described in (Bird, 2006,

    2010, 2014) Twelve short functions: 5 easy ( ) 4 medium ( ) 3 challenging ( ) 2 / 21
  2. Welcome Implement a Sudoku solver as described in (Bird, 2006,

    2010, 2014) Twelve short functions: 5 easy ( ) 4 medium ( ) 3 challenging ( ) Programming techniques: Top-down programming / wishful thinking 2 / 21
  3. Welcome Implement a Sudoku solver as described in (Bird, 2006,

    2010, 2014) Twelve short functions: 5 easy ( ) 4 medium ( ) 3 challenging ( ) Programming techniques: Top-down programming / wishful thinking Wholemeal programming (prevents a disease called “indexitis”) 2 / 21
  4. Welcome Implement a Sudoku solver as described in (Bird, 2006,

    2010, 2014) Twelve short functions: 5 easy ( ) 4 medium ( ) 3 challenging ( ) Programming techniques: Top-down programming / wishful thinking Wholemeal programming (prevents a disease called “indexitis”) Higher-order functions, recursion, point-free style 2 / 21
  5. How to play Sudoku N = 2 2 4 1

    3 4 2 1 3 N = 3 2 5 1 9 8 2 3 6 3 6 7 1 6 5 4 1 9 2 7 9 3 8 2 8 4 7 1 9 7 6 Fill in the empty cells with digits 1 to N2 such that every row, column and N × N box contains the digits 1 to N2. 3 / 21
  6. How to play Sudoku N = 2 2 4 1

    3 4 2 1 3 3 1 4 2 3 1 2 4 N = 3 2 5 1 9 8 2 3 6 3 6 7 1 6 5 4 1 9 2 7 9 3 8 2 8 4 7 1 9 7 6 4 6 7 3 8 5 7 9 1 4 1 9 4 8 2 5 9 7 3 8 5 2 4 3 7 2 6 8 6 8 1 4 9 5 3 7 4 6 2 5 1 6 5 1 9 3 3 8 5 4 2 Fill in the empty cells with digits 1 to N2 such that every row, column and N × N box contains the digits 1 to N2. 3 / 21
  7. Data types a a · · · a a a

    · · · a . . . . . . ... . . . a a · · · a Matrix a Row a Row a Row a type Matrix a = [Row a] type Row a = [a] 4 / 21
  8. Data types a a · · · a a a

    · · · a . . . . . . ... . . . a a · · · a Matrix a Row a Row a Row a 0 3 0 1 1 0 3 2 3 0 1 0 0 1 0 3 Grid type Matrix a = [Row a] type Row a = [a] type Grid = Matrix Digit type Digit = Int 4 / 21
  9. Data types a a · · · a a a

    · · · a . . . . . . ... . . . a a · · · a Matrix a Row a Row a Row a 0 3 0 1 1 0 3 2 3 0 1 0 0 1 0 3 Grid type Matrix a = [Row a] type Row a = [a] type Grid = Matrix Digit type Digit = Int We assume that digit zero indicates an empty cell: isEmpty :: Digit -> Bool isEmpty 0 = True isEmpty _ = False 4 / 21
  10. Exercise 1: solve [ ] solve :: Grid -> [Grid]

    solve = undefined Given: -- Generates grids by replacing empty entries -- with all possible choices completions :: Grid -> [Grid] 5 / 21
  11. Exercise 1: solve [ ] solve :: Grid -> [Grid]

    solve = undefined Given: -- Generates grids by replacing empty entries -- with all possible choices completions :: Grid -> [Grid] -- Tests whether a grid is a valid solution: -- has different entries in each row, column and box valid :: Grid -> Bool 5 / 21
  12. Exercise 1: solve [ ] solve :: Grid -> [Grid]

    solve = undefined Given: -- Generates grids by replacing empty entries -- with all possible choices completions :: Grid -> [Grid] -- Tests whether a grid is a valid solution: -- has different entries in each row, column and box valid :: Grid -> Bool Example: 0 3 0 1 1 0 3 2 3 0 1 0 0 1 0 3 Grid 2 3 4 1 1 4 3 2 3 2 1 4 4 1 2 3 Grid 5 / 21
  13. Exercise 2: completions [ ] completions :: Grid -> [Grid]

    completions = undefined Given: -- Replaces empty entries with all possible choices -- for that entry choices :: Grid -> Matrix [Digit] 6 / 21
  14. Exercise 2: completions [ ] completions :: Grid -> [Grid]

    completions = undefined Given: -- Replaces empty entries with all possible choices -- for that entry choices :: Grid -> Matrix [Digit] -- Generates a list of all possible boards -- from a given matrix of choices expand :: Matrix [Digit] -> [Grid] 6 / 21
  15. Exercise 2: completions [ ] completions :: Grid -> [Grid]

    completions = undefined Given: -- Replaces empty entries with all possible choices -- for that entry choices :: Grid -> Matrix [Digit] -- Generates a list of all possible boards -- from a given matrix of choices expand :: Matrix [Digit] -> [Grid] Example: 0 3 0 1 1 0 3 2 3 0 1 0 0 1 0 3 Grid 1 3 1 1 1 1 3 2 3 1 1 1 1 1 1 3 Grid 1 3 1 1 1 1 3 2 3 1 1 1 1 1 2 3 Grid · · · 4 3 4 1 1 4 3 2 3 4 1 4 4 1 4 3 Grid 6 / 21
  16. Exercise 3: choices [ ] choices :: Grid -> Matrix

    [Digit] choices = undefined 7 / 21
  17. Exercise 3: choices [ ] choices :: Grid -> Matrix

    [Digit] choices = undefined Example: 0 3 0 1 1 0 3 2 3 0 1 0 0 1 0 3 Matrix Digit 1 2 3 1 2 1 3 4 0 3 4 0 1 1 2 3 2 0 3 4 0 0 3 1 2 1 1 2 0 3 4 0 3 4 1 2 1 1 2 3 3 4 0 3 4 0 Matrix [Digit] 7 / 21
  18. Exercise 3: choices [ ] choices :: Grid -> Matrix

    [Digit] choices = undefined Example: 0 3 0 1 1 0 3 2 3 0 1 0 0 1 0 3 Matrix Digit 1 2 3 1 2 1 3 4 0 3 4 0 1 1 2 3 2 0 3 4 0 0 3 1 2 1 1 2 0 3 4 0 3 4 1 2 1 1 2 3 3 4 0 3 4 0 Matrix [Digit] Hint: Define a helper function choice :: Digit -> [Digit] 7 / 21
  19. Exercise 4: expand [ ] expand :: Matrix [Digit] ->

    [Grid] expand = undefined 8 / 21
  20. Exercise 4: expand [ ] expand :: Matrix [Digit] ->

    [Grid] expand = undefined Given: -- Computes the cartesian product of a list of lists cp :: [[a]] -> [[a]] 8 / 21
  21. Exercise 4: expand [ ] expand :: Matrix [Digit] ->

    [Grid] expand = undefined Given: -- Computes the cartesian product of a list of lists cp :: [[a]] -> [[a]] Example: 1 2 3 1 2 1 3 4 0 3 4 0 1 1 2 3 2 0 3 4 0 0 3 1 2 1 1 2 0 3 4 0 3 4 1 2 1 1 2 3 3 4 0 3 4 0 Matrix [Digit] 1 3 1 1 1 1 3 2 3 1 1 1 1 1 1 3 1 3 1 1 1 1 3 2 3 1 1 1 1 1 2 3 · · · 4 3 4 1 1 4 3 2 3 4 1 4 4 1 4 3 8 / 21
  22. Exercise 4: expand [ ] expand :: Matrix [Digit] ->

    [Grid] expand = undefined Given: -- Computes the cartesian product of a list of lists cp :: [[a]] -> [[a]] Example: 1 2 3 1 2 1 3 4 0 3 4 0 1 1 2 3 2 0 3 4 0 0 3 1 2 1 1 2 0 3 4 0 3 4 1 2 1 1 2 3 3 4 0 3 4 0 Matrix [Digit] 1 3 1 1 1 1 3 2 3 1 1 1 1 1 1 3 1 3 1 1 1 1 3 2 3 1 1 1 1 1 2 3 · · · 4 3 4 1 1 4 3 2 3 4 1 4 4 1 4 3 Hints: First generate all combinations across each row Then combine those generated combinations 8 / 21
  23. Exercise 5: cp [ ] cp :: [[a]] -> [[a]]

    cp = undefined Example: cp [[1, 2], [3, 4]] = [[1, 3], [1, 4], [2, 3], [2, 4]] 9 / 21
  24. Exercise 5: cp [ ] cp :: [[a]] -> [[a]]

    cp = undefined Example: cp [[1, 2], [3, 4]] = [[1, 3], [1, 4], [2, 3], [2, 4]] Hint: Use recursion, with the following base case cp [] = [[]] 9 / 21
  25. Exercise 5: cp [ ] cp :: [[a]] -> [[a]]

    cp = undefined Example: cp [[1, 2], [3, 4]] = [[1, 3], [1, 4], [2, 3], [2, 4]] Hint: Use recursion, with the following base case cp [] = [[]] xss 1 2 3 4 5 9 / 21
  26. Exercise 5: cp [ ] cp :: [[a]] -> [[a]]

    cp = undefined Example: cp [[1, 2], [3, 4]] = [[1, 3], [1, 4], [2, 3], [2, 4]] Hint: Use recursion, with the following base case cp [] = [[]] xss' 1 2 xs 3 4 5 9 / 21
  27. Exercise 5: cp [ ] cp :: [[a]] -> [[a]]

    cp = undefined Example: cp [[1, 2], [3, 4]] = [[1, 3], [1, 4], [2, 3], [2, 4]] Hint: Use recursion, with the following base case cp [] = [[]] xss' cp xss' 1 2 xs 3 4 5 3 4 3 5 9 / 21
  28. Exercise 5: cp [ ] cp :: [[a]] -> [[a]]

    cp = undefined Example: cp [[1, 2], [3, 4]] = [[1, 3], [1, 4], [2, 3], [2, 4]] Hint: Use recursion, with the following base case cp [] = [[]] xss' cp xss' 1 2 xs 3 4 5 3 4 3 5 1 3 4 1 3 5 1 9 / 21
  29. Exercise 5: cp [ ] cp :: [[a]] -> [[a]]

    cp = undefined Example: cp [[1, 2], [3, 4]] = [[1, 3], [1, 4], [2, 3], [2, 4]] Hint: Use recursion, with the following base case cp [] = [[]] xss' cp xss' 1 2 xs 3 4 5 3 4 3 5 1 3 4 1 3 5 1 2 3 4 2 3 5 2 9 / 21
  30. Exercise 5: cp [ ] cp :: [[a]] -> [[a]]

    cp = undefined Example: cp [[1, 2], [3, 4]] = [[1, 3], [1, 4], [2, 3], [2, 4]] Hint: Use recursion, with the following base case cp [] = [[]] xss' cp xss' 1 2 xs 3 4 5 3 4 3 5 1 3 4 1 3 5 1 2 3 4 2 3 5 2 ++ 9 / 21
  31. Intermezzo 0 3 0 1 1 0 3 2 3

    0 1 0 0 1 0 3 1 2 3 1 2 1 3 4 0 3 4 0 1 1 2 3 2 0 3 4 0 0 3 1 2 1 1 2 0 3 4 0 3 4 1 2 1 1 2 3 3 4 0 3 4 0 1 3 1 1 1 1 3 2 3 1 1 1 1 1 1 3 · · · 4 3 4 1 1 4 3 2 3 4 1 4 4 1 4 3 Finished implementing the completions function 10 / 21
  32. Intermezzo 0 3 0 1 1 0 3 2 3

    0 1 0 0 1 0 3 1 2 3 1 2 1 3 4 0 3 4 0 1 1 2 3 2 0 3 4 0 0 3 1 2 1 1 2 0 3 4 0 3 4 1 2 1 1 2 3 3 4 0 3 4 0 1 3 1 1 1 1 3 2 3 1 1 1 1 1 1 3 · · · 4 3 4 1 1 4 3 2 3 4 1 4 4 1 4 3 False False Finished implementing the completions function Next, the valid function: test whether a grid is a valid solution 10 / 21
  33. Exercise 6: valid [ ] valid :: Grid -> Bool

    valid = undefined Given: -- Checks that a list contains no duplicates nodups :: [a] -> Bool 11 / 21
  34. Exercise 6: valid [ ] valid :: Grid -> Bool

    valid = undefined Given: -- Checks that a list contains no duplicates nodups :: [a] -> Bool -- Re-orders the values from a matrix's rows, columns -- or boxes to appear along the rows rows :: Matrix a -> Matrix a cols :: Matrix a -> Matrix a boxs :: Matrix a -> Matrix a 11 / 21
  35. Exercise 6: valid [ ] valid :: Grid -> Bool

    valid = undefined Given: -- Checks that a list contains no duplicates nodups :: [a] -> Bool -- Re-orders the values from a matrix's rows, columns -- or boxes to appear along the rows rows :: Matrix a -> Matrix a cols :: Matrix a -> Matrix a boxs :: Matrix a -> Matrix a Examples: 1 3 1 1 1 1 3 2 3 1 1 1 1 1 1 3 False 2 3 4 1 1 4 3 2 3 2 1 4 4 1 2 3 True 11 / 21
  36. Exercise 7: nodups [ ] nodups :: [a] -> Bool

    nodups = undefined Examples: nodups [] = True nodups [1, 2, 3] = True nodups [1, 2, 1] = False 12 / 21
  37. Exercise 7: nodups [ ] nodups :: [a] -> Bool

    nodups = undefined Examples: nodups [] = True nodups [1, 2, 3] = True nodups [1, 2, 1] = False Hints: Use recursion Use Hoogle to find a function of type a -> [a] -> Bool 12 / 21
  38. Exercise 8: rows [ ] rows :: Matrix a ->

    Matrix a Example: 2 3 4 1 1 4 3 2 3 2 1 4 4 1 2 3 2 3 4 1 1 4 3 2 3 2 1 4 4 1 2 3 13 / 21
  39. Exercise 9: cols [ ] cols :: Matrix a ->

    Matrix a Example: 2 3 4 1 1 4 3 2 3 2 1 4 4 1 2 3 2 1 3 4 3 4 2 1 4 3 1 2 1 2 4 3 14 / 21
  40. Exercise 9: cols [ ] cols :: Matrix a ->

    Matrix a Example: 2 3 4 1 1 4 3 2 3 2 1 4 4 1 2 3 2 1 3 4 3 4 2 1 4 3 1 2 1 2 4 3 Hints: Use recursion Define a case for a one-row matrix; example: cols [[1,2,3,4]] = [[1],[2],[3],[4]] For the recursive case, use the zipWith function: zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] 14 / 21
  41. Exercise 10: boxs [ ] boxs :: Matrix a ->

    Matrix a Given: -- Groups a list into lists of length two group :: [a] -> [[a]] 15 / 21
  42. Exercise 10: boxs [ ] boxs :: Matrix a ->

    Matrix a Given: -- Groups a list into lists of length two group :: [a] -> [[a]] -- Flattens a nested list of elements ungroup :: [[a]] -> [a] 15 / 21
  43. Exercise 10: boxs [ ] boxs :: Matrix a ->

    Matrix a Given: -- Groups a list into lists of length two group :: [a] -> [[a]] -- Flattens a nested list of elements ungroup :: [[a]] -> [a] Example: 2 3 4 1 1 4 3 2 3 2 1 4 4 1 2 3 2 3 1 4 4 1 3 2 3 2 4 1 1 4 2 3 15 / 21
  44. Exercise 10: boxs [ ] boxs :: Matrix a ->

    Matrix a Given: -- Groups a list into lists of length two group :: [a] -> [[a]] -- Flattens a nested list of elements ungroup :: [[a]] -> [a] Example: 2 3 4 1 1 4 3 2 3 2 1 4 4 1 2 3 2 3 1 4 4 1 3 2 3 2 4 1 1 4 2 3 Hints: Use the previously defined cols function Chain five transformations (see next slide) 15 / 21
  45. Exercise 10: boxs [ ] 2 3 4 1 1

    4 3 2 3 2 1 4 4 1 2 3 16 / 21
  46. Exercise 10: boxs [ ] 2 3 4 1 1

    4 3 2 3 2 1 4 4 1 2 3 2 3 4 1 1 4 3 2 3 2 1 4 4 1 2 3 16 / 21
  47. Exercise 10: boxs [ ] 2 3 4 1 1

    4 3 2 3 2 1 4 4 1 2 3 2 3 4 1 1 4 3 2 3 2 1 4 4 1 2 3 2 3 4 1 1 4 3 2 3 2 1 4 4 1 2 3 16 / 21
  48. Exercise 10: boxs [ ] 2 3 4 1 1

    4 3 2 3 2 1 4 4 1 2 3 2 3 4 1 1 4 3 2 3 2 1 4 4 1 2 3 2 3 4 1 1 4 3 2 3 2 1 4 4 1 2 3 2 3 1 4 4 1 3 2 3 2 4 1 1 4 2 3 16 / 21
  49. Exercise 10: boxs [ ] 2 3 4 1 1

    4 3 2 3 2 1 4 4 1 2 3 2 3 4 1 1 4 3 2 3 2 1 4 4 1 2 3 2 3 4 1 1 4 3 2 3 2 1 4 4 1 2 3 2 3 1 4 4 1 3 2 3 2 4 1 1 4 2 3 2 3 1 4 4 1 3 2 3 2 4 1 1 4 2 3 16 / 21
  50. Exercise 10: boxs [ ] 2 3 4 1 1

    4 3 2 3 2 1 4 4 1 2 3 2 3 4 1 1 4 3 2 3 2 1 4 4 1 2 3 2 3 4 1 1 4 3 2 3 2 1 4 4 1 2 3 2 3 1 4 4 1 3 2 3 2 4 1 1 4 2 3 2 3 1 4 4 1 3 2 3 2 4 1 1 4 2 3 2 3 1 4 4 1 3 2 3 2 4 1 1 4 2 3 16 / 21
  51. Exercise 11: group [ ] group :: [a] -> [[a]]

    Example: group [1,2,3,4] = [[1,2],[3,4]] 17 / 21
  52. Exercise 12: ungroup [ ] ungroup :: [[a]] -> [a]

    Example: ungroup [[1,2],[3,4]] = [1,2,3,4] 18 / 21
  53. Exercise 12: ungroup [ ] ungroup :: [[a]] -> [a]

    Example: ungroup [[1,2],[3,4]] = [1,2,3,4] Hints: Use Hoogle 18 / 21
  54. That’s all folks Time to solve some Sudokus The current

    approach is inefficient, but correct 19 / 21
  55. That’s all folks Time to solve some Sudokus The current

    approach is inefficient, but correct Equational reasoning to improve performance 19 / 21
  56. That’s all folks Time to solve some Sudokus The current

    approach is inefficient, but correct Equational reasoning to improve performance Define a function prune that eliminates early invalid solutions filter valid . expand = filter valid . expand . prune 19 / 21
  57. That’s all folks Time to solve some Sudokus The current

    approach is inefficient, but correct Equational reasoning to improve performance Define a function prune that eliminates early invalid solutions filter valid . expand = filter valid . expand . prune It is not hard to define a function to prune a row (exercise): pruneRow [[4],[1,2],[1],[1,3]] = [[4],[2],[1],[3]] 19 / 21
  58. That’s all folks Time to solve some Sudokus The current

    approach is inefficient, but correct Equational reasoning to improve performance Define a function prune that eliminates early invalid solutions filter valid . expand = filter valid . expand . prune It is not hard to define a function to prune a row (exercise): pruneRow [[4],[1,2],[1],[1,3]] = [[4],[2],[1],[3]] Equational reasoning to define prune in terms of pruneRow 19 / 21
  59. That’s all folks Time to solve some Sudokus The current

    approach is inefficient, but correct Equational reasoning to improve performance Define a function prune that eliminates early invalid solutions filter valid . expand = filter valid . expand . prune It is not hard to define a function to prune a row (exercise): pruneRow [[4],[1,2],[1],[1,3]] = [[4],[2],[1],[3]] Equational reasoning to define prune in terms of pruneRow The function pruneRow satisfies the equation filter nodups . cp = filter nodups . cp . pruneRow 19 / 21
  60. That’s all folks Time to solve some Sudokus The current

    approach is inefficient, but correct Equational reasoning to improve performance Define a function prune that eliminates early invalid solutions filter valid . expand = filter valid . expand . prune It is not hard to define a function to prune a row (exercise): pruneRow [[4],[1,2],[1],[1,3]] = [[4],[2],[1],[3]] Equational reasoning to define prune in terms of pruneRow The function pruneRow satisfies the equation filter nodups . cp = filter nodups . cp . pruneRow Expand the expression filter valid . expand 19 / 21
  61. That’s all folks Time to solve some Sudokus The current

    approach is inefficient, but correct Equational reasoning to improve performance Define a function prune that eliminates early invalid solutions filter valid . expand = filter valid . expand . prune It is not hard to define a function to prune a row (exercise): pruneRow [[4],[1,2],[1],[1,3]] = [[4],[2],[1],[3]] Equational reasoning to define prune in terms of pruneRow The function pruneRow satisfies the equation filter nodups . cp = filter nodups . cp . pruneRow Expand the expression filter valid . expand Use the above equation and compress back the formula 19 / 21
  62. Further references Richard Bird’s papers and books (Bird, 2006, 2010,

    2014) Conor McBride’s Sudoku solver using applicative and traversable: https://stackoverflow.com/a/10242673/474311 20 / 21
  63. References Bird, R. (2010). Pearls of Functional Algorithm Design. Cambridge

    University Press. Bird, R. (2014). Thinking Functionally with Haskell. Cambridge University Press. Bird, R. S. (2006). A program to solve Sudoku. Journal of Functional Programming, 16(6):671–679. 21 / 21