For a while, I’ve wanted to build a little C# library to solve Sudoku puzzles. Something that would take the known values and figure out the values for the empty squares.
Since I had some time today, I went ahead and wrote it. Here it is, for any of you who want to use it.
General library information
For the 9 by 9 grid, I’ve numbered the rows and columns from 1 to 9. For the rows, 1 is the top row, 9 is the bottom. For the columns, 1 is the leftmost column, 9 is the rightmost column.
The Sudoku solver classes
This library only consists of two classes – the Square class (to hold information about each individual square) and the Board class (which holds the collection of Square objects and is where the UI would do most of its interaction).
I’ll also show the unit test class I created, to test if it can find all the values for the empty squares.
Square.cs
The Square class is mainly a “dumb bucket of values”. It only holds values for later retrieval and modification. The only calculation is does it to determine which 3×3 “block” a particular square is in.
When a Square object is instantiated, it sets the Row and Column property values (from the passed-in parameter values) and populates the PotentialValues list with the values from 1 through 9 (since the square could potentially be any one of those values at this point).
Notice that many of the properties have private setters, since an app should never have a reason to change those values. Also, many of the properties are “internal” – including the constructor. That’s because they should only ever be used by the Board object.
using System.Collections.Generic;
namespace SudokuEngine
{
public class Square
{
private readonly List<int> _potentialValues = new List<int>() {1, 2, 3, 4, 5, 6, 7, 8, 9};
internal enum Blocks
{
UpperLeft,
UpperMiddle,
UpperRight,
MiddleLeft,
Middle,
MiddleRight,
LowerLeft,
LowerMiddle,
LowerRight
}
public int Row { get; private set; }
public int Column { get; private set; }
internal Blocks Block
{
get
{
if(Row < 4)
{
if(Column < 4)
{
return Blocks.UpperLeft;
}
return Column < 7 ? Blocks.UpperMiddle : Blocks.UpperRight;
}
if(Row < 7)
{
if(Column < 4)
{
return Blocks.MiddleLeft;
}
return Column < 7 ? Blocks.Middle : Blocks.MiddleRight;
}
if(Column < 4)
{
return Blocks.LowerLeft;
}
return Column < 7 ? Blocks.LowerMiddle : Blocks.LowerRight;
}
}
public bool IsSolved { get { return Value != null; } }
public int? Value { get; set; }
internal List<int> PotentialValues { get; private set; }
internal Square(int row, int column)
{
Row = row;
Column = column;
PotentialValues = _potentialValues;
}
}
}
Board.cs
In the Board class’ constructor, the Squares list is populated with two small loops that give us the 81 squares (9 rows, with 9 columns).
The “brains” of this library is the SetSquareValue() method. When you call set a square’s value through this method, it will remove that value from the PotentialValues list for all other squares in the same row, column, or 3×3 block.
Then, it will see if there are any squares that don’t have a value, but only have one remaining PotentialValue. If so, it will set that square’s value to its only possible value, using the same method. This is a “recursive function” – it can possibly end up calling itself for another square in the list.
This happens every time you set a square. So, there is no “Solve()” method. The puzzle automatically gets solved as you add the known square values.
using System.Collections.Generic;
using System.Linq;
namespace SudokuEngine
{
public class Board
{
public List<Square> Squares { get; private set; }
public Board()
{
Squares = new List<Square>();
for(int row = 1; row < 10; row++)
{
for(int column = 1; column < 10; column++)
{
Squares.Add(new Square(row, column));
}
}
}
public void SetSquareValue(int row, int column, int value)
{
Square activeSquare = Squares.Single(x => (x.Row == row) && (x.Column == column));
activeSquare.Value = value;
// Remove value from other squares in the same row
foreach(Square square in Squares.Where(s => !s.IsSolved && (s.Row == row)))
{
square.PotentialValues.Remove(value);
}
// Remove value from other squares in the same column
foreach(Square square in Squares.Where(s => !s.IsSolved && (s.Column == column)))
{
square.PotentialValues.Remove(value);
}
// Remove value from other squares in the same quadrant
foreach(Square square in Squares.Where(s => !s.IsSolved && (s.Block == activeSquare.Block)))
{
square.PotentialValues.Remove(value);
}
// Set the Value for any square that only have one remaining PotentialValue
foreach(Square square in Squares.Where(s => !s.IsSolved && (s.PotentialValues.Count == 1)))
{
SetSquareValue(square.Row, square.Column, square.PotentialValues[0]);
}
}
}
}
TestBoard.cs
This is a unit test that populates a Sudoku puzzle with values in 35 squares. Those were enough to let the program determine the values for the remaining 46 squares.
I got these values from a Sudoku game I found on the web.
At the end, you’ll see that the number of remaining unsolved squares is zero (in the Assertion at the end of the test).
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using SudokuEngine;
namespace TestSudokuEngine
{
[TestClass]
public class TestBoard
{
[TestMethod]
public void Test_Game_01()
{
Board board = new Board();
board.SetSquareValue(1, 3, 4);
board.SetSquareValue(1, 5, 5);
board.SetSquareValue(1, 9, 2);
board.SetSquareValue(2, 1, 1);
board.SetSquareValue(2, 4, 2);
board.SetSquareValue(3, 1, 7);
board.SetSquareValue(3, 3, 5);
board.SetSquareValue(3, 4, 1);
board.SetSquareValue(3, 6, 8);
board.SetSquareValue(3, 7, 9);
board.SetSquareValue(4, 1, 3);
board.SetSquareValue(4, 2, 5);
board.SetSquareValue(4, 3, 2);
board.SetSquareValue(4, 6, 1);
board.SetSquareValue(4, 7, 7);
board.SetSquareValue(4, 8, 8);
board.SetSquareValue(5, 2, 6);
board.SetSquareValue(5, 5, 7);
board.SetSquareValue(5, 8, 5);
board.SetSquareValue(6, 2, 8);
board.SetSquareValue(6, 3, 7);
board.SetSquareValue(6, 4, 6);
board.SetSquareValue(6, 7, 4);
board.SetSquareValue(6, 8, 3);
board.SetSquareValue(6, 9, 1);
board.SetSquareValue(7, 3, 6);
board.SetSquareValue(7, 4, 3);
board.SetSquareValue(7, 6, 7);
board.SetSquareValue(7, 7, 5);
board.SetSquareValue(7, 9, 8);
board.SetSquareValue(8, 6, 2);
board.SetSquareValue(8, 9, 4);
board.SetSquareValue(9, 1, 8);
board.SetSquareValue(9, 5, 1);
board.SetSquareValue(9, 7, 3);
Assert.AreEqual(0, board.Squares.Count(x => !x.IsSolved));
}
}
}
Summary
This is one simple way to write some C# code that will solve a Sudoku puzzle. There are certainly other ways to write it, and this might give you an idea of how to write your own Sudoku engine.
You should be able to connect this to a UI, either in a desktop app or a web app, without too much work.
7 Comments