题目描述

给定一个 N×N 的棋盘，请你在上面放置 N 个棋子，要求满足：

每行每列都恰好有一个棋子
每条对角线上都最多只能有一个棋子
1 2 3 4 5 6

1 | | O | | | | |

2 | | | | O | | |

3 | | | | | | O |

4 | O | | | | | |

5 | | | O | | | |

6 | | | | | O | |

上图给出了当 N=6 时的一种解决方案，该方案可用序列 2 4 6 1 3 5 来描述，该序列按顺序给出了从第一行到第六行，每一行摆放的棋子所在的列的位置。

请你编写一个程序，给定一个 N×N 的棋盘以及 N 个棋子，请你找出所有满足上述条件的棋子放置方案。

输入格式
共一行，一个整数 N。

输出格式
共四行，前三行每行输出一个整数序列，用来描述一种可行放置方案，序列中的第 i 个数表示第 i 行的棋子应该摆放的列的位置。

这三行描述的方案应该是整数序列字典序排在第一、第二、第三的方案。

第四行输出一个整数，表示可行放置方案的总数。

(暴力枚举)

C++ 代码

#include<iostream>
#include <cstring>
using namespace std;

int n;//棋盘大小
int wz[13];//存储放置的位置
int map[13][13];//棋盘
int res = 0;//方案数
void sz(int x, int i,int k)//将棋盘打上或者去除标记的函数，打上标记，就是+1，去除标记就是-1（k取1或-1）
{
    for (int y = x + 1; y < n; y++)//水平方向标记
    {
        map[i][y] +=k;
    }
    for (int y = x + 1, z = i - 1; z >= 0 && y < n; y++, z--)//斜上方标记
    {
        map[z][y] +=k;
    }
    for (int y = x + 1, z = i + 1; z < n && y < n; z++, y++)//斜下方标记
    {
        map[z][y] += k;
    }
}

void dfs(int x)//核心函数，用于暴搜，我这个是一列一列的搜索
{
    if (x == n)//当下够n个棋子后
    {
        res++;//方案数+1
        if (res <= 3)//如果是前三个方案，输出，因为是按字典序搜索，所以直接输出前三个即可
        {
            for (int i = 0; i < n; i++)
            {
                cout << wz[i] << " ";
            }
            cout << endl;
        }
        return;//结束本分支
    }
    for (int i = 0; i < n; i++)//遍历棋盘中的本列
    {
        if (map[i][x]==0)//如果未被标记即该点未0，可下棋
        {
            wz[x] = i + 1;//记住该棋下的位置
            sz(x, i, 1);//打上标记
            dfs(x + 1);//进入该分支的下一阶段
            sz(x, i, -1);//去除标记
        }
    }
}

int main()
{
    memset(map, 0, 4 * 11 * 11);//初始化棋盘
    cin >> n;//输入棋盘大小
    for (int x = 0; x < n; x++)遍历第一颗棋子可以下的位置（内容同dfs函数中的内容）
    {
        wz[0] = x + 1;
        sz(0, x, 1);
        dfs(1);
        sz(0, x, -1);
    }
    cout << res;//输出答案
    return 0;
}