Creating a Sudoku Problem Solver using Microsoft Solver Foundation


Hi

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

Advertisements

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