N-Rooks Number of Solutions Backtracking

Question

These methods are supposed to give the count of arrangements that any number of rooks could have on a board in non-attacking arrangement. I know I must be missing something silly here. Help me out. For some reason my returned solution count is off, even though with print statements 6 solutions are found... I've tried printing the array, printing when a solution is found... and I can't find anything that helps.

EDIT*: The User Interface is incomplete. Ignore shitty errors in it. More concerned with the incorrect results I'm getting from my findnumsolution() method. I've tried directly passing values through the constructor and it still gives me wrong answers. 3x3 board, with 3 pieces, returns 5, 4x4 with 4 returns 13.

EDIT**: Cleaned unrelated code.

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

The first error, now fixed, is that you use a member variable in a recursive function where you should use a local variable. There are two variants here: Either return the number from each call or have a global or member function and accumulate the solutions there. Don't mix these approaches.

The second error, which wasn't there in the original post, but which was introduced when you posted the whole code, is here:

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

This is equivalent to:

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

The setting and restoring of the rook must be symmetric; that is each time a rook is placed you must rest it before trying to place a new rook or before recursing back up again. You can see that the rook is placed in every case, but is only cleaned up when it can be placed. This results in more rooks being on the board than should be.

Your check doesn't consider the the current columns, so you can either place both rook placements outside the braces or both inside. I suggest:

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

As an addendum, I think that the class should manage its own board. This will do away with many confusing board parameters. If you allocate the board size on the heap, you don't need the MAXSIZE, either. But beware: When board sizes get big, the counts of arrangements will overflow an 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;
}