Sudoku Solver Class & Demo Code

[AceInfinity]

Here's something I've attempted earlier today. I can solve most easy to intermediate puzzles, but the harder ones I sometimes get caught...

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using System.Windows.Forms;

namespace Sudoku_Brain
{

	#region Grid Diagram
	//    0 1 2 3 4 5 6 7 8
	//    -----------------
	// 0 |     |     |     |
	// 1 |  0  |  1  |  2  |
	// 2 |     |     |     |
	//   |-----------------|
	// 3 |     |     |     |
	// 4 |  3  |  4  |  5  |
	// 5 |     |     |     |
	//   |-----------------|
	// 6 |     |     |     |
	// 7 |  6  |  7  |  8  |
	// 8 |     |     |     |
	//    -----------------
	#endregion

	#region SudokuSolver Class
	class SudokuSolver
	{
		#region Fields & Properties
		private int _AssignedRows = 0;
		private int[,] _Grid = new int[9, 9];

		public int[,] GetResult
		{
			get { return _Grid; }
		}

		public bool Solved
		{
			get
			{
				foreach (int i in _Grid)
					if (i == 0) return false;
				return true;
			}
		}

		private int _MaxTries = 10000;
		public int MaxTries
		{
			get { return _MaxTries; }
			set { _MaxTries = value; }
		}
		#endregion

		#region Grid Assignment
		public void AssignRow(string values)
		{
			if (_AssignedRows != 9)
			{
				for (int i = 0; i < 9; i++)
					_Grid[_AssignedRows, i] = int.Parse(values[i].ToString());
				_AssignedRows++;
			}
			else
			{
				MessageBox.Show("You can only assign 9 rows to the grid.", "Too many rows", MessageBoxButtons.OK, MessageBoxIcon.Information);
			}
		}
		#endregion

		#region Solve Puzzle
		public bool TrySolve()
		{
			if (_AssignedRows < 9)
			{
				MessageBox.Show("You have not assigned all rows to the grid yet.", "Missing Row(s)", MessageBoxButtons.OK, MessageBoxIcon.Information);
				return false;
			}

			List<int> obj;
			int runs = 0;
			int count = 0;

			while (!Solved)
			{
				for (int row = 0; row < 9; row++)
				{
					for (int col = 0; col < 9; col++)
					{
						if (_Grid[row, col] == 0)
						{
							obj = new List<int>(GetColumn(col)
								.Union(GetRow(row))
								.Union(GetTile(row, col)))
								.Distinct().ToList();
							obj.Remove(0);

							if (obj.Count == 8 || runs > 10)
							{
								if (runs > 10) runs = 0;
								int x = Enumerable.Range(1, 9).FirstOrDefault(i => !obj.Contains(i));
								_Grid[row, col] = x;
							}
						}
					}
				}
				runs++;
				count++;

				if (count > MaxTries) return false;
			}

			return true;

		}
		#endregion

		#region Grid Regions
		private int[] GetTile(int x, int y)
		{
			int[] tile = new int[9];

			int tileIndex = (x / 3) + (y / 3 * 3);
			int tileRow = tileIndex / 3 * 3;
			int tileColumn = tileIndex % 3 * 3;
			int pos = 0;

			for (int c = tileColumn; c < tileColumn + 3; c++)
			{
				for (int r = tileRow; r < tileRow + 3; r++)
				{
					tile[pos++] = _Grid[c, r];
				}
			}

			return tile;
		}

		private int[] GetRow(int rowIndex)
		{
			int[] row = new int[9];
			for (int i = 0; i < 9; i++)
				row[i] = _Grid[rowIndex, i];
			return row;
		}

		private int[] GetColumn(int colIndex)
		{
			int[] col = new int[9];
			for (int i = 0; i < 9; i++)
				col[i] = _Grid[i, colIndex];
			return col;
		}
		#endregion
	}
	#endregion
}

I'd have an idea on how to solve the more difficult ones... but I was really just fooling around on this lol. Not sure if I want to spend the time towards making a more advanced Sudoku solving class. At points within the game that can't be determined and guaranteed through logic, you'd have to guess... Then keep some kind of log on the move that forced you to guess (snapshot of some sort of the numbers on the grid before you "guessed"), then up until you find out you can't make another move, backtrack to that point in time to try the other number that you haven't tried, or one of the other numbers. Process of elimination and validation.

It'd take some time, but I wanted to give it a try anyways. This is a GREAT project for people who are afraid of numbers :lol:

It took some time to wrap my brain around how to determine missing numbers on both axis', including 1 of the 9 box regions within the game board grid.

DEMO Code:

SudokuSolver solver = new SudokuSolver();

/* Puzzle that can be solved! */
solver.AssignRow("600300080");
solver.AssignRow("009400030");
solver.AssignRow("004500920");
solver.AssignRow("050840700");
solver.AssignRow("040006050");
solver.AssignRow("002050060");
solver.AssignRow("071004300");
solver.AssignRow("020007600");
solver.AssignRow("060005008");

/* Puzzle that can't be solved :( */
//solver.AssignRow("003000080");
//solver.AssignRow("008070400");
//solver.AssignRow("020600000");
//solver.AssignRow("050003001");
//solver.AssignRow("090000070");
//solver.AssignRow("600100050");
//solver.AssignRow("000007030");
//solver.AssignRow("004020800");
//solver.AssignRow("080000600");

if (solver.TrySolve())
{
	int[,] result = solver.GetResult;
	for (int row = 0; row < 9; row++)
	{
		for (int col = 0; col < 9; col++)
		{
			Console.Write(result[row, col]);
		}
		Console.Write('\n');
	}
}
else
{
	MessageBox.Show("Could not solve this puzzle... :(", "Couldn't solve", MessageBoxButtons.OK, MessageBoxIcon.Information);
}

edit: Btw, why did you guys remove the syntax highlighting code boxes? :confused2:

 

[writhziden]

I made a Sudoku solver in MATLAB at one point. The random guess portion of it was the slowest part (probably because I did not vectorize it for easy use in MATLAB). I could solve very hard puzzles within a few minutes.

edit: Btw, why did you guys remove the syntax highlighting code boxes? :confused2:

It was found to slow down site and page load times. We'll probably bring it back in a slimmer version. You should make requests for which languages you would like to see supported.

 

[AceInfinity]

All of them lol. A few that I would like to see though:

-Batch
-C#
-VB.NET
-Perl
-PowerShell
-C++
-Java & JavaScript
-PHP

Others are probably less common, if some in this list already aren't. Although I may be missing a few, this was just spur of the moment brainstorming for a quick post.