Just Code‎ > ‎

### F# - Sudoku Solver using search trees Step one: Defining the data structure

posted Jan 28, 2012, 3:56 PM by Peter Henell   [ updated Feb 19, 2012, 2:16 AM ]
 Few years ago i did a Sudoku solver in C# using search trees (depth first, width first) https://sites.google.com/site/mrmbookmarks/msg/C-WidthDepth-first-tree-search-soduko-solver . I'm now using this fun problem to learn F#. To begin with i will not solve Sudoku, instead i will solve a part of the sudoku problem: ```// [list of 9 items] // Rules: // every item in the list must be unique // only numbers 1-9 are considered valid // use 0 (zero) to indicate that a spot in the list have not been taken by any number // Input to the function is an list where one of the fields is a number between 1 and 9 // The result should be a list with all nine slots filled with unique numbers ``` To solve this problem we begin with defining the data structure required. Since this is used in a search tree i will call the main data structure "Node". The node will exist of some set of data and methods for comparing and generating new Nodes. I have abstracted the data part of node into a class of it's own, i call this SodukoProblem (Yes, i misspelled it again). I find that this separation allow me to easier manage the problem. My previous experience tell me that the data structure will need to support a few methods:  Get Children - A method of generating new Nodes to be examined based on the current node. The children are one step more evolved than the parent. Compare to other - A method of comparing this Node to another node to know if we already examined that Node. Is Goal - A method of knowing if we have reached the goal Print - Some way of printing the data structure for visual output This is our data structure at this moment: ```namespace DataStructure // This defines the datastructure containing the values type SodukoProblem(board : (int *int *int *int *int *int *int *int *int))= let Board = board member this.toList = match Board with | (a, b, c, d, e, f, g, h, i) -> [a; b; c; d; e; f; g; h; i] // find the first available slot (a slot that is zero) member this.findSpotFor value = match Board with | (0, b, c, d, e, f, g, h, i) -> [value; b; c; d; e; f; g; h; i] | (a, 0, c, d, e, f, g, h, i) -> [a; value; c; d; e; f; g; h; i] | (a, b, 0, d, e, f, g, h, i) -> [a; b; value; d; e; f; g; h; i] | (a, b, c, 0, e, f, g, h, i) -> [a; b; c; value; e; f; g; h; i] | (a, b, c, d, 0, f, g, h, i) -> [a; b; c; d; value; f; g; h; i] | (a, b, c, d, e, 0, g, h, i) -> [a; b; c; d; e; value; g; h; i] | (a, b, c, d, e, f, 0, h, i) -> [a; b; c; d; e; f; value; h; i] | (a, b, c, d, e, f, g, 0, i) -> [a; b; c; d; e; f; g; value; i] | (a, b, c, d, e, f, g, h, 0) -> [a; b; c; d; e; f; g; h; value] | (a, b, c, d, e, f, g, h, i) -> [] static member FromList (l : List) = match l with | [a; b; c; d; e; f; g; h; i] -> new SodukoProblem(a, b, c, d, e, f, g, h, i) | _ -> raise (System.ArgumentException("Wrong number of items in the supplid list")) // This defines the rules type Node(content: SodukoProblem, parent: Node ) = let Contentpriv = content let Parent = parent member this.Content = Contentpriv // A child of n is a node where a new value have been added to the array on a legal spot member this.getChildren = let taken = Set.ofList content.toList |> Set.toList let possible = [1..9] |> List.filter(fun x -> not ( List.exists(fun m -> m = x) taken)) let coll = possible |> List.map(fun x -> content.findSpotFor x) |> List.filter(fun x -> (List.length x) > 0) coll |> List.map(fun x -> new Node(SodukoProblem.FromList x, Parent)) member this.equalTo (other : Node) = other.Content.toList = Contentpriv.toList //true member this.isGoal = Set.count (Set.ofList Contentpriv.toList) = 9 && not (List.exists(fun x -> x = 0) Contentpriv.toList ) member this.print = printfn "%O" Contentpriv.toList new (content: SodukoProblem) = Node(content, Unchecked.defaultof) new (content: List) = match content with | [a; b; c; d; e; f; g; h; i] -> new Node(new SodukoProblem(a, b, c, d, e, f, g, h, i)) | _ -> Node([]) ``` To begin testing this data structure we will use this simple script: ```module Program open DataStructure let printList l = match l with | [a; b; c; d; e; f; g; h; i] -> printfn "%d; %d; %d; %d; %d; %d; %d; %d; %d;" a b c d e f g h i | _ -> printfn "" let step1 = new SodukoProblem(1, 0, 0, 0, 0, 0, 0, 0, 0) let step2 = SodukoProblem.FromList (step1.findSpotFor 2) let step3 = SodukoProblem.FromList (step2.findSpotFor 3) let step4 = SodukoProblem.FromList (step3.findSpotFor 4) let step5 = SodukoProblem.FromList (step4.findSpotFor 5) let step6 = SodukoProblem.FromList (step5.findSpotFor 6) let step7 = SodukoProblem.FromList (step6.findSpotFor 7) let step8 = SodukoProblem.FromList (step7.findSpotFor 8) let step9 = SodukoProblem.FromList (step8.findSpotFor 9) printfn "Check the internals of each step" printList step1.toList printList step2.toList printList step3.toList printList step4.toList printList step5.toList printList step6.toList printList step7.toList printList step8.toList printList step9.toList printfn "" let n = new Node(step1) let n8 = new Node(step8) let chi = n.getChildren let chi8 = n8.getChildren printfn "Check if the first step generated the children ok" for c in chi do printList c.Content.toList printfn "Is Goal: %b" c.isGoal printfn "" printfn "Check if the last child was created ok" for c in chi8 do printList c.Content.toList printfn "Is Goal: %b" c.isGoal ``` Results: ```Check the internals of each step 1; 0; 0; 0; 0; 0; 0; 0; 0; 1; 2; 0; 0; 0; 0; 0; 0; 0; 1; 2; 3; 0; 0; 0; 0; 0; 0; 1; 2; 3; 4; 0; 0; 0; 0; 0; 1; 2; 3; 4; 5; 0; 0; 0; 0; 1; 2; 3; 4; 5; 6; 0; 0; 0; 1; 2; 3; 4; 5; 6; 7; 0; 0; 1; 2; 3; 4; 5; 6; 7; 8; 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; Check if the first step generated the children ok 1; 2; 0; 0; 0; 0; 0; 0; 0; Is Goal: false 1; 3; 0; 0; 0; 0; 0; 0; 0; Is Goal: false 1; 4; 0; 0; 0; 0; 0; 0; 0; Is Goal: false 1; 5; 0; 0; 0; 0; 0; 0; 0; Is Goal: false 1; 6; 0; 0; 0; 0; 0; 0; 0; Is Goal: false 1; 7; 0; 0; 0; 0; 0; 0; 0; Is Goal: false 1; 8; 0; 0; 0; 0; 0; 0; 0; Is Goal: false 1; 9; 0; 0; 0; 0; 0; 0; 0; Is Goal: false Check if the last child was created ok 1; 2; 3; 4; 5; 6; 7; 8; 9; Is Goal: true ``` For Step Two: Sudoku Solver using search trees Step two: The algorithm