F# - Sudoku Solver using search trees Step two: The algorithm
Post date: Jan 29, 2012 12:03:28 AM
Full Source: http://code.google.com/p/peter-henell-f-sharp-sudoku-solver/source/browse/#git%2FSearchTrees
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 stringexception 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;