# Making backtracking Sudoku solver more functional

I'm implementing the backtracking solving algorithm for a Sudoku in F#. I'm wondering if I could make my code better respect the functional programming paradigm or even just making it simpler/better.

let solve originalSudoku =
let sudoku = Array2D.copy originalSudoku

let isValidNumber (x,y) n =
let square =
let (x1,y1) = (x/3)*3,(y/3)*3
[| for i in x1..(x1+2) do for j in y1..(y1+2)->(i,j) |]
|> Array.forall(fun (i,j)->sudoku.[i,j]<>n)
let line =
[|0..8|] |> Array.forall(fun i->x=i || sudoku.[i,y]<>n)

let column =
[|0..8|] |> Array.forall(fun i->y=i || sudoku.[x,i]<>n)

line && column && square

let rec isGridValid position=
let x,y = position/9, position%9
if position = 9*9 then
true
else if originalSudoku.[x,y] <> 0 then
isGridValid(position+1)
else
let isValid = isValidNumber (x,y)
let testCurrentCase n =
if isValid n then
sudoku.[x,y] <- n
isGridValid(position+1)
else
false
if ( not([|0..9|] |> Array.exists(testCurrentCase))) then
sudoku.[x,y] <- 0
false
else true

isGridValid 0 |> ignore

sudoku


A purely functional solution would be to get rid of the mutable array and instead use an immutable type like Map<int * int, int>. Your recursive backtracking function would then fill it and return it, instead of modifying a global array. Something like:

let rec solvePosition position sudoku =
let x,y = position/9, position%9
if position = 9*9 then
Some sudoku
else if Map.containsKey (x,y) sudoku then
solvePosition (position+1) sudoku
else
let isValid n = isValidNumber (x,y) n sudoku
let solveCurrentCase n =
if isValid n then
let newSudoku = Map.add (x, y) n sudoku
solvePosition (position+1) newSudoku
else
None
Array.tryPick solveCurrentCase [|1..9|]

• Thank you! I was worried about that mutable array. If I understand your wiki link well, there would be only one map in memory so your solution will not waste memory or be much slower? – Bruno Jun 12 '14 at 18:56
• Yeah, pretty much. Doing this does introduce some inefficiencies (for example each map you create and then throw away creates a small amount of garbage that has to be handled by the garbage collector), but those shouldn't matter most of the time. – svick Jun 12 '14 at 19:05

The function isValidNumber can take advantage of sequence expressions to make the code more readable. It may also be more efficient, as it will short-circuit the evaluation.

let square =
let squareX = (x / 3) * 3
let squareY = (y / 3) * 3
seq { for i in squareX .. squareX + 2 do
for j in squareY .. squareY + 2 -> sudoku.[i, j] <> n
}

let row = seq { for i in 0 .. 8 -> x = i || sudoku.[i, y] <> n }

let column = seq { for j in 0 .. 8 -> y = j || sudoku.[x, j] <> n }

square |> Seq.append row |> Seq.append column |> Seq.forall id

• That's a good idea thanks! But where does the "id" comes from? – Bruno Jun 11 '14 at 13:41
• @Bruno id is in the Microsoft.FSharp.Core.Operators namespace. See msdn.microsoft.com/en-us/library/ee353607.aspx. – mjolka Jun 11 '14 at 14:12