Just Code‎ > ‎

F# - Sudoku Solver using search trees Step two: The algorithm

posted Jan 28, 2012, 4:03 PM by Peter Henell   [ updated Feb 19, 2012, 2:16 AM ]


Continuing to solve the Sudoku problem we will here define the algorithm. Attached at the bottom of this page is the full source code used so far.

By running the code below we now know that the algorithm is working (it produces the expected output, there could be many bugs in it still). We will in the next step evolve the Node and SodukoProblem data structures to handle the real Sudoku problem. The beauty of the separation of algorithm and data structure is that the algorithm does not need to be changed when you want to solve some other problem. You only need to change the data structure. 

The goal when we start evolving the code is not only to solve the problem but also make the code be smarter and make use of functionality offered by F#.

This is the Solver agent so far:
module Solver
open DataStructure

exception NoSolutionFound of string
exception SolutionWasFound of Node

type Solver() =

    // Right now the internalSolve is not really recursive, it is more of a loop. Todo: Figure out a good way of making it use recursion in a smart way
    member this.solve (rf: Node) =
        let openNodes = []
        let closedNodes = []
        let nodes = []

        let root = rf
        let openNodes =  root :: openNodes
    
        let rec internalSolve (nodesToExamine : List<Node>)  = 
            if nodesToExamine.Length = 0 then 
               raise (NoSolutionFound("Could not find solution even after " + closedNodes.Length.ToString() + " tries" ))

            let node = nodesToExamine.Head // pick up the node we are going to examine
            let closedNodes = node :: closedNodes // add the node to the list of examined nodes
            let nodesToExamine = nodesToExamine.Tail // remove the node from the list of active nodes

            if (node.isGoal) then 
                node.print
                raise(SolutionWasFound(node))
        
            // Get the children of node and remove nodes that already exist in openNodes or closedNodes
            let nodes =  
                node.getChildren 
                |> List.filter(fun t -> not (List.exists(fun e -> t.equalTo e ) nodesToExamine )) 
                |> List.filter(fun t -> not (List.exists(fun e -> t.equalTo e ) closedNodes  ))

            // add these nodes to the end of openNodes
            // add thse to the begining of openNodes to use bredth first search
            internalSolve (nodes @ nodesToExamine)

        internalSolve openNodes


Program.fs:
module Program
open DataStructure
open Solver

//We are throwing different kind of exceptions to handle failure and success.
//Todo: Do not use exceptions lol

let s = new Solver()
try
    let res = s.solve (new Node(new SodukoProblem(1, 0, 0, 0, 0, 0, 0, 0, 0) ))
    res |> ignore
with
    | :? NoSolutionFound -> printfn "Did not find solution"
    | :? SolutionWasFound as found -> printfn "%O" (found.ToString())

Result:
1; 2; 3; 4; 5; 6; 7; 8; 9;

Comments