LeetCode 52 - N-Queen II

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

https://segmentfault.com/a/1190000003762668
We can use O(1) to detect is valid -> O(N^2)
https://leetcode.com/discuss/18411/accepted-java-solution
* don't need to actually place the queen, * instead, for each row, try to place without violation on * col/ diagonal1/ diagnol2. * trick: to detect whether 2 positions sit on the same diagnol: * if delta(col, row) equals, same diagnol1; * if sum(col, row) equals, same diagnal2. private final Set<Integer> occupiedCols = new HashSet<Integer>(); private final Set<Integer> occupiedDiag1s = new HashSet<Integer>(); private final Set<Integer> occupiedDiag2s = new HashSet<Integer>(); public int totalNQueens(int n) { return totalNQueensHelper(0, 0, n); } private int totalNQueensHelper(int row, int count, int n) { for (int col = 0; col < n; col++) { if (occupiedCols.contains(col)) continue; int diag1 = row - col; if (occupiedDiag1s.contains(diag1)) continue; int diag2 = row + col; if (occupiedDiag2s.contains(diag2)) continue; // we can now place a queen here if (row == n-1) count++; else { occupiedCols.add(col); occupiedDiag1s.add(diag1); occupiedDiag2s.add(diag2); count = totalNQueensHelper(row+1, count, n); // recover occupiedCols.remove(col); occupiedDiag1s.remove(diag1); occupiedDiag2s.remove(diag2); } } return count; }
https://discuss.leetcode.com/topic/26987/pretty-simple-java-solution/2

  Set<Integer> col = new HashSet<Integer>();
  Set<Integer> diag1 = new HashSet<Integer>();
  Set<Integer> diag2 = new HashSet<Integer>();

  public int totalNQueens(int n) {
    int[] res = new int[1];//\\
    helper(res,n,0);
    return res[0];
    
}
  public void helper(int[] res, int n, int row){
    if(row==n){
        res[0]++;
    }
    else{
        for(int i=0; i<n; i++){
            if(col.contains(i) || diag1.contains(i+row) || diag2.contains(row-i)) continue;
            else{
                col.add(i);
                diag1.add(i+row);
                diag2.add(row-i);
                helper(res,n,row+1);
                col.remove(i);
                diag1.remove(i+row);
                diag2.remove(row-i);
            }
         }
      }
   }

https://leetcode.com/discuss/18411/accepted-java-solution
https://leetcode.com/discuss/69603/easiest-java-solution-1ms-98-22%25

Start row by row, and loop through columns. At each decision point, skip unsafe positions by using three boolean arrays.

Start going back when we reach row n.

Just FYI, if using HashSet, running time will be at least 3 times slower!

    int count = 0;
    public int totalNQueens(int n) {
        boolean[] cols = new boolean[n];     // columns   |
        boolean[] d1 = new boolean[2 * n];   // diagonals \
        boolean[] d2 = new boolean[2 * n];   // diagonals /
        backtracking(0, cols, d1, d2, n);
        return count;
    }
    
    public void backtracking(int row, boolean[] cols, boolean[] d1, boolean []d2, int n) {
        if(row == n) count++;

        for(int col = 0; col < n; col++) {
            int id1 = col - row + n;
            int id2 = col + row;
            if(cols[col] || d1[id1] || d2[id2]) continue;
            
            cols[col] = true; d1[id1] = true; d2[id2] = true;
            backtracking(row + 1, cols, d1, d2, n);
            cols[col] = false; d1[id1] = false; d2[id2] = false;
        }
    }

int result = 0; public int totalNQueens(int n) { boolean[] column = new boolean[n]; boolean[] dia45 = new boolean[2 * n - 1]; boolean[] dia135 = new boolean[2 * n - 1]; helper(0, n, column, dia45, dia135); return result; } private void helper(int row, int n, boolean[] column, boolean[] dia45, boolean[] dia135) { if (row == n) { result++; return; } for (int col = 0; col < n; col++) { if (!column[col] && !dia45[col + row] && !dia135[n - 1- row + col]) { column[col] = dia45[col + row] = dia135[n - 1- row + col] = true; helper(row + 1, n, column, dia45, dia135); column[col] = dia45[col + row] = dia135[n - 1- row + col] = false; } } }

Just FYI, if using HashSet, running time will be at least 3 times slower!

int count = 0; public int totalNQueens(int n) { boolean[] cols = new boolean[n]; // columns | boolean[] d1 = new boolean[2 * n]; // diagonals \ boolean[] d2 = new boolean[2 * n]; // diagonals / backtracking(0, cols, d1, d2, n); return count; } public void backtracking(int row, boolean[] cols, boolean[] d1, boolean []d2, int n) { if(row == n) count++; for(int col = 0; col < n; col++) { int id1 = col - row + n; int id2 = col + row; if(cols[col] || d1[id1] || d2[id2]) continue; cols[col] = true; d1[id1] = true; d2[id2] = true; backtracking(row + 1, cols, d1, d2, n); cols[col] = false; d1[id1] = false; d2[id2] = false; } }
https://leetcode.com/discuss/6764/my-iterative-solution-for-reference-bit-wise-operation
https://discuss.leetcode.com/topic/38923/share-my-java-code-beats-97-83-run-times

    常规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)位.
    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);
            }
        }
    }

X. BitMap
https://leetcode.com/discuss/743/whats-your-solution

And a picture to illustrate how the bits projection works. 

/* backtrace program using bit-wise operation to speed up calculation. * 'limit' is all '1's. * 'h' is the bits all the queens vertically projected on a row. If h==limit, then it's done, answer++. * 'r' is the bits all the queens anti-diagonally projected on a row. * 'l' is the bits all the queens diagonally projected on a row. * h|r|l is all the occupied bits. Then pos = limit & (~(h|r|l)) is all the free positions. * p = pos & (-pos) gives the right most '1'. pos -= p means we will place a queen on this bit * represented by p. * 'h+p' means one more queue vertically projected on next row. * '(r+p)<<1' means one more queue anti-diagonally projected on next row. Because we are * moving to next row and the projection is skew from right to left, we have to * shift left one position after moved to next row. * '(l+p)>>1' means one more queue diagonally projected on next row. Because we are * moving to next row and the projection is skew from left to right, we have to * shift right one position after moved to next row. */ int totalNQueens(int n) { ans = 0; limit = (1<<n) - 1; dfs(0, 0, 0); return ans; } void dfs(int h, int r, int l) { if (h == limit) { ans++; return; } int pos = limit & (~(h|r|l)); while (pos) { int p = pos & (-pos); pos -= p; dfs(h+p, (r+p)<<1, (l+p)>>1); } } int ans, limit;
TODO: http://gregtrowbridge.com/a-bitwise-solution-to-the-n-queens-problem-in-javascript/
X. O(N^3)
http://www.jiuzhang.com/solutions/n-queens-ii/

    public static int sum;
    public int totalNQueens(int n) {
        sum = 0;
        int[] usedColumns = new int[n];
        placeQueen(usedColumns, 0);
        return sum;
    }
    public void placeQueen(int[] usedColumns, int row) {
        int n = usedColumns.length;
        
        if (row == n) {
            sum ++;
            return;
        }
        
        for (int i = 0; i < n; i++) {
            if (isValid(usedColumns, row, i)) {
                usedColumns[row] = i;
                placeQueen(usedColumns, row + 1);
            }
        }
    }
    public boolean isValid(int[] usedColumns, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (usedColumns[i] == col) {
                return false;
            }
            if ((row - i) == Math.abs(col-usedColumns[i])) {
                return false;
            }
        }
        return true;
    }

https://leetcode.com/discuss/80764/collection-of-solutions-in-java

Eight Queens:Write an algorithm to print all ways of arranging eight queens on an 8x8 chess board

so that none of them share the same row, column, or diagonal. In this case, "diagonal" means all

diagonals, not just the two that bisect the board.

int GRID_SIZE = 8;

void placeQueens(int row, Integer[] columns, Arraylist<Integer[]> results) {
        if (row == GRID_SIZE) {//Found valid placement
                results.add(columns.clone());
        } else {
                for (int col= 0; col< GRID_SIZE; col++) {
                        if (checkValid(columns, row, col)) {
                                columns[row] = col; // Place queen
                                placeQueens(row + 1, columns, results);
                        }
                }
        }
}

/* Check if (rowl, column!) is a valid spot for a queen by checking if there is a
 * queen in the same column or diagonal. We don't need to check it for queens in
 * the same row because the calling placeQueen only attempts to place one queen at
 * a time. We know this row is empty. */
boolean checkValid(Integer[] columns, int rowl, int column1) {
        for (int row2 = 0; row2 < rowl; row2++) {
                int column2 = columns[row2];
                /* Check if (row2, column2) invalidates (rowl, columnl) as a
                 * queen spot. */

                /* Check if rows have a queen in the same column */
                if (columnl == column2) {
                        return false;
                }

                /* Check diagonals: if the distance between the columns equals the distance
                 * between the rows, then they're in the same diagonal. */
                int columnDistance = Math.abs(column2 - columnl);

                /* rowl > row2, so no need for abs */
                int rowDistance = rowl - row2;
                if (columnDistance == rowDistance) {
                        return false;
                }
        }
        return true;
}
Read full article from Just Codings: [LeetCode] N-Queens I && II