0

私はこの再帰アルゴリズムを持っています:

#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! ですが、力ずくではないので間違っています。誰かがここで正しい答えを教えてくれますか?

4

1 に答える 1

1

N=8 の場合、漸近的な複雑さはありません。

N が変化する場合、ブルート フォース アプローチは、利用可能な N^2 の中から N 個のセルを選択し、それらにビショップを配置することが機能するかどうかを確認することです (そうではありませんか?)。これは N^2 の複雑さにつながります N ~ N^{2N}/N を選択してください! ~ (Ne)^N (多項式の項)。これは指数関数的に N を超えています。~ (N/e)^N.

私はあなたのアルゴリズムの詳細を読んでいませんが、実際には N! であるに違いありません。

于 2015-04-29T14:24:30.540 に答える