Making backtracking Sudoku solver more functional

Question

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

Answer 1

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|]

Answer 2

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