八皇后问题

柔情只为你懂 2022-05-28 01:47 250阅读 0赞

即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

由于皇后们是不能放在同一行的， 所以我们可以去掉“行”这个因素，即我第1次考虑把皇后放在第1行的某个位置， 第2次放的时候就不用去放在第一行了，因为这样放皇后间是可以互相攻击的。 第2次我就考虑把皇后放在第2行的某个位置，第3次我考虑把皇后放在第3行的某个位置， 这样依次去递归。每计算1行，递归一次，每次递归里面考虑8列， 即对每一行皇后有8个可能的位置可以放。找到一个与前面行的皇后都不会互相攻击的位置， 然后再递归进入下一行。找到一组可行解即可输出，然后程序回溯去找下一组可靠解。

我们用一个一维数组来表示相应行对应的列，比如c\[i\]=j表示， 第i行的皇后放在第j列。如果当前行是r，皇后放在哪一列呢？c\[r\]列。 一共有8列，所以我们要让c\[r\]依次取第0列，第1列，第2列……一直到第7列， 每取一次我们就去考虑，皇后放的位置会不会和前面已经放了的皇后有冲突。 怎样是有冲突呢？同行，同列，对角线。由于已经不会同行了，所以不用考虑这一点。 同列：c\[r\]==c\[j\]; 同对角线有两种可能，即主对角线方向和副对角线方向。 主对角线方向满足，行之差等于列之差：r-j==c\[r\]-c\[j\]; 副对角线方向满足， 行之差等于列之差的相反数：r-j==c\[j\]-c\[r\]。 只有满足了当前皇后和前面所有的皇后都不会互相攻击的时候，才能进入下一级递归。

#include <cstdio>
    #include <algorithm>
    using namespace std;
    
    
    int num[8];//比如num[i]=j,表示第i行的皇后放在第j列，这个数组很巧妙关键
    int sum;
    
    void dfs(int step){
    
        if(step>=8){
            sum++;
            for(int i=0;i<8;i++){
                for(int j=0;j<8;j++){
                    if(num[i]==j)
                        printf("1");
                    else
                        printf("0");
                }
                printf("\n");
            }
            printf("\n");
            return ;
        }
        //因为没一行本来就只放了一个,所以行不会存在攻击;
        //所以只需放在8列中的某一列即可,因此遍历8次
        for(int i=0;i<8;i++){
    
    
            num[step]=i;//第step行的皇后放在第i列
            int ok=0;
            for(int j=0;j<step;j++){//和前面几行的皇后比较，看是否相互攻击
                //如果和前面某个皇后在同一列或者在两斜线上说明这一列放不得
                if(num[step]==num[j]||num[step]-num[j]==step-j||num[step]-num[j]==j-step){
                    ok=1;
                    break;
                }
            }
            if(!ok){
                dfs(step+1);
            }
        }
    
    }
    int main(){
    
        sum=0;
        dfs(0);
        printf("%d\n",sum);
        return 0;
    }