Pretty straight forward, Neat and Modular DFS based solution in Java with comments.


  • 0
    P

    This was not a hard ques. but optimizing it is certainly a hard task. But I think this solution is pretty acceptable in most interviews and it won't take too long to code once you know the algorithm!

            public List<List<String>> solveNQueens(int n) { // DFS based recursive solution !
    		List<List<String>> res = new ArrayList<List<String>>();
    		char[][] board = new char[n][n];
    		for(int i = 0 ; i < n; i++)
    			Arrays.fill(board[i], '.');
    		dfs(res, board, 0, n);
    		return res;
    
    	}
    
    	private void dfs(List<List<String>> res, char[][] board, int col, int n) {
    		if (col == n) {
    			List<String> temp = charToList(board, n);
    			res.add(temp);
    			return;
    		}
    
    		for (int i = 0; i < n; i++) {
    			if (isSafe(board, i, col))  {
    				board[i][col] = 'Q'; // Easy recursion.
    				dfs(res, board, col + 1, n);
    				board[i][col] = '.'; // Put back '.' after the solution is found or not after recursion.
    			}
    					
    		}
    
    	}
    	private List<String> charToList (char[][] board, int n) { // convert char board to List as required.
    		List<String>  res = new ArrayList<>();
    		
    		for(int i = 0; i < n; i++) {
    			String str = "";
    			for(int j = 0 ; j < n; j++) {
    				str += board[i][j]; // 1 String per row.
    			}
    			res.add(str);
    		}
    				
    		
    		return res;
    	}
    
    	private boolean isSafe(char[][] board, int i, int j) {
    		int ldiag = i - 1, rdiag = i + 1; // Two diagnols check.
    		for (int col = j - 1; col >= 0; col--, ldiag--, rdiag++) { // Some math stuff but if you think about it, it will make sense.
    			if (ldiag >= 0 && board[ldiag][col] == 'Q' || rdiag  < board[0].length && board[rdiag][col] == 'Q')
    				return false;
    		}
    		for (int x = 0, y = 0; x < i || y < j; x++, y++) { // same row and column check.
    			if (x < i && board[x][j] == 'Q')
    				return false;
    			if (y < j && board[i][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.