Solving Sudoku with F# and Solver Foundation

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"
;;
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)
//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

//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"```