51. N-Queens

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.."]
]

Solution:

This is a classic DFS problem.

We recursively insert a queen to a row and check if the board is still valid.

To record the status, we know each row only has one queen, and each column only has one queen.

We use an col[] array and use col[i] to denote which column we insert the queen in row i.

Therefore, when we try to insert a queen in the current row, we can check if a column j has already been used.

To check diagonal attack, we check if Math.abs(col[row2] - col[row1]) == row2 - row1.



Code:

public class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        if (n <= 0) {
            return result;
        }
        int[] col = new int[n];
        helper(n, result, 0, col);
        return result;
    }
    
    public void helper(int n, List<List<String>> result, int row, int[] col) {
        if (row == n) {
            List<String> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                StringBuilder s = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    if (j == col[i]) {
                        s.append("Q");
                    }
                    else {
                        s.append(".");
                    }
                }
                list.add(s.toString());
            }
            result.add(list);
        }
        else {
            for (int i = 0; i < n; i++) {
                col[row] = i;
                if (isValid(row, col)) {
                    helper(n, result, row + 1, col);
                }
            }
        }
    }
    
    public boolean isValid(int row, int[] col) {
        for (int i = 0; i < row; i++) {
            if (col[row] == col[i] || Math.abs(col[row] - col[i]) == row - i) {
                return false;
            }
        }
        return true;
    }
}