JAVA - DFS clean - no tricks


  • 0
    D

    Building a chessboard row-by-row, this solution charges a straight forward DFS algorithm branching over all possible column positions to place the next queen in the next row. No funny indexing in the core of the algorithm. Checking board validity is O(n) by itself. Maybe there's a better way there.

    Without the fast-fail feature, the run failed to finish in time (but is still correct).

    public class Solution {
        
        public void solve(List<String> part, List<List<String>> result, int n) {
            /* part is a row by row ordering of queens. We build it down from the top.
            We will only allow valid rows to be added.
            
            As we finish traversing a branch, we pop the Queen and try the next position.
            And again DFSing downward.
            */
            
            if (part.size() == n) {
                result.add(new ArrayList<String>(part));
                return;
                
            } else {
                
                // iterate every possible Queen position in this row.
                for (int pos = 0; pos < n; pos++) {
                    char[] ch = new char[n];
            		Arrays.fill(ch, '.');
                    ch[pos] = 'Q';
                    
                    String row = new String(ch);
                    
                    if (isValid(part, row)) {
                        
                        // only valid solutions are allowed to build
                        part.add(row);
                    } else {
                        // fast fail this branch
                    	continue;
                    }
    
                     //dfs
                    solve(part, result, n);
                    
                    // pop this branch
                    part.remove(part.size() -1 );
                }
            }
        }
        
        public boolean isValid(List<String> board, String row) {
    
        	int pos = row.indexOf("Q");
        	
    		for (int dist = 1, prev = board.size() - 1; prev >= 0; dist++, prev--) {
    		    
                String prevRow = board.get(prev);
    		    int prevPos = prevRow.indexOf("Q");
    		    
    			if (prevPos + dist == pos || prevPos - dist == pos || prevPos == pos) {
    				return false;
    			}
    		}
    
            return true;
        }
        
        public List<List<String>> solveNQueens(int n) {
    
            List<List<String>> result = new ArrayList<>();
            solve(new ArrayList<String>(), result, n);
            return result;
        }
    
    }
    

Log in to reply
 

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