Fairly intuitive backtracking


  • 0
    R
    public class Solution {
        
        int[] colPos;
        List<List<String>> total;
        
        public List<List<String>> solveNQueens(int n) {
            total = new ArrayList<List<String>>();
            colPos = new int[n+1];
            NQueen(1);
            return total;
        }
        
        public void addGame() {
            ArrayList<String> board = new ArrayList<String>();
            for (int r = 1; r < colPos.length; r++) {
                StringBuilder sb = new StringBuilder();
                for (int col = 1; col < colPos.length; col++) {
                    if (colPos[r] == col) {
                        sb.append("Q");
                    } else {
                        sb.append(".");
                    }
                }
                board.add(sb.toString());
            }
            total.add(board);
        }
    
        public void NQueen(int queen) {
            for (int col = 1; col < colPos.length; col++) {
                if (isValid(col, queen)) {
                    colPos[queen] = col;
                    if (queen == colPos.length-1) {
                        addGame();
                        break;
                    }  else {
                        NQueen(queen+1);
                    }  
                } 
            }
        }
        
        public boolean isValid(int col, int row) {
            for (int r = 1; r < row; r++) {
                if (colPos[r] == col || Math.abs(colPos[r]-col) == Math.abs(row-r))
                    return false;
            }
            return true;
        }
        
    }
    

Log in to reply
 

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