F# - Sudoku Solver using search trees Step one: Defining the data structure
Post date: Jan 28, 2012 11:56:30 PM
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 .
Full Source: http://code.google.com/p/peter-henell-f-sharp-sudoku-solver/source/browse/#git%2FSearchTrees
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<int>) = 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<Node>) new (content: List<int>) = 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: false1; 3; 0; 0; 0; 0; 0; 0; 0; Is Goal: false1; 4; 0; 0; 0; 0; 0; 0; 0; Is Goal: false1; 5; 0; 0; 0; 0; 0; 0; 0; Is Goal: false1; 6; 0; 0; 0; 0; 0; 0; 0; Is Goal: false1; 7; 0; 0; 0; 0; 0; 0; 0; Is Goal: false1; 8; 0; 0; 0; 0; 0; 0; 0; Is Goal: false1; 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
Full Source: http://code.google.com/p/peter-henell-f-sharp-sudoku-solver/source/browse/#git%2FSearchTrees
For Step Two: Sudoku Solver using search trees Step two: The algorithm