企业官网建设流程全解析

题目：

求n皇后问题的所有解。

n个皇后摆放在n*n的棋盘格中，使得横、竖和两个对角线方向均不会出现两个皇后。

思路：

（1）采用剪枝减少不必要的计算；

（2） 快速判断不合法的情况：a、竖向；b、对角线1（右上→左下）；c、对角线2（左上→右下）；

b、对角线1：共有 2*n-1 个对角线，其中同一对角线上 i+j 的值相等，因此可用 i+j 来标识当前的对角线；

c、对角线2：共有 2*n-1 个对角线，其中同一对角线上 i-j 的值相等，因此可用 i-j+n-1 来标识当前的对角线；

代码如下：

package com.haobi; import java.util.ArrayList; import java.util.List; public class N_Queues { // res数组用来存储所有结果 private static List<String> res = new ArrayList<>(); // 记录纵方向上是否冲突 private static boolean col[]; // 记录对角线1方向上是否冲突 private static boolean dir1[]; // 记录对角线2方向上是否冲突 private static boolean dir2[]; public static void main(String[] args) { int Q = 4; List<String> list = solveNQueens(Q); int countA = 0; int countB = 0; for(String s: list) { countA++; if(countA % Q == 0) { System.out.println(s); }else { System.out.print(s+" "); } //每一种结果输出完毕 if(countA % (Q*Q) == 0) { countB++; System.out.println("第"+countB+"种方案输出完毕！"); } } } public static List<String> solveNQueens(int n){ res.clear(); //对col进行初始化 col = new boolean[n]; //对dir1进行初始化 dir1 = new boolean[2*n-1]; //对dir2进行初始化 dir2 = new boolean[2*n-1]; //定义动态数组row,将结果存在动态数组中 ArrayList<Integer> row = new ArrayList<>(); putQueue(n, 0, row); return res; } /** * 尝试在n皇后的问题中，摆放第index行的皇后位置 * @param n n皇后 * @param index 第index行 * @param row 结果存在row[]中 */ private static void putQueue(int n, int index, ArrayList<Integer> row) { if(index == n) { String[][] board = new String[n][n]; for(int i=0;i<n;i++) { board[i][row.get(i)] = "Q"; } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(board[i][j] == null) { board[i][j] = "-"; } res.add(board[i][j]); } } return; } for(int i=0;i<n;i++) { //尝试将第index行 if(!col[i] && !dir1[index+i] && !dir2[index-i+n-1]) {//如果均不冲突 row.add(i);//第index行元素摆放在第i个位置 col[i] = true;//该列不能再有元素 dir1[index+i] = true;//对角线1不能再有元素 dir2[index-i+n-1] = true;//对角线2不能再有元素 //递归 putQueue(n, index+1, row); //回溯 col[i] = false; dir1[index+i] = false; dir2[index-i+n-1] = false; row.remove(row.size()-1); } } return; } }

程序输出结果如下：

- Q - -
- - - Q
Q - - -
- - Q -
第1种方案输出完毕！
- - Q -
Q - - -
- - - Q
- Q - -
第2种方案输出完毕！