Click here to Skip to main content
Click here to Skip to main content

Tagged as

Go to top

Creating a Sudoku Problem Solver using Microsoft Solver Foundation

, 14 May 2013
Rate this:
Please Sign up or sign in to vote.
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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Gordon W Beeming
Software Developer Derivco
South Africa South Africa
Gordon Beeming is a Software Developer at Derivco in the sunny city of Durban, South Africa. He spends most his time hacking away at the keyboard in Visual Studio or with his family relaxing. He is a Visual Studio ALM Rangers, Visual Studio ALM MVP and Friend of Red Gate. His blog is at 31og.com and you can follow him on Twitter at twitter.com/gordonbeeming
 
http://31og.com
Follow on   Twitter   Google+   LinkedIn

Comments and Discussions

 
GeneralMy vote of 5 PinmemberArt Tres23-Jun-13 10:27 
QuestionHelp PinmemberMember 1005325214-May-13 21:06 
AnswerRe: Help PinprofessionalGordon W Beeming14-May-13 22:04 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.140926.1 | Last Updated 14 May 2013
Article Copyright 2013 by Gordon W Beeming
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid