题目描述

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

示例

Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where'Q'and'.'both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]

• 思路
  求n皇后问题的所有解。
  每行每行遍历，用一个一维数组统计每行的哪列放置皇后棋子，再进行合法性检验（每列不重复，斜线上不重复），当最后一行结束时保存数据。
  参考博客

import java.util.*;
public class Solution {
    public ArrayList<String[]> solveNQueens(int n) {
        ArrayList<String[]> list = new ArrayList<String[]>();
        if(n <= 0)
            return list;
        
        int[] rowToCol = new int[n];
        getAns(0, n, rowToCol, list);
        
        return list;
    }
    
    public void getAns(int row, int n, int[] rowToCol, ArrayList<String[]> list){
        if(row == n){
            String[] strs = new String[n];
            for(int i=0; i<n; i++){
                StringBuilder str = new StringBuilder();
                for(int j=0; j<n; j++){
                    if(rowToCol[i] == j)
                        str.append('Q');
                    else
                        str.append('.');
                }
                strs[i] = str.toString();
            }
            list.add(strs);
            return ;
        }
        
        for(int i=0; i<n; i++){
            rowToCol[row] = i;
            if(isFit(row, rowToCol))
                getAns(row+1, n, rowToCol, list);
        }
    }
    
    public boolean isFit(int row, int[] rowToCol){
        for(int i=0; i<row; i++){ //对已填行进行判断
            //排除同一列上的 和 同一斜线上的
            if(rowToCol[row] == rowToCol[i] ||
              Math.abs(rowToCol[row] - rowToCol[i]) == Math.abs(row - i))
                return false;
        }
        return true;
    }
}