4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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|]
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Bruno Jun 12 '14 at 18:56
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – svick Jun 12 '14 at 19:05
3
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.