递归求全排列

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入样例

输出样例

AC代码

include<iostream>
using namespace std;
const int N = 10;
int path[N];//保存序列
int state[N];//数字是否被用过
int n;
void dfs(int u)
{
    if(u > n)//数字填完了，输出
    {
        for(int i = 1; i <= n; i++)//输出方案
            cout << path[i] << " ";
        cout << endl;
    }

    for(int i = 1; i <= n; i++)//空位上可以选择的数字为:1 ~ n
    {
        if(!state[i])//如果数字 i 没有被用过
        {
            path[u] = i;//放入空位
            state[i] = 1;//数字被用，修改状态
            dfs(u + 1);//填下一个位
            state[i] = 0;//回溯，取出 i
        }
    }
}

int main()
{

    cin >> n;
    dfs(1);
}

用 path 数组保存排列，当排列的长度为 n 时，是一种方案，输出。
用 state 数组表示数字是否用过。当 state[i] 为 1 时：i 已经被用过，state[i] 为 0 时，i 没有被用过。
dfs(i) 表示的含义是：在 path[i] 处填写数字，然后递归的在下一个位置填写数字。
回溯：第 i 个位置填写某个数字的所有情况都遍历后，第 i 个位置填写下一个数字。

皇后问题

编写一个函数，求解皇后问题：在 n×n 的方格棋盘上，放置 n 个皇后，要求每个皇后不同行、不同列、不同左右对角线。

输入样例

输出样例

1 2	2 4 1 3 3 1 4 2

类似搜全排列按行搜索加上限制条件

AC代码

#include<bits/stdc++.h>
using namespace std;

const int N = 20;

int n,hh;
int a[N];
bool col[N],dg[N],udg[N];

void dfs(int u)
{
    if(u>n)
    {
        for(int i = 1;i<=n;i++)
        cout<<a[i]<<" ";
        puts("");
        hh++;
        return ;
    }



    for(int i = 1;i<=n;i++)
    {
        if(!col[i]&&!dg[u+i]&&!udg[i-u+n])
        {
            col[i] = 1;
            dg[u+i] = 1;
            udg[i-u+n] = 1;
            a[u] = i;
            dfs(u+1);
            col[i] = 0;
            dg[u+i] = 0;
            udg[i-u+n] = 0;
        }
    }
}

int main()
{
    cin>>n;

    dfs(1);

    //cout<<hh;

    return 0;
}

bool数组用来判断搜索的下一个位置是否可行
col列，dg对角线，udg反对角线

(x,y)->(u,i)

y = x+b; b = y-x; 下标为正需要加上一个数（随便加，保证为正且规则一样即可）

y = -x+b; b = y+x(正)

Fly

n皇后

递归求全排列

皇后问题