Solve N-Queens Problem?

List<List<string>> SolveNQueens(int n)

List<List<string>> results = new List<List<string>>();

int[] board = new int[n]; // board[i] = column position of queen

in row i

Solve(0, board, results, n);

return results;

void Solve(int row, int[] board, List<List<string>> results, int n)

if (row == n)

results.Add(GenerateBoard(board, n));

return;

for (int col = 0; col < n; col++)

if (IsSafe(row, col, board))

board[row] = col;

Solve(row + 1, board, results, n);

bool IsSafe(int row, int col, int[] board)

for (int i = 0; i < row; i++)

Follow on:

if (board[i] == col || Math.Abs(board[i] - col) ==

Math.Abs(i - row))

return false;

return true;

List<string> GenerateBoard(int[] board, int n)

List<string> res = new List<string>();

for (int i = 0; i < n; i++)

char[] row = new char[n];

for (int j = 0; j < n; j++)

row[j] = '.';

row[board[i]] = 'Q';

res.Add(new string(row));

return res;

Explanation:

Backtracking places queens row by row while checking columns and diagonals.