algorithm - 寻找回溯递归算法的复杂性

Question

我有这个递归算法:

#include <iostream>
#include <cmath>
#include <map>
#include <iterator>
#define N 8
using namespace std;
void putIntoBoard(int a, int b, int board[][N]);
bool isFull(int  board[][N]);
void cleanBoard(int board[][N]);
void bishopSolver(int level, int i, int board[][N]);
void putIntoArray(int a, int b);
void printout();

map<int, int> coordMap;

int main(){
    int board [N][N]= {0};
    int count= 0;
    int level;
    int i;



    bishopSolver(0,0,board);

    return 0;
}

void printout(){

    for (map<int,int>::iterator it = coordMap.begin(); it != coordMap.end(); ++it) {
        int value = it->second;


        int y = value / 8;
        int x = value - y * 8;
        cout<<"("<<x<<";"<<y<<"), ";
        x=x+1;
        if ((x) == 7) x=0;
        cout<<"("<<x<<":"<<y<<"), "<<endl;


    }
}




void putIntoBoard(int a, int b, int board[][N]){


    int i=a,j=b;
    board[i][j]=1;

    while(i>0 && (j<7) )/*Up right*/{
        i--;
        j++;
        board[i][j]=1;
    }
    i=a;
    j=b;
    while(j>0 && i>0) /*Up Left*/{
        i--;
        j--;
        board[i][j]=1;

    }
    i=a;
    j=b;
    while(i<7&& j<7) /*Down right*/{
        i++;
        j++;
        board[i][j]=1;

    }
    i=a;
    j=b;

    while(i<7 && j>0) /*Down left*/{

        i++;
        j--;
        board[i][j]=1;
    }


}
bool isFull(int  board[][N]){

    int x1, y1;

    for (map<int,int>::iterator it = coordMap.begin(); it != coordMap.end(); ++it) {
        int value = it->second;


        int y = value / 8;
        int x = value - y * 8;
        putIntoBoard(x, y, board);
    }

    int i, j;
    int count=0;
        for (i=0; i<=7; i++){

            if (i%2==1) j=1;
        else j=0;

        for (; j<=7; j+=2){
            if (board[i][j]==1) count++;
        }
    }
    if (count==32){
        cleanBoard(board);
        return true;
    }else{
        cleanBoard(board);
        return false;
    }
}
void cleanBoard(int board[][N]){
      for (int i=0; i<N; i++)
    {
        for (int j=0; j<N; j++) board[i][j]=0;
    }
}

void addToMap(int level, int i) {
    coordMap[level] = i;
}

void removeFromMap(int level) {
    coordMap.erase(level);
}


void bishopSolver(int level, int i, int board[][N]){
    int size = 63 - (6 -  level);
    for (; i < size; i+=2){
        addToMap(level, i);
        if(level == 3 && isFull(board)){

            cout<<"Solved: "<<endl;
            printout();
            return;
        }
        if (level < 3){
            bishopSolver(level + 1, i + 2, board);
        }
        removeFromMap(level);
    }
}

基本上它解决了象棋问题，用 8 个象填满棋盘，使整个棋盘被 8 个象棋占据。在我看来，这个算法是 n!，但它不是蛮力，所以我错了。有人可以在这里给我一个正确的答案吗？

Answer 1

如果 N=8 则没有渐近复杂性。

如果 N 发生变化，蛮力方法将是(不是吗？)在 N^2 个可用单元格中选择 N 个单元格，并检查将象放置在它们上面是否有效。这就导致了N^2的复杂度选择N~N^{2N}/N! ~ (Ne)^N(乘以多项式项)。这比 N 指数级多! ~ (N/e)^N.

我没有通读你的算法的细节，但我敢打赌它实际上是 N!。