My dfs based 248ms solution in java


  • 0
    M
    public class Solution {
    	List<List<String>>result;
        public List<List<String>> solveNQueens(int n) {
        	char board[][]=new char[n][n];
        	result=new ArrayList<List<String>>();
        	for(int i=0;i<n;i++){
        		Arrays.fill(board[i], '.');
        	}
        	dfs(board,0,0);
        	return result;
            
        }
        private void dfs(char[][]board,int row,int col){
        	
        	if(col==board.length){
        		result.add(getList(board));
        	}
        	for(int i=row;i<board.length;i++){
        			if(isSafe(board,i,col))
        			{
        				board[i][col]='Q';
        				dfs(board,row,col+1);   //if it is safe to put queen at board[row][col], we now need to find safe position for next column.
        				board[i][col]='.';
        			}
        		
        	}
      
        }
        /* The following function will return true if its safe to put the Queen at board[row][col]
        */
        private boolean isSafe(char board[][],int row,int col){
        	if(col>=board.length)
        		return false;
        	for(int i=0;i<board.length;i++){
        		for(int j=0;j<col;j++){
        			if(board[i][j]=='Q'&&(i==row||row+col==i+j||row-col==i-j)) //Return false if a quuen is already present in another row for same col, or in any diagnal passing through board[row][col]
        				return false;
        		}
        	}
        	return true;
        	
        }
        /* The following function will get List of Strings from the 2-D array board. 
        */
        private List<String> getList(char[][]board)
        {
        	List<String> list=new ArrayList<String>();
        	for(int i=0;i<board.length;i++){
        		list.add(new String(board[i]));
        	}
        	return list;
        }
    

    }


Log in to reply
 

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