Creating a Sudoku Problem Solver using Microsoft Solver Foundation

Today we are we are going to be creating a Sudoku Problem Solving Application using Microsoft Solver Foundation. First step will be to download the assembly, this can be downloaded through the MSDN Code Gallery. All you need is the DLL only download but you can download the full installation if you want samples and other documentation as well.

Next we’ll start a new instance of visual studio and create a new Console Application. Now add a class to this console application called MySudokuSolver.cs. Add a reference to Microsoft Solver Foundation. Update you MySudokuSolver.cs code to look like below.

using Microsoft.SolverFoundation.Solvers;

namespace SudokuSolverSample
{
    internal class MySudokuSolver
    {
        private static CspTerm[] GetSlice(CspTerm[][] sudoku, 
            int Ra, int Rb, int Ca, int Cb)
        {
            CspTerm[] slice = new CspTerm[9];
            int i = 0;
            for (int row = Ra; row < Rb + 1; row++)
                for (int col = Ca; col < Cb + 1; col++)
                {
                    {
                        slice[i++] = sudoku[row][col];
                    }
                }
            return slice;
        }

        public static int[,] Solve(int[,] input)
        {
            int[,] result = new int[9, 9];
            ConstraintSystem S = ConstraintSystem.CreateSolver();
            CspDomain Z = S.CreateIntegerInterval(1, 9);
            CspTerm[][] sudoku = S.CreateVariableArray(Z, "cell", 9, 9);
            for (int row = 0; row < 9; row++)
            {
                for (int col = 0; col < 9; col++)
                {
                    if (input[row, col] > 0)
                    {
                        S.AddConstraints(S.Equal(input[row, col], sudoku[row][col]));
                    }
                }
                S.AddConstraints(S.Unequal(GetSlice(sudoku, row, row, 0, 8)));
            }
            for (int col = 0; col < 9; col++)
            {
                S.AddConstraints(S.Unequal(GetSlice(sudoku, 0, 8, col, col)));
            }
            for (int a = 0; a < 3; a++)
            {
                for (int b = 0; b < 3; b++)
                {
                    S.AddConstraints(S.Unequal(GetSlice(sudoku, 
                        a * 3, a * 3 + 2, b * 3, b * 3 + 2)));
                }
            }
            ConstraintSolverSolution soln = S.Solve();
            for (int row = 0; row < 9; row++)
            {
                for (int col = 0; col < 9; col++)
                {
                    object val = null;
                    soln.TryGetValue(sudoku[row][col], out val);
                    result[row, col] = (int)val;
                }
            }

            return result;
        }
    }
}

and lastly update your program.cs to look the below code (I’ve left a comented out blank input to make it easier to create new inputs)

using System;

namespace SudokuSolverSample
{
    class Program
    {
        static void Main(string[] args)
        {
            int[,] input = new int[,] {{6,0,0, 0,0,1, 4,0,0},
                                        {0,0,0, 0,3,0, 0,7,0},
                                        {1,0,0, 0,0,0, 0,0,3},

                                        {0,0,0, 0,0,0, 0,0,7},
                                        {5,0,0, 4,0,0, 9,0,0},
                                        {9,0,0, 0,0,7, 5,0,0},

                                        {0,3,0, 0,4,0, 0,9,0},
                                        {0,0,1, 0,2,0, 0,0,8},
                                        {0,0,0, 5,0,0, 0,0,0}};

            int[,] output = MySudokuSolver.Solve(input);

            for (int row = 0; row < 9; row++)
            {
                if ((row % 3) == 0) System.Console.WriteLine();
                System.Console.WriteLine("{0}{1}{2} {3}{4}{5} {6}{7}{8}", 
                    output[0, row], output[1, row], output[2, row], output[3, row], 
                    output[4, row], output[5, row], output[6, row], output[7, row], 
                    output[8, row]);
            }

            Console.ReadLine();

        }
    }
}

That’s all you need. Hit Run and see the Sudoku Problem solved. I tried finding the hardest problems I could find to try and break this code but nothing could do it. If you find something let me know, will be interesting to see if there is a solution that is un solveable.

A running version of this can be found on the application demo site here.

Hope this not only helps solve those incredibly hard Sudoku puzzles but lets you see a brief bit of the power and speed of Microsoft Solver Foundation. Information on Versions and what each version supports can be found on the MSDN Website here.

Downloads

• SudokuSolverSample.zip