c++ - 回溯:8位主教占据整个董事会

我一直在写下这个回溯算法。问题:8位主教必须掩盖整个棋盘。它所要做的就是将4位主教放在白色的棋盘空间上，检查是否占用32个空间。如果是这样，请向左移动4个新的主教，使他们站在黑色空间上，问题得到解决。如果不是，请使用backtrack将主教放在其他地方。问题是，我只是无法将回溯记录下来-对我来说似乎太复杂了。

这是我所做的:

void findBishops(){
    for (int i=0; i<N; i++){ //get row
        int j;
        if (i%2==1) j=1; //2n+1 row has second white space, so we skip the first black space
        else j=0;
        for (; j<N; j+=2){ //get column
            //put into array those bishop coordinates and repeat 3 more times to get all 4 bishops.
            isFull(board, array); //give coordinates and check if all white spaces are occupied
            //if not - backtrack
            }
    }
}

bool isFull(int  board[][N], array[]){
   putIntoBoard(board, array[0], array[1]);
   putIntoBoard(board, array[2], array[3]);
   putIntoBoard(board, array[4], array[5]);
   putIntoBoard(board, array[6], array[7]);

    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){
        clean(board);
        return true;
    }else{
        clean(board);
        return false;
    }
}

void putIntoBoard(int board[][N], int a, int b){ //fills diagonal white spaces on board with 1's
    int i=a,j=b;
    board[i][j]=1;

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

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

    }
    i=a;
    j=b;

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

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


}

这是main function:

#include <iostream>
#define N 8
using namespace std;
void print(int board[][N]);
void putIntoBoard(int a, int b, int board[][N]);
bool isFull(int  board[][N], array[]);
void clean(int board[][N]);

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

    findBishops();

    cout<<"Counted possibilites: "<<count<<endl;
    return 0;
}

这只是一个原型(prototype)，如果您有更好的东西，请分享，我很乐意接受所有评论。

编辑:我忘记了几天前使用的其他算法，但是它没有递归也没有回溯，这里是:

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



    for (int i=0; i<N; i++)
    {
        int j;
        if (i%2==1) j=1;
        else j=0;
        for (; j<N; j+=2)
        {
            for(int k=0; k<N; k++)
            {
                int n;
                if (k%2==1) n=1;
                else n=0;
                for (; n<N; n+=2)
                {

                    for (int l=0; l<N; l++)
                    {
                        int o;
                        if (l%2==1) o=1;
                        else o=0;
                        for (; o<N; o+=2)
                        {

                            for(int m=0; m<N; m++)
                            {
                                int p;
                                if (m%2==1) p=1;
                                else p=0;
                                for (; p<N; p+=2)
                                {

                                    if (isFull(board,i,j,k,n,l,o,m,p))
                                    {
                                        count++;
                                        cout<<"Board filled up with white spaces on: ("<<i<<","<<j<<"), "<<"("<<k<<","<<n<<"), "<<"("<<l<<","<<o<<"), "<<"("<<m<<","<<p<<"), "<<endl;
                                    }

                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout<<"Counted possibilities: "<<count<<endl;

    return 0;
}

最佳答案

要将4个主教移至黑场，只需相对于垂直中心轴镜像它们即可。或水平的-结果将是相同的。它们将进入黑场，并且将威胁所有黑场(如果它们在镜像之前威胁了所有白场)。