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<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



For Step Two: Sudoku Solver using search trees Step two: The algorithm



Comments