This answer quotes ChatGPT
In this code, the Solve function calls the Backtrack function to search recursively for all solutions using the backtrack method. In the Backtrack function, we use some auxiliary arrays to keep track of which rows, columns, diagonals, and anti-diagonals have been used. During the search, we try to place the queen on one column of the board, and if we can, we recursively search the next column. When a legal solution is found, the counter count is increased by one.
using System;
namespace NQueensProblem
{
class Program
{
static void Main(string[] args)
{
int n, k;
while (true)
{
string[] input = Console.ReadLine().Split(' ');
n = int.Parse(input[0]);
k = int.Parse(input[1]);
if (n == -1 && k == -1) break;
char[][] board = new char[n][];
for (int i = 0; i < n; i++)
{
board[i] = Console.ReadLine().ToCharArray();
}
int count = Solve(board, k);
Console.WriteLine(count);
}
}
static int Solve(char[][] board, int k)
{
int n = board.Length;
bool[] rowUsed = new bool[n];
bool[] colUsed = new bool[n];
bool[] diagonalUsed = new bool[2 * n - 1];
bool[] antidiagonalUsed = new bool[2 * n - 1];
int count = 0;
Backtrack(board, k, 0, rowUsed, colUsed, diagonalUsed, antidiagonalUsed, ref count);
return count;
}
static void Backtrack(char[][] board, int k, int col, bool[] rowUsed, bool[] colUsed, bool[] diagonalUsed, bool[] antidiagonalUsed, ref int count)
{
if (k == 0)
{
count++;
return;
}
int n = board.Length;
for (int row = 0; row < n; row++)
{
if (board[row][col] == '#' && !rowUsed[row] && !colUsed[col] && !diagonalUsed[row + col] && !antidiagonalUsed[row - col + n - 1])
{
rowUsed[row] = true;
colUsed[col] = true;
diagonalUsed[row + col] = true;
antidiagonalUsed[row - col + n - 1] = true;
Backtrack(board, k - 1, col + 1, rowUsed, colUsed, diagonalUsed, antidiagonalUsed, ref count);
rowUsed[row] = false;
colUsed[col] = false;
diagonalUsed[row + col] = false;
antidiagonalUsed[row - col + n - 1] = false;
}
}
}
}
}