N-Queens


#1

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

Example:

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

#2

The below code uses backtracking to find out all possible combinations of board’s where you can place queens that won’t attack each other. The rules are that you can’t have your queen in the same row, col, 'diagandant-diag`.

class Solution {
    int[][] neighbors = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] grid = new char[n][n];
        for(char[] row : grid) { 
            Arrays.fill(row, '.');
        }
        boolean[] rows = new boolean[n], cols = new boolean[n], diag45  = new boolean[2*n-1],diag135 = new boolean[2*n-1];
        backtrack(grid, rows, cols,diag45,diag135, 0, 0, result);
        return result;
    }
    
    void backtrack(char[][] grid, boolean[] rows, boolean[] cols,boolean[] diag45,boolean[] diag135, int row, int queens, List<List<String>> result){
        if(queens==grid.length) result.add(snapshot(grid));
        if(row>=grid.length) return;
        int i = row;
        for(int j=0;j<grid[0].length;j++){
            if(!rows[i] && !cols[j] && !diag45[i+j] && !diag135[grid.length-1-i+j]){
                grid[i][j] = 'Q';
                
                rows[i] = true; cols[j] = true; diag45[i+j] = true; diag135[grid.length-1-i+j] = true;
                backtrack(grid, rows, cols,diag45,diag135, i+1, queens+1, result);
                grid[i][j] = '.';
                rows[i] = false; cols[j] = false; diag45[i+j] = false; diag135[grid.length-1-i+j] = false;
            }
        }
    }
    
    List<String> snapshot(char[][] grid){
        List<String> snap = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for(char[] row : grid){
            sb.setLength(0);
            for(char val : row){
                sb.append(val);
            }
            snap.add(sb.toString());
        }
        
        return snap;
    }
}