题目及测试

package pid051;
/*51. N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。示例 1：输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：输入：n = 1
输出：[["Q"]]提示：1 <= n <= 9
*/import java.util.List;public class main {public static void main(String[] args) {int[] testTable = {4,1,5,3,6,4};for (int ito : testTable) {test(ito);}}private static void test(int ito) {Solution solution = new Solution();List<List<String>> rtn;long begin = System.currentTimeMillis();System.out.print(ito+" ");		    System.out.println();//开始时打印数组rtn = solution.solveNQueens(ito);//执行程序long end = System.currentTimeMillis();	//System.out.println(ito + ": rtn=" + rtn);System.out.println( " rtn=" );for (int i = 0; i < rtn.size(); i++) {List<String> now=rtn.get(i);for(int j=0;j<now.size();j++){System.out.print(now.get(j)+" ");}System.out.println();}//打印结果几数组System.out.println();System.out.println("耗时：" + (end - begin) + "ms");System.out.println("-------------------");}}

解法1（成功，2ms，极快）

本题也是回溯算法的经典题目。N 皇后问题也是一个暴力穷举的问题。
其实题目可以改成，在每一行放置一个皇后，让这些皇后不能相互攻击。（因为每一行最多只有一个皇后）
我们可以先不考虑每一个皇后之间不能相互攻击的条件，如果要求每行只能放一个皇后，我们能否穷举出所有的放置方法？
考虑皇后之间相互攻击的问题
对于每一个格子进行计算分析能不能放置皇后，最后的代码实现会跳过这些格子，把皇后放在合法的位置上。
具体的，在每一个位置放置皇后，然后调用 backtrack 函数，进入下一行进行穷举进行判断
isValid 函数的逻辑
按照题意我们需要检查八个方向是否有其他方向，但实际上我们只需要检查三个方向即可。
因为我们的逻辑是每一行只放一个皇后，所以这个皇后的左边和右边不需要进行检查了。
因为我们是一行一行从上向下放置皇后，所以下方，左下方和右下方不会有皇后（还没放皇后）。
最后我们需要检查的只有上方、左上和右上三个方向。
斜方向45度，只需target-i=span，然后看target-queens[i]是否等于+-span即可。
函数 backtrack 依然像个在决策树上游走的指针，每个节点就表示在 board[row][col] 上放置皇后，通过 isValid 函数可以将不符合条件的情况剪枝。

package pid051;import java.util.ArrayList;
import java.util.List;class Solution {public List<List<String>> solveNQueens(int n) {List<List<String>> result = new ArrayList<>();if(n<=0){return null;}int[] nowQueens = new int[n];dfs(nowQueens,0,result);return result;}private void dfs(int[] nowQueens,int index,List<List<String>> result){if(index == nowQueens.length){result.add(createResult(nowQueens));return;}for(int i=0;i<nowQueens.length;i++){nowQueens[index]=i;if(testQueens(nowQueens,index)){dfs(nowQueens, index+1, result);}}}private boolean testQueens(int[] queens,int index){if(index == 0){return true;}int target = queens[index];for(int i=0;i<index;i++){int now = queens[i];if(now == target){return false;}int span = index-i;if(now+span==target){return false;}if(now-span==target){return false;}}return true;}private List<String> createResult(int[] nowQueens){List<String> result = new ArrayList<>();int length = nowQueens.length;for(int i=0;i<length;i++){StringBuilder nowBuilder = new StringBuilder();for(int j=0;j<nowQueens[i];j++){nowBuilder.append('.');}nowBuilder.append('Q');for(int j=nowQueens[i]+1;j<length;j++){nowBuilder.append('.');}result.add(nowBuilder.toString());}return result;}
}