N-Rooks 解决方案回溯数量

Question

这些方法应该可以计算出任何数量的车在非进攻布局中可以在棋盘上进行的布局。我知道我一定在这里遗漏了一些愚蠢的东西。帮帮我。出于某种原因，我返回的解决方案计数已关闭，即使使用打印语句找到了 6 个解决方案......我已经尝试打印数组，在找到解决方案时打印......但我找不到任何有用的东西。

编辑*：用户界面不完整。忽略其中的低级错误。更关心我从 findnumsolution() 方法中得到的不正确结果。我试过直接通过构造函数传递值，但它仍然给我错误的答案。 3x3 棋盘，有 3 块，returns 5，4x4 有 4 returns 13.

编辑**：清理了不相关的代码。

NRooks(int board[8][8], int n, int k)
{
    numRooks = n;
    boardSize = k;
    numSolutions = 0;
    for(int i = 0; i < 8; i++)
        for(int j = 0; j < 8; j++)
            board[i][j] = 0;
    numSolutions = findNumSolutions(board, 0, numRooks);
}

bool canPlace(int col, int row, int board[8][8])
{
    for(int i = col-1; i >= 0; i--){
        if(board[i][row] == 1){
            return false;
        }
    }
    return true;
}

int findNumSolutions(int board[8][8], int col, int rooksLeft)
{
   if(col > boardSize||rooksLeft ==0)
       return 1;
   int nsolutions = 0;
   for(int i = 0; i < boardSize; i++){
        board[col][i] = 1;
        if(!canPlace(col, i, board)){
            continue;
        }
        nsolutions += findNumSolutions(board, col + 1, rooksLeft - 1);
        board[col][i] = 0;
    }
    return nsolutions;
}

Answer 1

现在已修复的第一个错误是您在本应使用局部变量的递归函数中使用了成员变量。这里有两种变体：return 来自每次调用的数字，或者具有全局或成员函数并在那里累积解决方案。不要混用这些方法。

第二个错误，原始 post 中不存在，但在您 post 编辑整个代码时引入，位于此处：

// try placing piece in row of col
for(int i = 0; i < boardSize; i++){
    board[col][i] = 1;
    if(!canPlace(col, i, board)){
        continue;
    }
    nsolutions += findNumSolutions(board, col + 1, rooksLeft - 1);
    board[col][i] = 0;
}

这相当于：

// try placing piece in row of col
for (int i = 0; i < boardSize; i++){
    board[col][i] = 1;
    if (canPlace(col, i, board)) {
        nsolutions += findNumSolutions(board, col + 1, rooksLeft - 1);
        board[col][i] = 0;
    }
 }

车的设置和恢复必须是对称的；也就是说，每次放置车时，您都必须先休息，然后再尝试放置新车或再次递归返回。您可以看到车在每种情况下都已放置，但仅在可以放置时才被清理。这导致棋盘上出现的车多于应有的数量。

您的检查不考虑当前列，因此您可以将两个车放置在大括号外或都在大括号内。我建议：

for (int i = 0; i < boardSize; i++){
    if (canPlace(col, i, board)) {
        board[col][i] = 1;
        nsolutions += findNumSolutions(board, col + 1, rooksLeft - 1);
        board[col][i] = 0;
    }
}

作为补充，我认为 class 应该管理自己的董事会。这将消除许多令人困惑的 board 参数。如果在堆上分配板大小，则也不需要 MAXSIZE。但要注意：当棋盘尺寸变大时，排列的数量将溢出 int.

#include <iostream>

class NRooks {
public:
    NRooks(int n, int k);
    ~NRooks();

    int getSolutionTotal();

private:
    bool canPlace(int col, int row);
    int findNumSolutions(int col, int rooksLeft);

    int numSolutions;
    int numRooks;
    int boardSize;
    int *data;
    int **board;
};

NRooks::NRooks(int n, int k)
{
    numRooks = n;
    boardSize = k;
    numSolutions = 0;

    data = new int[k*k];
    board = new int*[k];

    for (int i = 0; i < k; i++) board[i] = data + k*i;
    for (int i = 0; i < k*k; i++) data[i] = 0;

    numSolutions = findNumSolutions(0, numRooks);
}

NRooks::~NRooks()
{
    delete[] data;
    delete[] board;
}

int NRooks::getSolutionTotal(){
    return numSolutions;
}

bool NRooks::canPlace(int col, int row)
{
    for (int i = col; i-- > 0; ) {
        if (board[i][row]) return false;
    }

    return true;
}

int NRooks::findNumSolutions(int col, int rooksLeft)
{
    if (rooksLeft == 0) return 1;
    if (col > boardSize) return (rooksLeft == 0);

    int nsolutions = 0;

    for (int i = 0; i < boardSize; i++) {
        if (canPlace(col, i)) {
            board[col][i] = 1;
            nsolutions += findNumSolutions(col + 1, rooksLeft - 1);
            board[col][i] = 0;
        }
    }

    if (rooksLeft < boardSize - col) {
        nsolutions += findNumSolutions(col + 1, rooksLeft);
    }

    return nsolutions;
}

int main()
{
    for (int boardSize = 2; boardSize <= 6; boardSize++) {
        for (int numPieces = 1; numPieces <= boardSize; numPieces++) {
            NRooks r = NRooks(numPieces, boardSize);

            std::cout << boardSize << " board, "
                      << numPieces << " rooks, "
                      << r.getSolutionTotal() << " solutions" 
                      << std::endl;
        }
    }

    return 0;
}

Answer 2

我不教这段代码的bug，但我有更高效的不回溯的解决方案。这只是一道数学题。

这道题是：给定整数N和K，找出将N个车放入K * K棋盘的方法数。

如果 N > K，则答案为零。
如果 N = K，则答案为 K!。因为每列可以select一个车，所以路数等于p={1, 2, 3,..., K}
的排列数
让我们考虑 N < K 的情况。
其实答案是P(K, N) * C(K, N)。如果棋盘大小为N * K，则只能select满足1<=p[i]<=K且p[i]不同的排列
所以有P(K, N)种方法。
您还可以在放置车的 K 行中选择 N 行。并且有 C(K, N) 种方式。
那么，最后的答案就是P(K, N) * C(K, N)

如果您不知道 P(Permutation) 或 C(Combination)，请阅读 here。
最后，如果 N <= K，答案是 P(K, N) * C(K, N)，否则答案是零。
时间复杂度O(K)，优于O(P(K, N) * C(K, N))暴力算法

Answer 3

我正在使用 square1001

描述的方法

#include <iostream>
using namespace std;

long long fact(int n)
{
    long long factorial=1;
    if(n<=0)
    {
        return 1;
    }
    for(int i=1; i<=n; ++i)
    {
        factorial *= i;              // factorial = factorial*i;
    }
    return factorial;
}
long long permutation(int n, int r) {
    if( n<=0 || r<= 0)
    {
        return 1;
    }
    return fact(n)/fact(n-r);
}

long long combination(int n, int r) {
    if(r > n / 2) r = n - r; // because C(n, r) == C(n, n - r)
    long long ans = 1;
    int i;

    for(i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }

    return ans;
}

long long findNumSolutions(int boardSize,int numberofRooks)
{
    if(numberofRooks>boardSize || numberofRooks <=0)
    {
        return 0;
    }
    long long comb=combination(boardSize,numberofRooks);
    long long  perm=permutation(boardSize,numberofRooks);
    cout<<"comb : "<<comb<<endl;
    cout<<"perm : "<<perm<<endl;
    return comb*perm;
}

int main ()
{
  std::cout <<findNumSolutions(3,3)<<endl;

  return 0;
}

N-Rooks 解决方案回溯数量

N-Rooks Number of Solutions Backtracking

c++

algorithm

backtracking