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

• 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]``````

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

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

• Thank you so much for your explanation.

• 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]``````

• Great solution.

It could be faster if you use set.

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

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

• 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);
}
return;
}
for (int q = 0; q < n; q++) {
if(!queens.contains(q) && !xy_diff.contains(p - q) && !xy_sum.contains(p + q)){
searchValidLocation(n, queens, xy_diff, xy_sum);
}
}
}
}
``````

• 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?!

• This post is deleted!

• 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.

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