Java Solution using Backtracking [Accepted]


  • 0
    N

    Lets first start with what are the conditions that may cause two queens to contradict with each other on a chess board:

    1. If two queens are on the same row
    2. If two queens are on the same column
    3. If two queens are on the same diagonal, or in other words the difference between the rows of two queen position is equal to the difference between the columns of the two queens

    Also important thing to keep in mind is two queens are exactly the same object i.e. arrangement with Queen1 at position 0,0 and Queen2 at position 1,2 is the same thing as saying Queen2 at position 0,0 and Queen1 at position 1,2 as two queen objects are indistinguishable.

    With this in mind lets scratch out the first condition which may cause the queens to contradict i.e. the rows. We can simply avoid this by always starting with row 0 and increasing linearly. That way the queen at row 0 will merely change columns to find different valid arrangement and not change rows. This way we can always assume the Queen@i will be above Queen@i-1 and below Queen@i+1. Now with backtracking we simply keep on changing the columns for every queen in every row and see if the arrangement is valid.

    class Solution {
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> results = new ArrayList<List<String>>();
            // Sanity checks
            if(n == 0) {
                return results;
            }
            else if(n == 1) {
                List<String> list = new ArrayList<String>();
                list.add("Q");
                results.add(list);
                return results;
            }
            
            // Create a matrix representing board for easy look up of positions and we can change it to List<String> later
            String[][] matrix = new String[n][n];
            for(int i = 0; i < n; i++) {
                String[] t = new String[n];
                // Fill it up empty
                Arrays.fill(t, ".");
                matrix[i] = t;
            }
            
            solve(matrix, 0, results);
            return results;
        }
        
        private void solve(String[][] matrix, int row, List<List<String>> results) {
            if(row == matrix.length) {
                results.add(convert(matrix));
                return;
            }
            
            // Check every column to see if it is a valid position on the passed row
            for(int column = 0; column < matrix[0].length; column++) {
                if(!isValidPosition(matrix, row, column)) continue;
                matrix[row][column] = "Q";
                // We always pass the next row while recursing i.e. row + 1
                solve(matrix, row + 1, results);
                matrix[row][column] = ".";
            }
        }
        
        private boolean isValidPosition(String[][] matrix, int row, int col) {
            /*
            Since we are always starting with row 0 and increasing we need to only check for validity from 0 to row - 1 
            this way we ensured the first condition above will never happen.
            */
            for(int i = 0; i < row; i++) {
                // Ensuring the second condition of column is avoided
                if(matrix[i][col].equals("Q")) {
                    return false;
                }
                
                // Making sure the diagonals arent shared across two positions
                int rowDiff = Math.abs(row - i);
                if((col + rowDiff < matrix[0].length && matrix[i][col + rowDiff].equals("Q")) ||
                  (col - rowDiff >= 0 && matrix[i][col - rowDiff].equals("Q"))) {
                    return false;
                }
            }
            return true;
        }
        
        private List<String> convert(String[][] matrix) {
            List<String> list = new ArrayList<>();
            for(int i = 0; i < matrix.length; i++) {
                StringBuilder sb = new StringBuilder();
                for(int j = 0; j < matrix.length; j++) {
                    sb.append(matrix[i][j]);
                }
                list.add(sb.toString());
            }
            return list;
        }
    }
    

    The runtime of above code is O(n^2) and we cannot do better than that since we have to look at all positions.
    Space complexity is also O(n^2) but we can bring it down to O(N) as if u look carefully we actually dont need to store the whole representation of matrix since we know rows will never collide so all we need to store is the column positions of the queens insert until passed row index.


Log in to reply
 

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