KK's blog

每天积累多一些

0%

LeetCode 051 N-Queens

Posted on Edited on Disqus:

LeetCode

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.



Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.



Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space, respectively.



 


Example 1:



Input: n = 4
Output: [[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above


Example 2:



Input: n = 1
Output: [[“Q”]]


 


Constraints:




  • 1 <= n <= 9


题目大意：

八皇后问题，求所有解

Global dict算法思路(推荐)：

DFS填位法模板

注意事项：

  1. 用3个set，col_set, 对角线，反对角线set来提高效率。
  2. path用append的方法加入，这样终止条件用n来比较，不能用len(path)
  3. 打印函数中，one_result在每轮后reset；字符串不能改其中一个，只能用子串+Q+子串： (‘.’ path[i]) + ‘Q’ + (‘.’ (n - path[i] - 1))

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def solveNQueens(self, n: int) -> List[List[str]]:
	res, path = [], []
	self.dfs(n, 0, path, res, set(), set(), set())
	result = self.convert(res)
	return result

def dfs(self, n, start, path, res, col_set, diag_set, anti_diag_set):
	if start == n: # remember not len(path)
		res.append(list(path))
		return
	for i in range(n): # 4
		if not self.is_valid(start, i, col_set, diag_set, anti_diag_set):
			continue
		path.append(i)  # [0, 2]
		col_set.add(i)
		diag_set.add(start - i)
		anti_diag_set.add(start + i)
		self.dfs(n, start + 1, path, res, col_set, diag_set, anti_diag_set)
		anti_diag_set.remove(start + i)
		diag_set.remove(start - i)
		col_set.remove(i)
		path.pop()

def is_valid(self, i, val, col_set, diag_set, anti_diag_set):
	if val in col_set or i - val in diag_set or i + val in anti_diag_set:
		return False
	return True

算法分析：

时间复杂度为O(n!)，空间复杂度O(n^2)

常数空间算法II解题思路(推荐)：

较直观的方法，但复杂度稍差

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def solveNQueens2(self, n: int) -> List[List[str]]:
	res, path = [], []
	self.dfs2(n, 0, path, res)
	result = self.convert(res)
	return result

def dfs2(self, n, start, path, res):
	if start == n: # remember not len(path)
		res.append(list(path))
		return
	for i in range(n): # 4
		path.append(i) # [0, 2]
		if self.is_valid2(path):
			self.dfs2(n, start + 1, path, res)
		path.pop()

def is_valid2(self, path):
	if len(path) != len(set(path)):
		return False
	for i in range(len(path)):
		for j in range(i + 1, len(path)):
			#if i == j:
			 #   continue
			if abs(i - j) == abs(path[i] - path[j]):
				return False
	return True

def convert(self, res):
	result, one_result = [], []
	for k in range(len(res)):
		one_result = [] # remember
		path = res[k]
		n = len(path)
		for i in range(n):
			s = ('.' * path[i]) + 'Q' + ('.' * (n - path[i] - 1))  # remember not s[path[i]] = 'Q'
			one_result.append(s)
		result.append(one_result)
	return result

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public List<List<String>> solveNQueens2(int n) {
	List<List<String>> res = new ArrayList<>();
	int[] col = new int[n];
	solveR(n, col, 0, res);
	return res;
}

// 5/2/2020
void solveR(int n, int[] col, int st, List<List<String>> res) {
	if(st == n) {
		print(col, res);
		return;
	}
	
	for(int i = 0; i < n; i++) {
		col[st] = i;
		if(isValid(col, st))
			solveR(n, col, st + 1, res);
	}
}

boolean isValid(int[] col, int k) {
	for(int i = 0; i < k; i++) {
		if(col[i] == col[k])
			return false;
	}

	for(int i = 0; i < k; i++) {
		if(Math.abs(k - i) == Math.abs(col[k] - col[i])) //use abs
			return false;
	}
	return true;
}

算法分析：

时间复杂度为O(n!)，空间复杂度O(n^2)

Free mock interview