经典搜索题目——八皇后（P1219）（洛谷训练场）题解

分手后的思念是犯贱 2022-12-28 07:24 196阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入
     *  输出
     *  算法分析
     *  解题标程
     *  错题总结

--------------------

# 题目描述 #

检查一个如下的6 x 6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

![在这里插入图片描述][2020121514210338.png]

上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下：

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。

## 输入 ##

## 输出 ##

2 4 6 1 3 5
    3 6 2 5 1 4
    4 1 5 2 6 3
    4

## 算法分析 ##

*  难点在于怎么去记录每条对角线的位置
 *  总共有两类对角线：
 *  1、从右上角到左下角 2、从左上角到右下角
 *  对于情况1而言，在图中的可以很容易找到规律每条对角线可记录为 i+j
 *  对于情况2而言，如果使用 i+j 没有一个统一的情况，而当使用 i-j 时，会导致数组下标出现负数，那么这里将所有的数字向正数方向移动 n 位，即 i-j+n，这时就可以统一情况2的对角线

## 解题标程 ##

#include <cstdio>
    #include <iostream>
    #include <cstring>
    using namespace std;
    //map[0]记录列
    //map[1]记录右上角到左下角的对角线
    //map[2]记录左上角到右下角的对角线
    int map[3][1005];
    int n;
    int to[4][2]={
        {
        -1,0},{
        1,0},{
        0,-1},{
        0,1}};
    int ans[1005];
    
    int cnt=0;
    void dfs(int i) //用每行，这样就不用标记行坐标，行是不会重复的
    {
        
        if(i>n){
        
            cnt++;
            if(cnt>3)
                return;
            for(int k=1;k<=n;k++)
                cout << ans[k] << " ";
            cout << endl;
            return;
        }
        for(int j=1;j<=n;j++){
          //搜索每一列
            if((!map[0][j])&&(!map[1][i+j])&&(!map[2][i-j+n])){
        
                ans[i]=j;
                map[0][j]=1;
                map[1][i+j]=1;
                map[2][i-j+n]=1;
                dfs(i+1);
                map[0][j]=0;
                map[1][i+j]=0;
                map[2][i-j+n]=0;
            }
        }
        return;
    }
    
    int main()
    {
        
        cin >> n;
    
        dfs(1);
        
        cout << cnt << endl;
        
        return 0;
    }

--------------------

## 错题总结 ##

> 注意对角线的规律！！！

[2020121514210338.png]: /images/20221120/cddd79ac736e435985de8dff1db1ea72.png