排列数字

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10;
int path[N]; //用来存方案
int st[N]; //用来检查哪一个数被用过
int n;
void dfs(int u)
{
    //表示深搜到最后了，即可以输出结果
    if(u==n)
    {
        for(int i=0;i<n;i++)
        cout<<path[i]<<" ";
        cout<<endl;
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(!st[i]) //找到一个没有被搜索过的数字
        {
            path[u]=i;
            st[i]=1;
            dfs(u+1); //递归调用，再次深搜
            //恢复现场，一切回归到递归之前的状态
            path[u]=0; //因为path[]的数值会一次一次的被覆盖，因此此步可以省略
            st[i]=0;
        }
    }
}
int main()
{
    cin>>n;
    dfs(0);
    return 0;
}

n-皇后问题

解法1：利用上题的思想进行枚举

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 20;
int n;
char res[N][N];
bool col[N]; //存储用过哪一行,因为每一行只能有一个皇后
bool dg[N];  //存储用过哪一条负对角线，在同一条对角线上时，横坐标 + 纵坐标是一个定值
bool udg[N]; //存储用过哪一条正对角线，在同一条对角线上时，横坐标 - 纵坐标是一个定值，但是数组下标不能是一个复数，所以需要加上偏移量n
void dfs(int u)
{
    if (u == n)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
                cout << res[i][j];
            cout<<endl;
        }
        cout<<endl;
        return;
    }
    for (int i = 0; i < n; i++)
    {
        if (!col[i] && !dg[u + i] && !udg[n - u + i]) //u是已知的横坐标x值，i是递归求解的纵坐标y值，所以dg和udg函数这样写
        {
            res[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = 1;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - u + i] = 0;
            res[u][i] = '.';
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            res[i][j] = '.';
    dfs(0);
    return 0;
}

解法2：最原始的方法，直接枚举每个格子，每个格子有两种情况，放皇后或者不放皇后

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 20;
int n;
char res[N][N];
bool row[N];                  //存储用过哪一列
bool col[N];                  //存储用过哪一行
bool dg[N];                   //存储用过哪一条负对角线，在同一条对角线上时，横坐标 + 纵坐标是一个定值
bool udg[N];                  //存储用过哪一条正对角线，在同一条对角线上时，横坐标 - 纵坐标是一个定值，但是数组下标不能是一个复数，所以需要加上偏移量n
void dfs(int x, int y, int s) //x表示列，y表示行，s表示放了几个皇后
{
    if (y == n) //表示如果在一行中跑出界了，要把它拉回来
        y = 0, x++;
    if (x == n) //表示枚举到最后一行
    {
        if (s == n) //如果放了n个皇后，就输出结果
        {
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                    cout << res[i][j];
                cout << endl;
            }
            cout << endl;
        }
        return; //不论如何都要回溯
    }
    //对于每次枚举，只有两种情况，放皇后和不放皇后
    //不放皇后
    dfs(x, y + 1, s);
    //放皇后
    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
    {
        res[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = 1;
        dfs(x, y + 1, s + 1);
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = 0;
        res[x][y] = '.';
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            res[i][j] = '.';
    dfs(0,0,0);
    return 0;
}