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


About the Author

Question Info

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

Related Question

(语言-python)问题

当从"CustomerService"测试"createCustomer"方法时出现NullPointerException

python遍历循环前100条ip地址

Python安装失败

在cond->的哈希映射向量中Dissoc一个键

document.onkeypress = (e)在用vue实现监听扫描枪的时候发现onkeypress已经弃用了该如何

CPython脚本执行器不能在Pentaho Kettle上工作

disco diffusion本地化module出错

带有actions/setup-python的可重用GitHub动作工作流失败,因为它找不到requirements.txt

关于WifiManager.RSSI_CHANGED_ACTION