一、基本概念
1.N皇后问题是由国际象棋8皇后问题引申过来的，在国际象棋中有8行8列的棋盘，其中皇后的前进路线为：横、纵、以及双斜线，为了使皇后之间互不冲突，就要摆放皇后，使之前进路线不重叠。
如下所示就是一个8皇后问题的解决方案，如图可以验证，各个皇后之间互不冲突：
Q . . . . . . . . . . . Q . . . . . . . . . . Q . . . . . Q . . . . Q . . . . . . . . . . . Q . . Q . . . . . . . . . Q . . . .
2.由此引申到N皇后问题，借用leetcode 51的问题解决该问题
二、问题解析：
/*51. N皇后 n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例:
输入: 4 输出: [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."],
["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ] 解释: 4 皇后问题存在两个不同的解法。 * * */
分析
逐行摆放皇后的过程中的，如何判断某一个位置不能再摆放位置？
1.使用一维数组，标记某一行、某一列是否被占用
private boolean[] col;
如果有皇后摆放在第一行或者第一列，则col[1]==true
2.标记两个对角线，这里涉及到两个小技巧
（1）右上：同一对角线相加为同一个数
（2）左下：同一对角线相加为同一个数
为了使其数组下标从0开始，需要在加上n-1;
三、代码及注释
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;
public class Solution {
private boolean[] col;
private boolean[] dia1;
private boolean[] dia2;
private ArrayList<List<String>> res;
public List<List<String>> solveNQueens(int n) {
res = new ArrayList<List<String>>();
col = new boolean[n];
dia1 = new boolean[2 * n - 1];
dia2 = new boolean[2 * n - 1];
LinkedList<Integer> row = new LinkedList<Integer>();
putQueen(n, 0, row);
return res;
}
// 尝试在一个n皇后问题中, 摆放第index行的皇后位置
private void putQueen(int n, int index, LinkedList<Integer> row){
if(index == n){
res.add(generateBoard(n, row));
return;
}
for(int i = 0 ; i < n ; i ++)
// 尝试将第index行的皇后摆放在第i列
if(!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]){
row.addLast(i);
col[i] = true;
dia1[index + i] = true;
dia2[index - i + n - 1] = true;
putQueen(n, index + 1, row);
col[i] = false;
dia1[index + i] = false;
dia2[index - i + n - 1] = false;
row.removeLast();
}
return;
}
private List<String> generateBoard(int n, LinkedList<Integer> row){
assert row.size() == n;
ArrayList<String> board = new ArrayList<String>();
for(int i = 0 ; i < n ; i ++){
char[] charArray = new char[n];
Arrays.fill(charArray, '.');
charArray[row.get(i)] = 'Q';
board.add(new String(charArray));
}
return board;
}
private static void printBoard(List<String> board){
for(String s: board)
System.out.println(s);
System.out.println();
}
public static void main(String[] args) {
int n = 4;
List<List<String>> res = (new Solution()).solveNQueens(n);
for(List<String> board: res)
printBoard(board);
}
}
