Click here to Skip to main content
15,886,362 members
Articles / Artificial Intelligence

Sudoku using Microsoft Solver Foundation

Rate me:
Please Sign up or sign in to vote.
4.85/5 (36 votes)
26 May 2014CPOL6 min read 84.6K   2.2K   112  
An example of how to use Microsoft Solver Foundation on a constraint satisfaction problem.
using Microsoft.SolverFoundation.Services;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Configuration;

namespace Sudoku
{
	public static class SudokuProblem
	{
		private static List<int> problem = new List<int>();
		private static List<int> solution = new List<int>();
		private static int hints = Properties.Settings.Default.Setting;

		public static bool IsSolved(List<int> possibleSolution)
		{
			if (possibleSolution == null)
			{
				return false;
			}

			for (int i = 0; i < possibleSolution.Count; i++)
			{
				if (possibleSolution[i] != solution[i])
				{
					return false;
				}
			}
			return true;
		}

		public static void GenerateSudoku()
		{
			SolverContext context = SolverContext.GetContext();
			Model model = context.CreateModel();

			List<Decision> decisionList = DecisionFactory.BuildDecisions(Grid.GetAllSquares());
			model.AddDecisions(decisionList.ToArray());

			// Add 27 constraints to model
			for (int j = 0; j < 9; j++)
			{
				model.AddConstraints("constraint_" + j,
						Model.AllDifferent(getDecision(decisionList, Grid.GetRow(j))),
						Model.AllDifferent(getDecision(decisionList, Grid.GetColumn(j))),
						Model.AllDifferent(getDecision(decisionList, Grid.GetRegion(j)))
				);
			}

			// Add seeds to model
			List<int> seedValues = Utils.GetUniqueRandomNumbers(1, 10, 9);
			for (int i = 0; i < 9; i++)
			{
				model.AddConstraints("seed_" + i.ToString(), decisionList[i] == seedValues[i]);
			}

			context.Solve(new ConstraintProgrammingDirective());
			solution = ConvertDecicionsToIntegers(decisionList);
		}

		public static void GenerateProblem()
		{
			GenerateSudoku();
			HideNumbers();
		}

		public static List<int> GetSolution()
		{
			return solution;
		}

		public static List<int> GetProblem()
		{
			return problem;
		}

		private static List<int> ConvertDecicionsToIntegers(List<Decision> decisionList)
		{
			List<int> results = new List<int>();
			foreach (Decision decision in decisionList)
			{
				results.Add(Convert.ToInt32(decision.ToString()));
			}
			return results;
		}

		private static Term[] getDecision(List<Decision> decisionList, List<int> indexes)
		{
			Term[] results = new Term[9];
			int i = 0;
			foreach (int index in indexes)
			{
				results[i] = (decisionList[index]);
				i++;
			}
			return results;
		}

		private static void HideNumbers()
		{
			List<int> toHide = Utils.GetUniqueRandomNumbers(0, Constants.BoardSize, Constants.BoardSize - hints);

			// Initialize problem to solution
			problem = new List<int>();
			problem.AddRange(solution);

			foreach (int hideMe in toHide)
			{
				problem[hideMe] = Constants.PlaceHolder;
			}
		}

		public static bool HasUniqueSolution()
		{
			SolverContext context = SolverContext.GetContext();
			context.ClearModel();
			Model model = context.CreateModel();

			List<Decision> decisionList = DecisionFactory.BuildDecisions(Grid.GetAllSquares());
			model.AddDecisions(decisionList.ToArray());

			// Add 27 constraints to model
			for (int j = 0; j < 9; j++)
			{
				model.AddConstraints("constraint_" + j,
						Model.AllDifferent(getDecision(decisionList, Grid.GetRow(j))),
						Model.AllDifferent(getDecision(decisionList, Grid.GetColumn(j))),
						Model.AllDifferent(getDecision(decisionList, Grid.GetRegion(j)))
				);
			}

			// Add all hints as constraints
			for (int i = 0; i < problem.Count; i++)
			{
				if (problem[i] != 0)
				{
					// This is a hint
					model.AddConstraints("hint_" + i.ToString(), decisionList[i] == problem[i]);
				}
			}

			List<DecisionBinding> decisionBindings = new List<DecisionBinding>();
			for (int i = 0; i < problem.Count; i++)
			{
				if (problem[i] == 0) // This is hidden square
				{
					DecisionBinding binding = decisionList[i].CreateBinding();
					decisionBindings.Add(binding);
				}
			}
			context.FindAllowedValues(decisionBindings);
			foreach (DecisionBinding decisionBinding in decisionBindings)
			{
				if (decisionBinding.Int32FeasibleValues.ToList().Count > 1)
				{
					
					return false;
				}
			}
			return true;
		}
	}
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

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


Written By
Code Rain
South Africa South Africa
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions