My Simple Java Solution


  • 2
    R
    public class Solution {
        public List<List<String>> solveNQueens(int n) {
            List result = new ArrayList();
            if (n <= 0) {
                return result;
            }
            
            search(n, result, new ArrayList<Integer>());
            return result;
        }
        
        private void search(int n, List result, List<Integer> cols) {
            if (cols.size() == n) {
                result.add(printChessBoard(cols));
                return;
            }   
            
            for (int col = 0; col < n; col++) {
                if (!isValid(cols, col)) {
                    continue;
                }
                cols.add(col);
                search (n, result, cols);
                cols.remove(cols.size() - 1);
            }
        }
        
        private boolean isValid(List<Integer> cols, int col) {
            int row = cols.size();
            for (int i = 0; i < row; i++) {
                // same column
                if (col == cols.get(i)) {
                    return false;
                }
                // left-top to right-bottom
                if (row - i == col - cols.get(i)) {
                    return false;
                }
                // right-top to left-bottom
                if (i - row == col - cols.get(i)) {
                    return false;
                }
            }
            return true;
        }
        
        private List<String> printChessBoard (List<Integer> cols) {
            
            int n = cols.size();
            List<String> solution = new ArrayList<String>();
            
            for (int i = 0; i < n; i++) {
                int col = cols.get(i);
                char[] chars = new char[n];
                for (int j = 0; j < n; j++) {
                    if ( j == col) {
                        chars[j] = 'Q';
                    } else {
                        chars[j] = '.';
                    }
                }
                solution.add(String.valueOf(chars));
            }
            
            return solution;
        }
    }

Log in to reply
 

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