【递归入门】n皇后问题

以你之姓@ 2023-02-13 14:47 29阅读 0赞

题目描述

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。
    如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。

输入

一个整数n（ 1 < = n < = 10 )

输出

每行输出对应一种方案，按字典序输出所有方案。每种方案顺序输出皇后所在的列号，相邻两数之间用空格隔开。
    如果一组可行方案都没有，输出“no solute!”

样例输入

样例输出

2 4 1 3
    3 1 4 2

#include <cstdio> 
    #include <cmath>
    const int maxn = 10;
    int flag;  //标志有无至少一组可行方案 
    int a[maxn],n;
    
    //判断当前位置是否可行 
    bool isValid(int row){
        
     int i,num;
     for(i = 0; i < row; i++){
        
      //将当前行与其他行作比较 
      if(abs(a[i] - a[row]) == abs(row - i) || a[row] == a[i])
      //如果第row行与第i行的行数之差的绝对值等于列数之差的绝对值，则处于同一对角线 
      //或者处于同一列上，则不可行 
       return false;
     }
     return true;
    }
    
    //深度优先搜索 
    void dfs(int n,int now,int row){
        
     //需要放置n个棋子，当前所放第now个棋子，row表示行数 
     int i;
     if(now == n){
          //放完了n个棋子，输出每行所放棋子的列数 
      for(i = 0; i < n-1; i++)
       printf("%d ",a[i] + 1);
      printf("%d\n",a[n-1] + 1);
      flag = 1; //有可行方案 
      return; 
     } 
     for(i = 0; i < n; i++){
        
      //对一行的n列依次判断 
      a[row] = i;  //第row行的第i列放棋子 
      if(isValid(row)){
         
      //如果可行则进行下一步dfs 
       dfs(n, now + 1, row + 1);
      }
     }
    } 
    
    int main(int argc, char** argv) {
        
     scanf("%d", &n);
     flag = 0;  //初始值标志为0 
     dfs(n,0,0);
     if(flag == 0) //无可行方案 
      printf("no solute!\n");
     return 0;
    }