51. N-Queens

Problem:

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.

Example:

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

Analysis:
Easy backtracking.
1. With 1d array to store the queens' positions, need to first initialize array to -1. queens[r] = c, c can be 0.
2. If two points are on the diagonal, then the abs of their rows and columns are equal.

Solution:

class Solution {
    List<List<String>> res;
    public List<List<String>> solveNQueens(int n) {
        res = new ArrayList<>();
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        dfs(queens, 0);
        return res;
    }
    
    // queens[r] = c; pos is column
    private void dfs(int[] queens, int row) {
        if (row == queens.length) {
            addSolution(queens);
            return;
        }
        
        for (int i = 0; i < queens.length; i++) {
            if (isValid(queens, row, i)) {            
                queens[row] = i;
                dfs(queens, row + 1);   
                queens[row] = -1;
            }
        }
    }
    
    private boolean isValid(int[] queens, int row, int col) {
        // i is row
        for (int i = 0; i < row; i++) {
            if (queens[i] == col)
                return false;
            else if (Math.abs(queens[i] - col) == Math.abs(row - i))
                return false;
        }
        return true;
    }
    
    private void addSolution(int[] queens) {
        List<String> list = new ArrayList<>();
        for (int r = 0; r < queens.length; r++) {
            StringBuilder sb = new StringBuilder();
            for (int c = 0; c < queens.length; c++) {
                if (queens[r] != c) {
                    sb.append('.');
                } else {
                    sb.append('Q');
                }
            }
            list.add(sb.toString());
        }
        res.add(list);
    }
}