https://leetcode-cn.com/problems/n-queens/
# -*- coding:utf-8 -*- class Solution(object): def solveNQueens(self, n): """ :type n: int :rtype: List[List[str]] """ def check(i, j, temp_dir): for x in range(n): # 检查横竖 if temp_dir[x][j] is 'Q' or temp_dir[i][x] is 'Q': return False # 检查右上斜线 if i + x < n and j - x >= 0: if temp_dir[i + x][j - x] is 'Q': return False # 检查左下斜线 if i - x >= 0 and j + x < n: if temp_dir[i - x][j + x] is 'Q': return False # 检查左上斜线 if i - x >= 0 and j - x >= 0: if temp_dir[i - x][j - x] is 'Q': return False # 检查右下斜线 if i + x < n and j + x < n: if temp_dir[i + x][j + x] is 'Q': return False return True def back(x, from_x_idx, temp_dir): if x == n: import copy res.append(copy.deepcopy(temp_dir)) return if from_x_idx > n - 1: return for i in range(from_x_idx, n): for j in range(n): if temp_dir[i][j] is not 'Q' and check(i, j, temp_dir): temp_dir[i][j] = 'Q' back(x + 1, i + 1, temp_dir[:]) temp_dir[i][j] = '.' res = [] init_map = [['.' for _ in range(n)] for _ in range(n)] back(0, 0, init_map) res_final = [] for i in range(len(res)): temp_res = [] for j in range(n): temp_res.append("".join(res[i][j])) res_final.append(temp_res) return res_final if __name__ == '__main__': n = 8 print(Solution().solveNQueens(n))
思路:回溯法,判断当前位置是否可以摆放然后一步一步回溯即可。
值得提出的是,由于对于较大的n运行时间较长,因此要进行状态压缩也就是剪枝,比如当前位置的横纵斜不需要判断,比当前位置的x坐标小的不需要判断等。可以再做一个可访问地图剪枝即可。
0052 求个长度即可。
0 条评论