Fast and Concise Java Code 6ms


  • 1
    M

    The idea is no different with others but there is some optimization during the backtracking. The solution is easy to understand so please direct to the code.

    public class Solution {
        public List<List<String>> solveNQueens(int n) {
            int[] board = new int[n];
            for (int i = 0; i < n; ++i) board[i] = i; // Trick 1: Using 1d array, the value represents column. Fill every row with different column value, so you don't need to check whether row and row, column and column has conflicts. Only to check the diagonal elements.
            List<List<String>> res = new ArrayList<>();
            char[] rowStr = new char[n]; // Trick 2: Using a prepared char array to construct a row of the board.
            Arrays.fill(rowStr, '.');
            permute(board, 0, res, rowStr);
            return res;
        }
        
        public void permute(int[] board, int start, List<List<String>> res, char[] rowStr) {
            if (start == board.length) {
                res.add(construct(board, rowStr));
                return;
            }
            for (int i = start; i < board.length; ++i) {
                int tmp = board[start];
                board[start] = board[i];
                board[i] = tmp;
                if (check(board, start)) { // Check the validness before recursion
                    permute(board, start+1, res, rowStr);
                }
                tmp = board[start];
                board[start] = board[i];
                board[i] = tmp;
            }
        }
        
        public boolean check(int[] board, int row) {
            for (int i = row-1; i >= 0; --i) {
                if (row-i == Math.abs(board[row]-board[i])) return false;
            }
            return true;
        }
        
        public List<String> construct(int[] board, char[] rowStr) {
            List<String> res = new ArrayList<>();
            for (int i : board) {
                rowStr[i] = 'Q';
                res.add(new String(rowStr));
                rowStr[i] = '.'; // Remember to replace '.' back for future use
            }
            return res;
        }
    }
    

Log in to reply
 

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