Share my straightforward java 4ms solution beats 93.36%----very easy to understand


  • 0
    S

    For each position on the board, it's easy to check row and column, for the two diagonals, if two positions are at the same diagonal then there must have x1+y1 = x2 + y2 or x2 - x1 = y2 - y1. We can use an boolean array col to remember whether current column is valid to put a queen, and as for the row, we can do the backtracking recursively row by row.

    public class Solution {
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++)
                board[i][j] = '.';
        }
        boolean[] col = new boolean[n];
        boolean[] diagonal_1 = new boolean[2*n-1];     //x1 + y1 = x2 + y2, we have 2*n-1 such diagonals 
        List<List<String>> res = new ArrayList<>();
        backtrack(res, 0, board, col, diagonal_1);
        return res;
    }
    
    public void backtrack(List<List<String>> res, int row, char[][] board, boolean[] col, boolean[] diagonal_1) {
        if(row == board.length) {
            List<String> ans = new ArrayList<>();
            for(int i = 0; i < board.length; i++)
                ans.add(String.valueOf(board[i]));
            res.add(ans);
            return;
        }
        
        for(int j = 0; j < board.length; j++) {
            if(!col[j] && !diagonal_1[row+j] && checkDiagonal_2(board, row, j)) {
                board[row][j] = 'Q';
                col[j] = true;
                diagonal_1[row+j] = true;
                backtrack(res, row+1, board, col, diagonal_1);
                board[row][j] = '.';
                col[j] = false;
                diagonal_1[row+j] = false;
            }
        }
    }
    
    /* check the diagonal which has the feature x1 - x2 = y1 - y2 */
    public boolean checkDiagonal_2(char[][] board, int x, int y) {
        int min = Math.min(x, y);
        x -= min;
        y -= min;
        while(x < board.length && y < board.length) {
            if(board[x++][y++] == 'Q')
                return false;
        }
        return true;
    }
    

    }


Log in to reply
 

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