Backtracking is a general algorithm for finding all solutions to a constraint satisfaction problem. It builds candidates incrementally and abandons a candidate as soon as it determines the candidate cannot lead to a valid solution. The N-Queens problem asks: place N queens on an N×N chessboard so that no queen can attack another — no two queens share the same row, column, or diagonal.
Safety Check
Before placing a queen, verify that no existing queen occupies the same column or either diagonal above the current row:
// Returns true if placing a queen at (row, column) is safe.
// Checks the column above and both diagonals.
private bool IsSafe(char[,] board, int row, int column)
{
// Same column — check all rows above
for (int i = 0; i < row; i++)
if (board[i, column] == 'Q') return false;
// Top-left diagonal (\)
for (int i = row, j = column; i >= 0 && j >= 0; i--, j--)
if (board[i, j] == 'Q') return false;
// Top-right diagonal (/)
for (int i = row, j = column; i >= 0 && j < Size; i--, j++)
if (board[i, j] == 'Q') return false;
return true;
}Recursive Backtracking
Try every column in the current row. A safe placement recurses to the next row; when all N rows are filled a complete solution is saved. Backtracking resets the cell and tries the next column:
// Recursive backtracking — try every column in the current row.
// If a placement is safe, place the queen and recurse to the next row.
// When all rows are filled, record the board as a solution.
private void Solve(char[,] board, int row, int column)
{
if (column == 0 && row == Size)
{
Solutions.Add(CloneBoard(board));
return;
}
for (int i = 0; i < Size; i++)
{
if (IsSafe(board, row, i))
{
board[row, i] = 'Q';
Solve(CloneBoard(board), row + 1, 0);
board[row, i] = '-'; // backtrack
}
}
}Complete Solution
The NQueens class collects every valid board state in Solutions and provides a pretty-printer. Queens are represented as 'Q' and empty squares as '-':
public class NQueens
{
public int Size { get; }
public List<char[,]> Solutions { get; } = new List<char[,]>();
public int SolutionsCount => Solutions.Count;
public NQueens(int size) => Size = size;
public void SolveNQueens()
{
char[,] board = new char[Size, Size];
for (int i = 0; i < Size; i++)
for (int j = 0; j < Size; j++)
board[i, j] = '-';
Solve(board, 0, 0);
}
public void PrintSolution(int index)
{
var sb = new StringBuilder();
for (int i = 0; i < Size; i++)
{
for (int j = 0; j < Size; j++)
sb.Append(Solutions[index][i, j]).Append(' ');
sb.AppendLine();
}
Console.Write(sb);
}
private bool IsSafe(char[,] board, int row, int col)
{
for (int i = 0; i < row; i++)
if (board[i, col] == 'Q') return false;
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i, j] == 'Q') return false;
for (int i = row, j = col; i >= 0 && j < Size; i--, j++)
if (board[i, j] == 'Q') return false;
return true;
}
private char[,] CloneBoard(char[,] board)
{
var copy = new char[Size, Size];
for (int i = 0; i < Size; i++)
for (int j = 0; j < Size; j++)
copy[i, j] = board[i, j];
return copy;
}
private void Solve(char[,] board, int row, int col)
{
if (col == 0 && row == Size) { Solutions.Add(CloneBoard(board)); return; }
for (int i = 0; i < Size; i++)
{
if (IsSafe(board, row, i))
{
board[row, i] = 'Q';
Solve(CloneBoard(board), row + 1, 0);
board[row, i] = '-';
}
}
}
}Usage
An 8-Queens problem has 92 distinct solutions:
NQueens nQueens = new NQueens(8);
nQueens.SolveNQueens();
Console.WriteLine(quot;Solutions: {nQueens.SolutionsCount}"); // 92
nQueens.PrintSolution(0); // first solution
nQueens.PrintSolution(10); // eleventh solution