0
Follow
0
View

# On the chessboard problem, no error can be found

dafa1680 注册会员
2023-02-27 21:29

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++)
{
}

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;
}
}
}
}
}

``````

isabel333 注册会员

Publish Time
2023-02-27 21:29
Update Time
2023-02-27 21:29