LeetCode | 0051. N-Queens N 皇后【Python】
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode | 0051. N-Queens N 皇后【Python】,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2478字,纯文字阅读大概需要4分钟。
内容图文
![LeetCode | 0051. N-Queens N 皇后【Python】](/upload/InfoBanner/zyjiaocheng/1106/1411e430351f4b9b85b9813ef8a75fc4.jpg)
Problem
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
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:
Input: 4
Output: [
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.
问题
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 ‘Q‘ 和 ‘.‘ 分别代表了皇后和空位。
示例:
输入:4
输出:[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
提示:
- 皇后彼此不能相互攻击,也就是说:任何两个皇后都不能处于同一条横行、纵行或斜线上。
思路
回溯
回溯模板:
res = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
Python3 代码
from typing import List
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
res = []
# 一维列表
board = [‘.‘ * n for _ in range(n)]
def isValid(board, row, col):
"""
检查是否有皇后互相冲突
"""
# 检查第 row 行 第 col 列是否可以放皇后
# 只需考虑 <= row,因为后面的棋盘是空的
for row_index in range(row):
# 判断当前行是否放了皇后
if row_index == row:
if ‘Q‘ in board[row_index]:
return False
# 判断遍历每行时,第 col 列是否已经放了皇后
if ‘Q‘ == board[row_index][col]:
return False
# 判断左上方是否放了皇后
tmp_row, tmp_col = row, col
while tmp_row > 0 and tmp_col > 0:
tmp_row -= 1
tmp_col -= 1
if ‘Q‘ in board[tmp_row][tmp_col]:
return False
# 判断右上方是否放了皇后
tmp_row, tmp_col = row, col
while tmp_row > 0 and tmp_col < n - 1:
tmp_row -= 1
tmp_col += 1
if ‘Q‘ in board[tmp_row][tmp_col]:
return False
return True
def replace_char(string, char, index):
"""
构建新的字符串进行赋值
"""
string = list(string)
string[index] = char
return ‘‘.join(string)
def backtrack(board, row):
# 1.结束条件
if row == len(board):
# 需要用 list 转化一下
res.append(list(board[:]))
return
# 2.剪枝
# m = len(board[row])
for col in range(n):
# 剪枝
if not isValid(board, row, col):
continue
# 3.回溯并更新 row
board[row] = replace_char(board[row], ‘Q‘, col)
backtrack(board, row + 1)
board[row] = replace_char(board[row], ‘.‘, col)
backtrack(board, 0)
return res
if __name__ == "__main__":
n = 4
print(Solution().solveNQueens(n))
GitHub 链接
参考
原文:https://www.cnblogs.com/wonz/p/13648985.html
内容总结
以上是互联网集市为您收集整理的LeetCode | 0051. N-Queens N 皇后【Python】全部内容,希望文章能够帮你解决LeetCode | 0051. N-Queens N 皇后【Python】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。