# 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: **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**

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