To continue learning about F# and to practice programming functionally, I have written a simple Sudoku solver. I use the word simple, because some simple Sudoku problems can be solved only by going over the board and removing entries without having to make “guesses” and backtracking.
This guessing and backtracking usually involves implementing a depth-first search when writing a Sudoku algorithm.
In the interest of time (there’s another project which I have been delaying for months and need to be starting) I have only implemented a solution to the easy type of Sudokus.
The first part is writing code that checks whether a board is correctly solved. This part can be done first and it’s better to do so since we will need it to check whether our Sudoku solver actually works.
The process is pretty easy, in Board.fs I implement the types I need to represent the board (Value) and it’s state (BoardSolved).
Checking the board implies collecting all it’s rows, columns and boxes (which are nine 3×3 regions on the board) and then checking them for duplicates.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
module Board | |
type Value = | |
| Locked of int | |
| Possible of int List | |
type BoardSolved = | |
| Solved | |
| InvalidSolution | |
| BoardUnlocked | |
// Get a series of board elements defined by the function eFunc | |
let private getLinearElements eFunc start end' (board:Value[,]) : Value list = | |
[start..end'] |> List.fold (eFunc) [] | |
// Get the Values at row rowNum | |
let row rowNum (board:Value[,]) : Value list = | |
getLinearElements (fun acc e -> board.[rowNum, e] :: acc) 0 8 board | |
// Get the values at column colNum | |
let column colNum (board:Value[,]) : Value list = | |
getLinearElements (fun acc e -> board.[e, colNum] :: acc) 0 8 board | |
// Get the values at box boxNum. A box is a 3×3 square of which there are 9 in the Sudoku board. | |
// The squares are at fixed position and are numbered sequentially from 0 to 8 with 0 being the top left corner | |
// and 8 and the bottom right corner. | |
let box boxNum (board:Value[,]) : Value list = | |
let startX, endX, startY, endY = match boxNum with | |
| 0 -> 0, 2, 0, 2 | |
| 1 -> 3, 5, 0, 2 | |
| 2 -> 6, 8, 0, 2 | |
| 3 -> 0, 2, 3, 5 | |
| 4 -> 3, 5, 3, 5 | |
| 5 -> 6, 8, 3, 5 | |
| 6 -> 0, 2, 6, 8 | |
| 7 -> 3, 5, 6, 8 | |
| 8 -> 6, 8, 6, 8 | |
| _ -> failwith "Invalid box values. range: 0-8" | |
[startY..endY] | |
|> List.fold (fun acc x -> (getLinearElements (fun acc e -> board.[x, e] :: acc) startX endX board) @ acc) [] | |
let containsDuplicates list : bool = | |
List.length list <> (list |> List.distinct |> List.length) | |
// Check if a particular board is solved by returning it's BoardSolved status. | |
let boardSolved (board:Value[,]) : BoardSolved = | |
let makeLists func = | |
List.init 1 (fun x -> List.init 9 (fun y -> func y board)) | |
// check that all squares are locked | |
let allLocked = board |> Seq.cast<Value> | |
|> Seq.forall (fun e -> match e with | |
| Locked _ -> true | |
| _ -> false) | |
match allLocked with | |
| false -> BoardUnlocked | |
// check for duplicates | |
| true -> match makeLists row |> List.exists (fun x -> x |> List.exists (containsDuplicates)) with | |
| true -> InvalidSolution | |
| false -> match makeLists column |> List.exists (fun x -> x |> List.exists (containsDuplicates)) with | |
| true -> InvalidSolution | |
| false -> match makeLists box |> List.exists (fun x -> x |> List.exists (containsDuplicates)) with | |
| true -> InvalidSolution | |
| false -> Solved |
To solve a board we go over all rows, columns and boxes and for each item in these collections we remove from the list of possible values those values which have already been selected in another item. I call this “locking” the values.
This operation is applied successively until the board is solved. The most complicated part came because I used a 2D array to represent the board but I needed to convert the rows, columns and boxes values to lists. Converting the lists generated from the boxes was the single most complicated and longest part of the whole program.
I guess it pays to just use lists for everything and skip on using arrays. The language and it’s libraries are pretty much made for working with lists and sequences so when you deviate from that you end up having to write additional code.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
module Solver | |
open Board | |
// Takes a Value list in parameter and return a new list with all possible wich are duplicates of | |
// locked values removed | |
let removePossibleEntries (values:Value list) : Value list = | |
// printf "\nremovePossibleEntries entry %A" values | |
// get locked values | |
let locked = values |> List.filter (fun x -> match x with | |
| Locked _ -> true | |
| Possible _ -> false) | |
|> List.map (fun x -> match x with | |
| Locked y -> y | |
| Possible _ -> failwith "Should have been filtered out") | |
// remove locked values from all lists of possible values | |
values |> List.map | |
(fun x -> match x with | |
| Locked y -> Locked y | |
| Possible items -> Possible (List.filter (fun z -> not (List.contains z locked)) items)) | |
// go over all values and switch List of one possible value to a Locked value | |
let lockSingleValues (values:Value list) = | |
// printf "\nlockSingleValues entry %A" values | |
values |> List.map (fun x -> match x with | |
| Possible [a] -> Locked a | |
| Possible (head :: tail) -> Possible (head :: tail) | |
| Possible [] -> failwith "Error this Possible list is empty" | |
| Locked v -> Locked v) | |
// when given a list of of lists each created by the application of the row function, convert it back to a board | |
let newBoardFromRows (items:Value list list) = | |
Array2D.init 9 9 (fun i j -> items.[i].[8-j]) | |
// when given a list of of lists each created by the application of the column function, convert it back to a board | |
let newBoardFromColumns (items:Value list list) = | |
Array2D.init 9 9 (fun i j -> items.[j].[8-i]) | |
// when given a list of of lists each created by the application of the box function, convert it back to a board | |
let newBoardFromBox (items:Value list list) = | |
let unboxed = Array2D.create 9 9 (Locked 0) | |
let si = seq { | |
for h in [0; 3; 6] do yield! seq { | |
for i in 1..3 do yield! seq { | |
for j in 1..3 do yield 0 + h | |
for j in 1..3 do yield 1 + h | |
for j in 1..3 do yield 2 + h | |
} | |
} | |
} | |
let sj = seq { | |
for i in 1..3 do yield! seq { | |
for j in 1..3 do yield! [0..2]; | |
for j in 1..3 do yield! [3..5]; | |
for j in 1..3 do yield! [6..8]; | |
} | |
} | |
let sx = seq { | |
for i in 0..8 do yield! seq { | |
for j in 0..8 do yield i, j | |
} | |
} | |
let coordinates = List.map2 (fun i j -> i, j) (si |> Seq.toList) (sj |> Seq.toList) | |
List.iter2 (fun (x, y) (i, j) -> Array2D.set unboxed x y (items.[i].[8-j])) (sx |> Seq.toList) coordinates | |
unboxed | |
// remove and lock values | |
// remove = remove elements in lists of possible values. We remove those values which already appear somewhere else in | |
// the unit | |
// lock = when there is only one possible value we change it from a list of 1 possible to a locked value | |
let removeAndLock (board:Value[,]) = | |
let perform func dest = | |
[0..8] |> List.map (fun i -> func i dest |> removePossibleEntries |> lockSingleValues) | |
// perform row board |> perform column |> perform box | |
perform row board |> newBoardFromRows |> perform column |> newBoardFromColumns |> perform box |> newBoardFromBox | |
let solve (board:Value[,]) = | |
// call removeAndLock, if board has changed call it again in case we are able to remove more possible values | |
// after the changes in the first removeAndLock call | |
let rec exclusionStep previousStep = | |
let currentStep = removeAndLock previousStep | |
if currentStep = previousStep then currentStep else exclusionStep currentStep | |
let newBoard = exclusionStep board | |
// check if the board is solved otherwise try to solve the board by trying arbitrary values | |
match boardSolved newBoard with | |
// we can return this valid board | |
| Solved -> newBoard | |
// we need to continue not all squares are filled | |
| BoardUnlocked -> failwith "Board not yet solved" | |
// we have come to an invalid solution after the exclusionStep, this shouldn't be happening | |
| InvalidSolution -> failwith "InvalidSolution after performStep" |
Here is the GitHub repo with the whole thing.
To make this solver capable of solving any Sudoku, we would need to change the
| BoardUnlocked -> failwith “Board not yet solved”
line with calling a depth-first search which would select the first unlocked value, try and select the first possible value for this item and then continue recursively trying to solve the board until either it succeeds or it fails. When/if it fails backtrack and continue it’s search using another value.