51. N-Queens

Then-queens puzzle is the problem of placingnqueens on ann×nchessboard such that no two queens attack each other.

Given an integern, return all distinct solutions to then-queens puzzle.

Each solution contains a distinct board configuration of then-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.."]
]

思路：DFS

public class Solution {
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                board[i][j] = '.';
            }
        }

        List<List<String>> res = new ArrayList<List<String>>();
        List<String> temp = new ArrayList<String>();
        dfs(board,0,res,temp);
        return res;
    }

    public void dfs(char[][] board,int rowInd, List<List<String>> res, List<String> temp){
        if (rowInd==board.length){
            res.add(new ArrayList<String>(temp));
            return;
        }

        for (int i=0;i<board.length;i++){
            if (isValid(board,rowInd,i)){
                board[rowInd][i] = 'Q';
                String colStr = new String(board[rowInd]);
                temp.add(colStr);
                //System.out.println(colStr);
                dfs(board,rowInd+1,res,temp);
                board[rowInd][i] = '.';
                temp.remove(temp.size()-1);
            }
        }
    }

    public boolean isValid(char[][] board,int row,int col){
        for (int i=0;i<row;i++){
            for (int j=0;j<board.length;j++){
                if (board[i][j]=='Q'&&(row+j==col+i||row+col==i+j||col==j))
                    return false;
            }
        }
        return true;
    }
}