51. N皇后

class Solution {
    int count;
    List ls;
    int n;
    boolean bool[][];

    public List<List<String>> solveNQueens(int n) {
        count = 0;
        ls = new LinkedList();
        bool = new boolean[n][n];
        this.n = n;
        dfs(0);
        return ls;
    }

    private void dfs(int x) {
        if (x == n) {
            ArrayList<String> path = new ArrayList<String>();
        
            for(int i = 0 ; i < n ; i++) {
                StringBuffer stb = new StringBuffer("");
                for(int j = 0 ; j < n ; j++) {
                if(bool[i][j] == true )
                    stb.append("Q");
                else stb.append(".");
                }
                path.add(stb.toString());
            }
            ls.add(path);
            return;
        }
        for (int i = 0; i < n; i++) {
            int temp = x;
            int flag = 0;
            while (temp >= 0) {
                if((i+flag<n&&bool[temp][i+flag])||(i-flag>=0&&bool[temp][i-flag])||bool[temp][i])break;
                temp--;
                flag++;
            }
            if(temp==-1) {
                bool[x][i] = true;
                dfs(x+1);
                bool[x][i] = false;
            }
        }
    }
}