DFS+剪枝优化

N皇后问题题目描述在 N×NN×N 的方格棋盘放置了 NN 个皇后使得它们不相互攻击即任意 22 个皇后不允许处在同一排同一列也不允许处在与棋盘边框成 4545 角的斜线上。你的任务是对于给定的 NN求出有多少种合法的放置方法。输入描述输入中有一个正整数 N≤10N≤10表示棋盘和皇后的数量输出描述为一个正整数表示对应输入行的皇后的不同放置数量。输入输出样例示例 1输入5输出10运行限制最大运行时间1s最大运行内存: 128Mpackage mar27; import java.util.Scanner; public class Test1 { static int ans 0; static int[] a; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); a new int[n 1];//a[i] j表示第i行第j列放置皇后或者是第i行的皇后放置在第i个位置 dfs(n , 1); System.out.println(ans); } static void dfs(int n , int r){ if(r n) { ans; return; } for (int i 1; i n ; i) { a[r] i;//这一步直接代替了回溯撤销 if(check(r))//剪枝优化 dfs(n , r 1 ); } } static boolean check(int r){ for (int i 1; i r ; i) { if(a[i] a[r] || Math.abs(i - r) Math.abs(a[i] - a[r])) return false; } return true; } }