c++ - N-Rooks解决方案数量回溯

这些方法应该给出在非攻击性的情况下，任何数量的车都可以在一个板上的排列的计数。
我知道我一定错过了一些傻事帮帮我由于某种原因，我返回的解决方案计数是关闭的，即使与打印语句6解决方案被发现我试过打印阵列，找到解决方案后打印我找不到任何有帮助的东西。
编辑*：用户界面不完整。忽略其中的错误更关心的是我从findnumsolution（）方法得到的错误结果。我尝试过直接通过构造函数传递值，但它仍然给了我错误的答案3x3板，3块，返回5，4x4，4返回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;
}

最佳答案

第一个错误，现在已修复，是在递归函数中使用成员变量，在递归函数中应该使用局部变量。这里有两个变体：要么从每个调用返回数字，要么有一个全局函数或成员函数，并在那里累积解决方案别把这些方法混在一起。
第二个错误，在最初的帖子中没有，但是在你发布整个代码时出现了，在这里：

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

rook的设置和恢复必须是对称的；也就是说，每次放置rook时，必须在尝试放置新rook之前或在再次递归备份之前让它休息你可以看到车放在每一个箱子里，但只有当它可以放的时候才会被清理干净这将导致更多的车在董事会上比应该的。
您的检查不考虑当前列，因此您可以将两个rook放置在大括号外，也可以将两者都放置在大括号内。我建议：

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

作为补充，我认为这个班应该管理自己的董事会这将消除许多令人困惑的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;
}