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"
#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"
Advertisements

2 thoughts on “Solving Sudoku with F# and Solver Foundation

  1. Pingback: Constraint Programming « Code Contemplation

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s