So, here is more Haskell from me, because I really like it. This time around, I wrote a small and simple sudoku solver. Sudokus are really nice little puzzles that involve a partially filled 9x9 grid containing numbers from one to nine. The objective is to fill it following these rules:
- Each number must only appear once per row
- Each number must only appear once per column
- Each number must only appear once per 3x3 ‘box’, of which there are nine
A common strategy is checking empty cells for available numbers to fill in, so the ones that are not already present in the corresponding row, column or box. This is also the approach my solver takes, by checking each of the empty cells for options and, if there is only one possible option, filling it in. Repeat this until there are no empty cells anymore and you have a guaranteed correct solution. There is a great deal of mathematics behind sudoku puzzles, and if you are interested in that, the Wikipedia article is a great read.
Because I wrote my solver before conducting any research, it emulates my approach, which is brute forcing. Still, it solves 9x9 sudokus in <0.01 seconds. We will now have an in-depth look at it. If you want context, the whole code including an example is on Github.
I implemented the solver in form of a Haskell library that exports three functions:
buildbuilds the internal representation of the puzzle from a list of integers
prettyPrintprints a puzzle
solvesolves a puzzle
build is really simple, because it looks like this:
build :: [Value] -> Grid build vs = zip [0..] vs
This already exposes the internal structure of a puzzle, which is this:
type Value = Int type Coord = Int type Cell = (Coord, Value) type Grid = [Cell]
I chose to use a single associative list over a nested list because it makes the code a whole lot easier to read when accessing various cells of a grid, at the expense of having to do some maths.
prettyPrint is not really worth explaining or even showing, all it does is
dividing a grid into nine chunks, the lines, converting the integers to chars,
replacing zeros with underscores, insert some spaces for readability and prints
the whole thing out. I just added it so I could check the results easily.
solve is the really interesting part here. Solve loops until a puzzle is
solved, which looks like this:
solved :: Grid -> Bool solved = foldr (\(_, v) r -> if v == 0 then False else r) True solve :: Grid -> Grid solve g | solved g = g | otherwise = solve $ fill g (0, get g 0)
fill does is it iterates once through all the cells, and each time it
encounters an empty cell (
(_, 0)), it checks which numbers could be placed in
it. If there is only one possibility, it changes the grid accordingly and
continues. After a complete iteration, it returns the changed grid.
fill :: Grid -> Cell -> Grid fill g c@(n, v) | n >= 81 = g | v /= 0 = fill g next | length opts == 1 = fill (change g (n, (head opts))) next | otherwise = fill g next where next = (n + 1, get g (n + 1)) opts = options g c
change goes through the grid, looking for the cell we want to change,
replaces the value and returns the changed grid, so we can use it for the
remainder of the iteration. It is very easily implemented using a single
change :: Grid -> Cell -> Grid change g (n, v) = map (\(gn, gv) -> if gn == n then (n, v) else (gn, gv)) g
get gets the value of the cell at a coordinate in a grid, pretty simple:
get :: Grid -> Coord -> Value get g n = snd $ g !! n
options on the other hand is a little bit more complicated. It has to check
the row, the column and the box a given cell is in, and check for a number
between one and nine that is not already present in any of them. And because I
chose to use a single list to represent the whole grid, having the list indices
stored inside a cell comes in very handy, because we can use it to calculate
the indices of the other cells in the same row, column and box. But first, this
options :: Grid -> Cell -> [Value] options g (n, _) = let r = (rowWise n) ++ (colWise n) ++ (boxWise n) in filter (`notElem` (map (get g) r)) [1..9]
It looks a bit overloaded, but is actually quite easy.
r is a composite list
that includes all the coordinates (/indices) of the cells that affect the
possible content of this cell. We
map it to get to transform it to a list of
numbers that are not possible here, and then simply return all numbers between
one and nine that are not in that list. If you go back to
fill above, you can
see that if the length of this list is one, this solution is filled in.
To finish this off, here are the three remaining functions that calculate the coordinates of the affecting cells. I planned these out when I could not sleep yesterday.
rowWise :: Coord -> [Coord] rowWise n = let r = n `div` 9 * 9 in [r..(r+8)] colWise :: Coord -> [Coord] colWise n = let os = n`mod` 9 in [os,(os+9)..80] boxWise :: Coord -> [Coord] boxWise n = let c = n `mod` 9 `div` 3 r = n `div` 27 * 3 s = r * 9 + c * 3 in [s..(s+2)] ++ [(s+9)..(s+11)] ++ [(s+18)..(s+20)]
colWise should be pretty easy to understand if you imagine a
grid and try out some example cells.
boxWise is a bit more contrived, what it
generally does it figures out in which of the nine boxes the cell is by
comparing the offset from the left and the offset from the top separately, and
then using the top-left cell of this box as a starting point to get the other
eight coordinates, which are always in the same relative position.
So this is the complete code to solve a sudoku puzzle. If you exclude the printing stuff, it is about 50 lines long, and there is a lot to optimize here, but I will leave it as it is, because I am only interested in the PoC.