Post date: Feb 18, 2012 4:51:58 PM
Full Source: http://code.google.com/p/peter-henell-f-sharp-sudoku-solver/source/browse/#git%2FSearchTrees
As a small adjustment in hope of getting better performance I change the data container to Arrays instead of lists.
The reason for doing this is that the functions on Lists are of high complexity.
The nth-function for the Lists are actually of O(n) complexity which is a huge deal. From my understanding the index access of an array is of O(1) complexity.
Check the implementation of the List and Array classes on your local computer in these files:
C:\Program Files (x86)\FSharp-2.0.0.0\source\fsharp\FSharp.Core\list.fs
C:\Program Files (x86)\FSharp-2.0.0.0\source\fsharp\FSharp.Core\array.fs
After changing to Arrays i decided to try out the Parallel tasks library to try to use more of my cores.
I identified only a few places that i directly could benefit from running code in parallel.
The getChildren function of the SudokuNode class had two sets of calculations that i thought would be good candidates.
The first candidate is the part where we are gathering the row, column and regions to figure out what numbers are already taken.
We can easily get the row, column and region at the same time, and that's why it is a easy fix to make it parallel.
The second candidate is the part where we are creating the new child nodes based on the numbers we have found to be possible numbers.
Summary:
These small changes have made finding the solution for the Hard sudoku problem gone down from 1 minute to 15-20 seconds.
member this.getChildren = // find the index of a free spot to place our next number let freeSpot = content.findFreeSpot // get the row, column and region based on that index let (row, column, region) = content.indexToRCR freeSpot let p = Async.Parallel [ async { return content.getRow row } async { return content.getCol column } async { return content.getRegion region } ] |> Async.RunSynchronously |> Array.concat // Get all number between 1 and 9 that do not exists in the row nor column nor region let possible = (Set.ofArray [|1..9|]) - Set.ofArray( p ) let neww = Async.Parallel [for i in possible -> async { return new SudokuNode(replaceAt freeSpot i content.Board) } ] |> Async.RunSynchronously neww