Fast, short, and easy-to-understand python solution, 11 lines, 76ms


  • 44
    C

    ideas:

    Use the DFS helper function to find solutions recursively. A solution will be found when the length of queens is equal to n ( queens is a list of the indices of the queens).


    In this problem, whenever a location (x, y) is occupied, any other locations (p, q ) where p + q == x + y or p - q == x - y would be invalid. We can use this information to keep track of the indicators (xy_dif and xy_sum ) of the invalid positions and then call DFS recursively with valid positions only.

    At the end, we convert the result (a list of lists; each sublist is the indices of the queens) into the desire format.

    def solveNQueens(self, n):
        def DFS(queens, xy_dif, xy_sum):
            p = len(queens)
            if p==n:
                result.append(queens)
                return None
            for q in range(n):
                if q not in queens and p-q not in xy_dif and p+q not in xy_sum: 
                    DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])  
        result = []
        DFS([],[],[])
        return [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]

  • 0

    Thank you very much for your solution, especially for your explanation.


  • 0
    L

    I have a 88ms solution, but your solution is really really nice.


  • 0
    C

    Thank you so much for your explanation.


  • 0
    T

    Thank you for your nice solution. My iterative solution, anyone can help me improve it?

    def solveNQueens(self, n):
            results = [[]]
            for i in range(n):
                tmp = []
                for ares in results:
                    newLine = [' '] * n
                    for ki, kj in enumerate(ares):
                        newLine[kj] = '.'
                        if 0 <= ki + kj - i < n:  newLine[ki + kj - i] = '.' # i + j == ki + kj
                        if 0 <= i + kj - ki < n:  newLine[i + kj - ki] = '.' # j - i == kj - ki
    
                    for j in range(n):
                        if newLine[j] == '.': continue
                        tmp.append(ares+[j])
                results = tmp
            return [['.'*j + 'Q' + '.'*(n-j-1) for j in ares] for ares in results]

  • 0
    R

    Great solution.

    It could be faster if you use set.


  • 0
    V

    @rockkoca have you tried it? my solution using set and OrderDict is way slower than using lists


  • 0
    V

    @cmc p + q == x + y or p - q == x - y This is amazing observation. You are the man :)


  • 0
    S

    Thanks for your great solution! I tried to replicate your logic in Java but it doesn't seem to work and I couldn't figure out why. Any help is greatly appreciated!

    import java.util.*;
    public class NQueensSolution {
        List<List<String>> solutions = new ArrayList<List<String>>();
        public List<List<String>> solveNQueens(int n) {
            searchValidLocation(n, new HashSet<>(), new HashSet<>(), new HashSet<>());
    
         return solutions;
        }
        public void searchValidLocation (int n, HashSet<Integer> queens, HashSet<Integer> xy_diff, HashSet < Integer > xy_sum){
            int p = queens.size();
            if(p == n){
                ArrayList<String> solution = new ArrayList<>();
                for(int q : queens){
                    StringBuilder myStr = new StringBuilder();
                    for(int i = 0; i < n; i++){
                        if(i == q){
                            myStr.append('Q');
                        } else {
                            myStr.append('.');
                        }
                    }
                    System.out.println(myStr);
                    solution.add(myStr.toString());
                }
                solutions.add(solution);
                return;
            }
            for (int q = 0; q < n; q++) {
                if(!queens.contains(q) && !xy_diff.contains(p - q) && !xy_sum.contains(p + q)){
                    queens.add(q);
                    xy_diff.add(p - q);
                    xy_sum.add(p + q);
                    searchValidLocation(n, queens, xy_diff, xy_sum);
                }
            }
        }
    }
    

  • 0
    U

    p + q == x + y or p - q == x - y would be invalid

    Isn't it too weak?
    Consider any p==x OR q==y OR abs( p - q ) == abs ( x - y ) to be invalid?!


  • 0
    D
    This post is deleted!

  • 0
    J

    Isn't it too weak?
    Consider any p==x OR q==y OR abs( p - q ) == abs ( x - y ) to be invalid?!

    @universedark
    use "p + q == x + y or p - q == x - y" is fine. "p - q == x - y" is used to check no other queens on diagonal 1 (left top to right bottom), and "p + q == x + y" for diagonal 2 (right top to left bottom).

    and the list queens, can make sure every col/row only contains one queen.


Log in to reply
 

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