F# - Sudoku Solver using search trees Step Five: Defining the data structure for the complete problem

Post date: Feb 5, 2012 9:21:58 PM

Part one: https://sites.google.com/site/mrmbookmarks/msg/F---Sudoku-Solver-using-search-trees-Step-one-Defining-the-datastructure

Part two: https://sites.google.com/site/mrmbookmarks/msg/F---Sudoku-Solver-using-search-trees-Step-two-The-algorithm

Part Three: https://sites.google.com/site/mrmbookmarks/msg/F---Sudoku-Solver-using-search-trees-Step-Three-Adding-Unit-Tests

Part Four: https://sites.google.com/site/mrmbookmarks/msg/F---Sudoku-Solver-using-search-trees-Step-Four-Adding-more-Unit-Tests

Part Five: https://sites.google.com/site/mrmbookmarks/msg/F---Sudoku-Solver-using-search-trees-Step-Five-Defining-the-data-structure-for-the-complete-problem

Part Six: https://sites.google.com/site/mrmbookmarks/msg/F---Sudoku-Solver-using-search-trees-Step-Six-Solving-Sudoku

Party Seven: https://sites.google.com/site/mrmbookmarks/msg/F---Sudoku-Solver-using-search-trees-Step-Seven-Increasing-performance-using-parallel-tasks

Full Source: http://code.google.com/p/peter-henell-f-sharp-sudoku-solver/source/browse/#git%2FSearchTrees

To move on to solve the complete Sudoku problem we need to evolve our data structure first.

I created a new small project to test this out before merging it into the big solution.

I decided to use one list to hold all the values, using zero to indicate a spot that have not been taken yet.

The list is only logically separated into Regions, Rows and Columns. This is done by internal functions of the type.

For information about rules of Sudoku check this site: http://www.sudoku.name/rules/en

In my data structure:

• Regions are numbered one to nine
• Rows are numbered one to nine
• Columns are numbered one to nine

Since all the three different "views" of the data is returned as lists we can use the same simple function to know if a number is already in that region, row or column.

I created a function isIn that simply checks if the searched for item is in the supplied list.

I also added interface functions for checking if an item is in a region, row or column. So far these functions all call the same function but that might change.

In the next step we will once again implement the functions required for the algorithm: isGoal, equalTo and getChildren. Of course this will require us to create supporting private functions inside the data structures.

TestingNewSudokuProblem.fs

type SudokuProblemComplete(board : list<int>) = // Regions // 1; 2; 3 // 4; 5; 6 // 7; 8; 9 let getRegion r = let r = r - 1 [ (List.nth board (0+r)) ; (List.nth board (1+r)) ; (List.nth board (2+r)) (List.nth board ((0+r) + 9)) ; (List.nth board ((1+r) + 9)) ; (List.nth board ((2+r) + 9)) (List.nth board ((0+r) + 18)) ; (List.nth board ((1+r) + 18)) ; (List.nth board ((2+r) + 18)) ] let getRow r = let r = r - 1 [for i in 0..8 -> List.nth board (i + r * 9)] let getCol c = let c = c - 1 [for i in 0..8 -> List.nth board (c + 9 * i)] let isIn lst i = lst |> List.exists(fun x -> x = i) let isInCol c i = isIn c i let isInRow r i = isIn r i let isInRegion r i = isIn r i member this.PrintTests = printfn "Regions" for i in [1..9] do printfn "%O" (getRegion i) printfn "Rows" for i in [1..9] do printfn "%O" (getRow i) printfn "Cols" for i in [1..9] do printfn "%O" (getCol i) type SudokuNode(content : SudokuProblemComplete) = member this.Content = content member this.isGoal = false member this.getChildren = [content] member this.equalTo other = false member this.print = printfn "N/A"// Testing of the type begin here let board = [ 0; 0; 8; 0; 1; 0; 0; 0; 9; 6; 0; 1; 0; 9; 0; 2; 3; 0; 0; 4; 0; 0; 3; 7; 0; 0; 5; 0; 3; 5; 0; 0; 8; 2; 0; 0; 0; 0; 2; 6; 5; 0; 8; 0; 0; 0; 0; 4; 0; 0; 1; 7; 5; 0; 5; 0; 0; 3; 4; 0; 0; 8; 0; 0; 9; 7; 0; 8; 0; 5; 0; 6; 1; 0; 0; 0; 6; 0; 9; 0; 0; ] let sc = new SudokuProblemComplete(board) sc.PrintTests