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)-&gt;(i,j) |] 
            |&gt; Array.forall(fun (i,j)-&gt;sudoku.[i,j]&lt;&gt;n)
        let line = 
            [|0..8|] |&gt; Array.forall(fun i-&gt;x=i || sudoku.[i,y]&lt;&gt;n)

        let column = 
            [|0..8|] |&gt; Array.forall(fun i-&gt;y=i || sudoku.[x,i]&lt;&gt;n)

        line &amp;&amp; column &amp;&amp; square

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

    isGridValid 0 |&gt; ignore

    sudoku
A purely functional solution would be to get rid of the mutable array and instead use an immutable type like Map&lt;int * int, int&gt;. 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|]