051.md

51. N-Queens

Solution 1

// DFS
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList();
        List<String> cur = new ArrayList();
        _solve(n, 0, cur, ans);
        return ans;
    }

    private void _solve(int n, int row, List<String> cur, List<List<String>> ans) {
        if (row == n) {
            ans.add(new ArrayList<String>(cur));
            return;
        }
        for (int col = 0; col < n; col++) {
            String t = "";
            for (int i = 0; i < n; i++) {
                if (i == col)
                    t += 'Q';
                else
                    t += '.';
            }
            cur.add(t);
            if(_isValid(cur))
                _solve(n, row + 1, cur, ans);
            cur.remove(cur.size() - 1);
        }
    }

    private boolean _isValid(List<String> cur) {
        int col = cur.size() - 1;
        int ind = cur.get(col).indexOf('Q');
        for (int i = 0; i < col; i++) {
            int diff = Math.abs(cur.get(i).indexOf('Q') - ind);
            if (diff == 0 || diff == col - i)
                return false;
        }
        return true;
    }
}