Skip to main content
added 7 characters in body; edited title
Source Link
Jamal
  • 34.9k
  • 13
  • 133
  • 237

Backtracking sudoku Making backtracking Sudoku solver, more functional?

I'm implementing the backtracking solving algorithm for a sudokuSudoku in f# and I'mF#. I'm wondering if I could make my code tobetter respect more 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

Backtracking sudoku solver, more functional?

I'm implementing the backtracking solving algorithm for a sudoku in f# and I'm wondering if I could make my code to respect more the functional programming paradigm or even just 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

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
edited tags
Link
200_success
  • 144.2k
  • 22
  • 188
  • 473
Source Link
Bruno
  • 582
  • 3
  • 12

Backtracking sudoku solver, more functional?

I'm implementing the backtracking solving algorithm for a sudoku in f# and I'm wondering if I could make my code to respect more the functional programming paradigm or even just 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