0051. N-Queens

https://leetcode.com/problems/n-queens

Description

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

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

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 1:

**Input:** n = 4
**Output:** [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
**Explanation:** There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

**Input:** n = 1
**Output:** [["Q"]]

Constraints:

• 1 <= n <= 9

ac

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<List<String>>();

        List<char[]> board = new ArrayList<char[]>();
        char[] chars = new char[n];
        for (int i = 0; i < n; i++) chars[i] = '.';
        for (int i = 0; i < n; i++) board.add(chars.clone());

        Set<Integer> cSet = new HashSet<Integer>();

        backtrack(n, 0, cSet, board, res);

        return res;
    }
    private void backtrack(int n, int r, Set<Integer> cSet, List<char[]> board, List<List<String>> res) {
        if (r == n) {
            res.add(copyBoard(board));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!cSet.contains(i) && canPut(board, r, i)) {
                cSet.add(i);
                board.get(r)[i] = 'Q';
                backtrack(n, r+1, cSet, board, res);
                cSet.remove(i);
                board.get(r)[i] = '.';
            }
        }
    }
    private boolean canPut(List<char[]> board, int row, int col) {
        int r = row, c = col;
        while (r >= 0 && c >= 0) {
            if(board.get(r)[c] == 'Q') return false;
            r--;
            c--;
        }
        r = row;c = col;
        while (r >= 0 && c < board.get(0).length) {
            if(board.get(r)[c] == 'Q') return false;
            r--;
            c++;
        }
        return true;
    }
    private List<String> copyBoard(List<char[]> board) {
        List<String> r = new ArrayList<String>();
        for (int i = 0; i < board.size(); i++) {
            r.add(String.valueOf(board.get(i)));
        }
        return r;
    }
}