N皇后问题【递归、搜索】

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。

共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。

共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

1
8
5
0

1
92
10

AC代码

#include 
#include

using namespace std;

const int MAX_NUM = 11;
int cnt = 0 ,board[MAX_NUM] , ans[MAX_NUM];

void output_ans(int n){
    cout << ans[n] << endl;
}

// 判断第i行的第k列是否可以放置
bool judge_ok(int find_row_index , int find_col_index){
    for(int cur_row = 1 ; cur_row < find_row_index  ; cur_row ++){
        if(board[cur_row] == find_col_index || abs(cur_row - find_row_index ) == abs(board[cur_row] - find_col_index) ){
            return false;
        }
    }
    return true;
}

void place_queen(int row_index , int n){
    if(row_index > n){
        //cnt ++ ;
        ans[n] ++ ;
        return ;
    }
    // 判断当前行的每一列
    for(int cur_col = 1 ; cur_col <= n ; cur_col ++){
        if(judge_ok(row_index , cur_col )){
            board[row_index] = cur_col;
            place_queen(row_index + 1 , n);
        }
    }

}

int main()
{
    int n ;

    while(cin >> n && n != 0){
        memset(board , 0 , sizeof(board));
        if(ans[n] != 0){
            output_ans(n);
            continue;
        }
        place_queen(1 , n);
        output_ans(n);
    }

    return 0;
}

输入一个正整数（<=10），可设置最大数字MAX_NUM = 10

输出总共有多少种方案，需要进行枚举，设置全局变量数组ans

首先对循环输入，结束条件为n = 0

 while(cin >> n && n != 0)

这是一个很好的多组输入的模板方法

若题目中出现出现多组输入，而且没有结束的输入条件就可以直接使用

 while(cin >> n){

然后进行判断是否当前的n是否已经计算过，这点一定要注意！！！

if(ans[n] != 0)

我第一次提交代码就是因为没有对这个进行处理，然后导致超时了

当时我想的是，n就1-10，就没有去存了

而且自己测试我直接输入10也很快就给出答案，就直接提交了

结果超时了！！

因为还需要考虑到如果测试用例中，全部都是10，每次都计算一遍，时间就会显得很长！！！

执行最主要的函数，函数大致功能就是循环递归放置皇后，并在行超过n时，cnt累加

传入参数

• 行下标——row_index
• 最大列下标——n

意为，从当前的行下标判断在每一列上放置皇后

大致执行逻辑

若当前递归的行下标row_index是否大于放置个数n

• 大于

  • ans[当前下标] ++
  • 返回函数

• 小于或等于

  • 放置皇后

放置皇后的具体逻辑

对当前行row_index每一列放置皇后

• 判断当前行row_index和当前列cur_col是否可放置——judgeOk函数

  • 可放置

    • 将当前的列下标 赋值给 当前棋盘上的行下标

      board[row_index] = cur_col
      

    • 递归自身——行数+1

judgeOk函数逻辑

判断该行该列是否可以放置皇后

传入参数

• find_row_index——查询的行下标
• find_col_index——查询的列下标

从行数1——当前查询的行下标find_row_index循环

• 判断

  • 棋盘的当前行是否等于当前列下标——不能在同一行

    因为在刚开始时，改函数返回的是true

    则在放置皇后函数中，将会放置皇后

    board[row_index] = cur_col
    

  • 当前行下标 - 查询的行下标 与 棋盘对应结果 - 查询的列下标的绝对值进行比较——45度判断

    • 是

      • 返回false

最后返回true