Sudoku Solver - Backtracking Algorithm

I coded this a few weeks ago, so here it is. A simple, neat and highly customizable Sudoku solver (with a simple board) in C# based on the Backtracking algorithm.

In action:

Sudoku solver in C#

And here's the source code

• SudukoBoard.cs:

  // SudukoBoard.cs public class SudokuBoard : GroupBox { public sealed class SudokuCell : TextBox { public int X { get; private set; } public int Y { get; private set; } /// 
   /// Thread-safe Get/Set Text. /// 
   public string Value { get { string text = string.Empty; Invoke(new MethodInvoker(delegate { text = Text; })); return text; } set { Invoke(new MethodInvoker(delegate { Text = value; })); } } // Ctor. public SudokuCell(int x, int y, int width, int height) { X = x; Y = y; Width = width; Height = height; TextAlign = HorizontalAlignment.Center; Font = new Font("Verdana", 8, FontStyle.Regular); } // Only digits (except 0) are allowed. protected override void OnKeyPress(KeyPressEventArgs e) { if (char.IsWhiteSpace(e.KeyChar) || (!char.IsDigit(e.KeyChar) && e.KeyChar != (char) 8) || e.KeyChar == (char) 48) e.Handled = true; base.OnKeyPress(e); } } // An array representing the board. private readonly SudokuCell[,] _cell; private readonly int _cellWidth, _cellHeight; // Current board values. All operations/verifications are performed on this array. public readonly string[,] CurrBoardValues; public SudokuCell this[int x, int y] { get { return _cell[x, y]; } } // Ctor. public SudokuBoard(int cellWidth, int cellHeight) { _cellWidth = cellHeight; _cellHeight = cellHeight; Width = cellWidth * 9 + 20; Height = cellHeight * 9 + 28; _cell = new SudokuCell[9, 9]; CurrBoardValues = new string[9, 9]; CreateBoardControl(); } // Creates the actual sudoku board control (an array of SudokuCell in a GroupBox.) private void CreateBoardControl() { int extraSpaceX, extraSpaceY = 0; for (int y = 0; y < 9; y++) { extraSpaceX = 0; if (y != 0 && y % 3 == 0) extraSpaceY += 3; for (int x = 0; x < 9; x++) { if (x != 0 && x % 3 == 0) extraSpaceX += 3; _cell[x, y] = new SudokuCell(x, y, _cellHeight, _cellHeight) { MaxLength = 1, Location = new Point(Location.X + 7 + x * _cellWidth + extraSpaceX, Location.Y + 15 + y * _cellHeight + extraSpaceY) }; _cell[x, y].TextChanged += OnSudokuCellTextChanged; Controls.Add(_cell[x, y]); } } } private void OnSudokuCellTextChanged(object sender, EventArgs eventArgs) { var cell = (SudokuCell) sender; TryMove(cell); } #region Public methods public void ClearBoard() { for (int y = 0; y < 9; y++) { for (int x = 0; x < 9; x++) { _cell[x, y].Value = CurrBoardValues[x, y] = string.Empty; } } } public void UpdateBoard() { for (int y = 0; y < 9; y++) { for (int x = 0; x < 9; x++) { _cell[x, y].Value = CurrBoardValues[x, y]; } } } public bool TryMove(SudokuCell cell) { return TryMove(cell.X, cell.Y, cell.Value); } public bool TryMove(int x, int y, string value) { CurrBoardValues[x, y] = value; /* !IsMoveAllowedInRow(x, y, value) || !IsMoveAllowedInColumn(x, y, value) || !IsMoveAllowedInCurrentBox(x, y, value) */ if (!IsMoveAllowed(x, y, value)) { _cell[x, y].Value = string.Empty; CurrBoardValues[x, y] = string.Empty; return false; } return true; } #endregion #region Rules public bool IsMoveAllowed(int x, int y, string value) { return IsMoveAllowedInRow(x, y, value) && IsMoveAllowedInColumn(x, y, value) && IsMoveAllowedInCurrentBox(x, y, value); } private bool IsMoveAllowedInRow(int x, int y, string value) { for (int i = 0; i < 9; i++) { if (i == x) continue; if (CurrBoardValues[i, y] == value) return false; } return true; } private bool IsMoveAllowedInColumn(int x, int y, string value) { for (int i = 0; i < 9; i++) { if (i == y) continue; if (CurrBoardValues[x, i] == value) return false; } return true; } private bool IsMoveAllowedInCurrentBox(int x, int y, string value) { int boxX = 0, boxY = 0; if (x > 5) boxX = 6; else if (x > 2) boxX = 3; if (y > 5) boxY = 6; else if (y > 2) boxY = 3; for (int j = 0; j < 3; j++) { for (int i = 0; i < 3; i++) { if (boxX + i == x && boxY + j == y) continue; if (CurrBoardValues[boxX + i, boxY + j] == value) return false; } } return true; } #endregion } 

• SudokuSolver.cs:

  // SudokuSolver.cs public class SudokuSolver { private int _numOfTrials; private readonly SudokuBoard _board; private readonly AutoResetEvent _solvedEvent; public SudokuSolver(SudokuBoard board) { _board = board; _numOfTrials = 0; _solvedEvent = new AutoResetEvent(false); } #region Solve public void Solve() { var thread = new Thread(StartBacktrackSolver) { IsBackground = true }; thread.Start(); // Waiting for the solver thread to solve. _solvedEvent.WaitOne(); _board.UpdateBoard(); OnGameCompleted(_numOfTrials); _numOfTrials = 0; } private void StartBacktrackSolver() { BacktrackSolver(0, 0); _solvedEvent.Set(); } // Backtrack solving algorithm. private bool BacktrackSolver(int x, int y) { if (x == 9) { if (y == 8) return true; // game solved! x = 0; y++; } // pre-solved value. if (!string.IsNullOrEmpty(_board.CurrBoardValues[x, y])) { return BacktrackSolver(x + 1, y); } // Trying every possible (1 - 9) value on each cell. for (int i = 1; i < 10; i++) { if (_board.IsMoveAllowed(x, y, i.ToString())) { _numOfTrials++; _board.CurrBoardValues[x, y] = i.ToString(); // Moving on to the next cell. if (BacktrackSolver(x + 1, y)) return true; // game solved. // DEAD END reached. } } // DEAD END (no move was possible!) _board.CurrBoardValues[x, y] = string.Empty; return false; } #endregion public delegate void GameCompletedHandler(int numOfTrials); public event GameCompletedHandler GameCompleted; private void OnGameCompleted(int numOfTrials) { if (GameCompleted != null) GameCompleted(numOfTrials); } }

• Usage: http://pastebin.com/AK213QTN

Wanna try it? Here's just the executable:
http://www.mediafire.com/?umzad2b7jsgyjcg

Found a bug or something? Let me know.
Enjoy! ;)