Clear and short solution in Java using bit masks [explanation in Mandarin]


  • 2
    M
    /*
        以一行为一个recursion level, 在这一行的每个位置尝试放置queen.
        queen不能和*之前*已经放置过的queen在同一列, 同一个对角线.
        -- y方向的bit mask显然, size为n. 自左向右对应从低位到高位.
        -- diagonal方向的bit mask size为2 * n - 1, 自上向下(对应从低位到高位)看所在的bit是n - 1 + row - col
        -- anti-diagonal方向的bit mask size为2 * n - 1, 自上向下(对应从低位到高位)看所在的bit是row + col
    */
    public class Solution {
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> ans = new ArrayList<>();
            if (n <= 0) return ans;
            char[][] board = new char[n][n];
            for (char[] row: board) Arrays.fill(row, '.');  // initially, all slots empty
            dfs(ans, board, 0, 0, 0, 0);
            return ans;
        }
        
        private void dfs(List<List<String>> ans, char[][] board, int row, long yMask, long diagMask, long antiDiagMask) {
            int n = board.length;
            if (row == n) {
                List<String> curAns = new ArrayList<>();
                for (char[] sArr: board) curAns.add(new String(sArr));
                ans.add(curAns);
                return;
            }
            for (int col = 0; col < n; ++col) {  // try each position (col) at current level (row)
                boolean yValid = (yMask & (1 << col)) == 0;
                boolean diagValid = (diagMask & (1 << (n - 1 + row - col))) == 0;
                boolean antiDiagValid = (antiDiagMask & (1 << (row + col))) == 0;
                if (yValid && diagValid && antiDiagValid) {
                    board[row][col] = 'Q';
                    dfs(ans, board, row + 1, yMask | (1 << col), diagMask | (1 << (n - 1 + row - col)), 
                        antiDiagMask | (1 << (row + col)));
                    board[row][col] = '.';
                }
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.