Java with one array


  • 0
    T

    Array board[] represents the columns in the chess board. The value at each index represents the row the queen is placed in that column.

    To check diagonals, simply find the difference between the two rows and two columns. If these differences equal each other, then they are in the same diagonal. Essentially, if the slope of these two points is +/- 1.

    public class Solution {
        public int totalNQueens(int n) {
            int[] board = new int[n];
            return totalUtil(n, 0, board);
        }
        
        private int totalUtil(int n, int col, int[] board) {
            if (col == n) return 1;
            
            int ways = 0;
            for (int i = 0; i < n; i++) {
                if (canPlace(col, i, board)) {
                    board[col] = i;
                    ways += totalUtil(n, col+1, board);
                }
            }
            return ways;
        }
      
        private boolean canPlace(int col1, int row1, int[] board) {
            for (int col2 = 0; col2 < col1; col2++) {
                int row2 = board[col2];
                int colDiff = col1 - col2;
                int rowDiff = Math.abs(row1 - row2);
                if (row1 == row2 || colDiff == rowDiff) return false;
            }
            return true;
        }
    }
    

Log in to reply
 

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