N皇后问题（递归加回溯）

N皇后问题递归加回溯

N皇后问题是把N个皇后放在一个N×N棋盘上，使皇后之间不会互相攻击。

给出一个整数n，返回n皇后问题的所有摆放方案
例如输入4
返回[↵ [".Q..", ↵ "...Q",↵ "Q...",↵ "..Q."],↵↵ ["..Q.", ↵ "Q...",↵ "...Q",↵ ".Q.."]↵]

import java.util.*;
public class Solution {
    public ArrayList<String[]> solveNQueens(int n) {
        ArrayList<String[]> result = new ArrayList<String[]>();
        //存放每个皇后的位置，索引为第几排，值为放在第几个位置
        int[] queen = new int[n];
        helper(n, 0, result, queen);
        return result;
    }

     private void helper(int n, int rowNum, ArrayList<String[]> result, int[] queen) {
        //说明走通了存储题目要求格式
        if (rowNum == n) {
            ArrayList<String> oneResult = new ArrayList<String>();
            // Current chess board is valid
            for (int i = 0; i < n; i++) {
                StringBuilder sb = new StringBuilder(n);
                int tmp = n;
                while (tmp > 0) {
                    sb.append(".");
                    tmp--;
                }
                int column = queen[i];
                sb.replace(column, column + 1, "Q");
                oneResult.add(sb.toString());
            }
            String[] answer=new String[oneResult.size()];
            int index=0;
            for(String line : oneResult)
                answer[index++]=line;
            result.add(answer);
            return;
        }
        //在这里进行回溯加递归，为社么赋值了没有赋回原值是因为有了rowNum这个进行到了第几行，以前赋的值直接会被覆盖
        for (int i = 0; i < n; i++) {
            queen[rowNum] = i;
            if (check(rowNum, queen))
                helper(n, rowNum + 1, result, queen);
        }
    }
     //判断是否满足冲突条件
      private boolean check(int rowNum, int[] queen) {
        int colNum = queen[rowNum];
        for (int i = 0; i < rowNum; i++) {
            if (queen[i] == colNum || (queen[i] + i == colNum + rowNum) || (queen[i] - i == colNum - rowNum))
                return false;
        }
        return true;
    }
}