Here is a simple Sudoku solver that uses F# and Microsoft Solver Foundation’s Constraint Programming solver.

The 9×9 matrix of a Sudoku puzzle is represented as a list of 81 cells. Cells can have values 0-9. Zeros represent blank cells.

We first create a Solver Foundation ‘model’ object which we will use to model the Sudoku puzzle.

Each value of the puzzle matrix is converted to a Solver Foundation ‘term’ object. Zeros are treated as “decision variables” and are converted to variable terms that can take on integer values from 1-9. The rest are converted to constant terms.

Having defined the terms, we can now define relationships between the terms using the Solver Foundation ‘language’ of operators.

Next we take this list of 81 terms and organize it by binning each cell into its row, column and group (of local 9 cells) in line with the Sudoku puzzle matrix. We use some modulo arithmetic magic to make this happen.

Now that we know the cells in each row, column and group we can use this information to add “all different” constraints for each row, column and group. We use the ‘AllDifferent’ Solver Foundation operator to create the constraints. We add all the constraints to the model object.

Our puzzle is now modeled mathematically and we let loose Solver Foundation on it to solve it for us.

Below is the complete listing of the F# code (just update the paths at the top to correctly reference external resources before using).

Or you can get the source from GitHub here.

#r @"C:\ws\ReferenceAssemblies\Solver30\Microsoft.Solver.Foundation.dll" #load @"C:\Users\Fai\Documents\Microsoft Solver Foundation\Samples\FSharp\SfsMeasures\SfsWrapper.fs" ;; open Microsoft.SolverFoundation.Services open Microsoft.SolverFoundation.SfsWrapper ;; let sudokuPuzzle = //9x9 matrix as list of 81 cells //use 0 for blank cell [0; 5; 0; 4; 8; 1; 0; 9; 0; 8; 0; 0; 0; 0; 0; 0; 0; 2; 0; 0; 1; 0; 0; 0; 7; 0; 0; 3; 2; 0; 9; 0; 5; 0; 1; 6; 0; 0; 0; 0; 3; 0; 0; 0; 0; 6; 8; 0; 2; 0; 7; 0; 3; 5; 0; 0; 3; 0; 0; 0; 4; 0; 0; 5; 0; 0; 0; 0; 0; 0; 0; 1; 0; 7; 0; 3; 2; 4; 0; 6; 0] //create model let ctx = SolverContext.GetContext() ctx.ClearModel() let mdl = SfsModel(ctx) //map puzzle cells to model terms let p2 = sudokuPuzzle |> List.map(fun cell -> match cell with | 0 -> mdl.CreateIntRangeVariable(1, 9) :> SfsIntTerm<1> //variable term if 0 | x when x >= 1 && x <= 9 -> mdl.CreateIntConstant(cell) //constant term otherwise | _ -> failwith "cell values should be 0 to 9") //we bin each cell 3 ways; the row, col and group it belongs to let binnedCells = p2 |> List.mapi (fun i cell -> let row = i / 9 let col = i % 9 let group = (row / 3, col / 3) (row, col, group, cell)) //function to add 'all different' constraints for each group //(the grouping function is provided as input) let addConstraints groupByFunction aList = //function to extract just the cell term from a tuple let f2 = fun (row,col,group,cell:SfsIntTerm<1>) -> cell aList |> Seq.groupBy groupByFunction |> Seq.map (fun (_,xs) -> xs |> Seq.map f2 |> Seq.toArray |> mdl.AllDifferent) |> Seq.toArray |> mdl.AddConstraints //for each row, col and group we add the 'all different' constraints let rowConstraints = binnedCells |> addConstraints (fun (row,_,_,_) -> row) let colConstrains = binnedCells |> addConstraints (fun (_,col,_,_) -> col) let groupConstraints = binnedCells |> addConstraints (fun (_,_,group,_) -> group) ;; let sol = mdl.Solve(SolverDirectives.ConstraintProgramming) if sol.Quality = SolverQuality.Feasible then printfn "Solution found:" printfn "%A" p2 else printfn "No solution found"

Pingback: Constraint Programming « Code Contemplation

Nice work!