前言

今天是經典的深度優先搜索問題，即八皇后問題，
在這里插入圖片描述
作為經典問題，我發現了一種新的寫法，不需要開二維陣列即可完成，

題目

給定一個 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 行的棋子應該擺放的列的位置，
這三行描述的方案應該是整數序列字典序排在第一、第二、第三的方案，
第四行輸出一個整數，表示可行放置方案的總數，

資料范圍

6 ≤ N ≤ 13 6≤N≤13 6≤N≤13

輸入樣例：
6
輸出樣例：
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

詳細題解

寫法1

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15;

int n;
bool col[N], dg[N*2], udg[N*2];
int path[N], ans;

void dfs(int x)
{
    if(x > n)
    {
        ++ ans;
        if (ans <= 3)
        {
            for (int i = 1; i <= n; ++ i )
                cout << path[i] << " ";
            cout << endl;
        }
        return ;
    }
    
    for (int y = 1; y <= n; ++ y )
        if (!col[y] && !dg[x - y + n] && !udg[x + y])
        {
            path[x] = y;
            col[y] = dg[x - y + n] = udg[x + y] = true;
            dfs(x + 1);
            
            path[x] = 0;
            col[y] = dg[x - y + n] = udg[x + y] = false;
        }
}

int main()
{
    cin >> n;
    dfs(1);
    cout << ans << endl;
    
    return 0;
}