题
1.843. n-皇后问题 - AcWing题库
大名鼎鼎N皇后
import java.util.*;public class Main {static int N = 10;static int n;static char[][] map = new char[N][N];static boolean[] row = new boolean[N];static boolean[] col = new boolean[N];static boolean[] dg = new boolean[N*2];static boolean[] udg = new boolean[N*2];static void dfs(int u, int x, int y) {if(u > n)return ;if(y == n) {y = 0;x += 1;}if(x == n) {if(u == n) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {System.out.print(map[i][j]);}System.out.println();}System.out.println();}return ;}// 这一列不放皇后dfs(u, x, y+1);if(!row[x] && !col[y] && !dg[x-y+n] && !udg[x+y]) {map[x][y] = 'Q';row[x] = col[y] = dg[x-y+n] = udg[x+y] = true;dfs(u+1, x, y+1);map[x][y] = '.';row[x] = col[y] = dg[x-y+n] = udg[x+y] = false;}}public static void main(String[] args) {Scanner scan = new Scanner(System.in);n = scan.nextInt();for(int i = 0; i < n; i++){for(int j = 0; j < n; j++) {map[i][j] = '.';}}dfs(0, 0, 0);scan.close();}}//zhuanxinyidian!!!这是第一种搜索顺序，目前先掌握这一种。
N皇后的思路就是，按照行的顺序，以每一行的视角来看每一列，这样来遍历每一个格子是不是能放皇后，u记录当前放的是第几个皇后。
当u>n的时候，说明已经遍历到最底层，我们可以开始模拟放皇后，一层一层返回了。当y==n时，说明此时遍历的位置已经超出边界，换下一行的第一个格子看。当x==n时u==n，说明在最后一行，最后一个皇后也放好了，说明当前这个矩阵就满足条件了，可以输出了。
因为是深度优先遍历，是一定会一行一行的遍历下去的。然后对于每一行来说，有两种选择，第一是在这一列放皇后，判断位置是否满足条件；第二是向下一层递归，在下一列放皇后。
如果这一行、这一列、主对角线、副对角线都没有放过皇后，那么久放！然后将标记数组给标记一下。放的皇后个数加1，列加1，为什么不行加1，因为我们要模拟所有的格子，模拟每种情况，不能漏掉。
2.842. 排列数字 - AcWing题库
import java.util.*;public class Main {static int n;static final int N = 10;static int[] path = new int[N];static boolean[] st = new boolean[N];static void dfs(int u) {if(u == n) {for(int i = 0; i < n; i++){System.out.print(path[i] + " ");}System.out.println();return;}for(int i = 1; i <= n; i++) {if(!st[i]) {st[i] = true;path[u] = i;dfs(u+1);// 不恢复也可以，因为后续这个path[i]会不断被覆盖path[u] = 0;st[i] = false;}}}public static void main(String[] args) {Scanner scan = new Scanner(System.in);n = scan.nextInt();dfs(0); scan.close();}
}有n个位置放数字，第一个位置的数字放好之后，还有n-1个位置。
对于第n-1个位置，第n-1个位置放好之后，还有n-2个位置。
。。。
就这样一层一层的递归下去，返回的时候又模拟出不同的情况。