算法 -- 四皇后问题(回溯法)

昔我往矣,杨柳依依。今我来思,雨雪霏霏


问题描述

在 4*4 的棋盘上无冲突的摆放 4 个皇后,无冲突是指一个皇后所在位置的水平、竖直以及斜线上不能出现其他的皇后,其他的 n 皇后问题以此类推

解决方法

按行来摆放棋子,下一行的摆放满足于与上一行的棋子没有冲突,否则就返回上一步走其他的路线,这就是所谓的回溯法

详细说明

  1. 在第一行有四种可能,选择第一个位置放上皇后

  2. 第二行原本可以有四种可能摆放,但是第一第二个已经和第一行的皇后冲突了,因此只剩下第三第四个格子了,先选择第三个格子

  3. 接下来是第三行,根据规则可以看出,第三行已经没有位置放了,因为都跟第一第二行的皇后冲突,此时返回到第二行第四个

  4. 继续来到第三行,发现只有第二个满足条件

  5. 然后发现第四行已经不能放了,只能继续返回,返回到第一行,开始下一种可能

  6. 按照 1-5 的步骤,可以找到下面的其中一种解法 enter description here

总而言之,回溯法就是开始一路到底,碰到南墙了就返回走另外一条路,有点像穷举法那样走遍所有的路

算法实现

构建二维数组,增加规则,利用递归实现回溯效果

# include <stdio.h>
# define N 4         // 可以调整

int count=0;

// 判断 Q[i][j] 是否存在冲突 
int isCorrect(int i, int j, int (*Q)[N]) {

    int s,t;
    // 判断行 
    for(s=i,t=0; t<N; t++)
        if(Q[s][t]==1 && t!=j)
            return 0;

    // 判断列 
    for(s=0,t=j; s<N; s++)
        if(Q[s][t]==1 && s!=i)
            return 0;

    // 判断左上角    
    for(s=i-1,t=j-1; s>=0&&t>=0; s--,t--)
        if(Q[s][t]==1)
            return 0;

    // 右下角 
    for(s=i+1,t=j+1; s<N&&t<N; s++,t++)
        if(Q[s][t]==1)
            return 0;

    // 右上角 
    for(s=i-1,t=j+1; s>=0&&t<N; s--,t++)
        if(Q[s][t]==1)
            return 0;

    // 左下角 
    for(s=i+1,t=j-1; s<N&&t>=0; s++,t--)
        if(Q[s][t]==1)
            return 0;

    return 1;



}

// 递归函数,第 i+1 行的遍历  
void Queue(int i, int (*Q)[N]) {

     int j,k;

     // 第四行已经遍历完,打印符合条件的结果,结束 
     if(i==N) {

         count++;
         printf("No.%d slove way\n",count);   
         for(k=0;k<N; k++) {

             for(j=0; j<N; j++)
                 printf("%-5d", Q[k][j]);
             printf("\n");

             //return;
         }
         printf("\n");

     }

     // 遍历第 i+1 行的 j+1 列 
     for(j=0;j<N; j++) {

         if(isCorrect(i,j,Q)) {

             Q[i][j]=1;
             Queue(i+1,Q);   // 遍历下一行 
             Q[i][j]=0;      // 如果下一行不成立,则回溯,重置 0                      

         }  
     }  
}

int main() {

    int Q[N][N];
    int i,j;

    // 初始化二维数组并打印 
    for (i=0; i<N; i++) { 

        for(j=0; j<N; j++) {
            Q[i][j] = 0;
            printf("%-5d",Q[i][j]);
        }
        printf("\n");

    }
    printf("\n");
    Queue(0, Q); // 从第一行开始递归 
    printf("solve count is %d\n", count);
    getchar();
    getchar();
    return 0; 



}

效果展示

N = 4 时,有两种解法

N = 8 时,有 92 种解法

然后手贱试了一下 N = 16 的,结果跑了 7-8 分钟这样,已经到了第23028 种解法了,第一行还在第一个位置,果断放弃