Share my Java code (beats 97.83% run times)


  • 13
    M
    /*
        常规n-queens解法, 数答案个数.
        用column标记此行之前的哪些column已经放置了queen. 棋盘坐标(row, col)对应column的第col位(LSB --> MSB, 下同).
        用diag标记此位置之前的哪些主对角线已经放置了queen. 棋盘坐标(row, col)对应diag的第(n - 1 + row - col)位.
        用antiDiag标记此位置之前的哪些副对角线已经放置了queen. 棋盘坐标(row, col)对应antiDiag的第(row + col)位.
    */
    public class Solution {
        int count = 0;
        
        public int totalNQueens(int n) {
            dfs(0, n, 0, 0, 0);
            return count;
        }
        
        private void dfs(int row, int n, int column, int diag, int antiDiag) {
            if (row == n) {
                ++count;
                return;
            }
            for (int i = 0; i < n; ++i) {
                boolean isColSafe = ((1 << i) & column) == 0;
                boolean isDiagSafe = ((1 << (n - 1 + row - i)) & diag) == 0;
                boolean isAntiDiagSafe = ((1 << (row + i)) & antiDiag) == 0;
                if (isColSafe && isDiagSafe && isAntiDiagSafe) {
                    dfs(row + 1, n, (1 << i) | column, (1 << (n - 1 + row - i)) | diag, (1 << (row + i)) | antiDiag);
                }
            }
        }
    }

  • 0
    O

    Nice one. Efficient in space. Except the Chinese explanations.


  • 0
    M

    sorry for the inconvenience. i'll try using English next time.


  • 0
    W

    @mach7 your solution can not fit situation when n large than 32


Log in to reply
 

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