首页 > 其他 > 详细

Leetcode - 51. N 皇后

时间:2021-09-08 20:59:49      阅读:23      评论:0      收藏:0      [点我收藏+]

n皇后问题研究的是如何将n个皇后放置在n×n的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数n,返回所有不同的n皇后问题的解决方案。
每一种解法包含一个不同的n皇后问题的棋子放置方案,该方案中 ‘Q‘ 和 ‘.‘ 分别代表了皇后和空位。

示例 1:
技术分享图片

输入:n = 4
输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释:如上图所示,4 皇后问题存在两个不同的解法。

示例 2:

输入:n = 1
输出:[["Q"]]

提示:

  • 1 <= n <= 9
  • 皇后彼此不能相互攻击,也就是说:任何两个皇后都不能处于同一条横行、纵行或斜线上。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/n-queens
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

(未完成)解1 2021/9/7 O(?)

def solveNQueens(n: int) -> list:
    ‘‘‘
    .Q..
    ...Q
    Q...
    ..Q.

    ..Q.
    Q...
    ...Q
    .Q..
    ‘‘‘
    ‘‘‘
    一个一个放?
    比如,(x表示不能放了)
    q   x   x   x
    x   x   .   .
    x   .   x   .
    x   .   .   x
    
    q   x   x   x
    x   x   q   x
    x   x   x   x
    x   .   x   x
    只剩1个空位了,不行
    
    不过这个遍历的深度不小,O(n^2)后面一层一层下去
    试试吧
    ‘‘‘
    # 棋盘
    qipan=[[‘.‘]*n]*n
    # 剩余的Q
    remain_q=n
    # 剩下的空位,存位置(x,y)
    blank=[]
    for x in range(0,n):
        for y in range(0,n):
            qipan[x][y]=‘Q‘
            remain_q-=1
            # 初始化blank
            for i in range(0,n):
                for j in range(0,n):
                    # 横,竖
                    if i==x or j==y: continue
                    # 斜,斜就是斜率,±1
                    if abs((j-y)/(i-x))==1: continue
                    blank.append((i,j))
            # 开始填剩下的Q
            while remain_q and blank.__len__():
                # 貌似又要递归,写不下去了
    pass

if __name__ == ‘__main__‘:
    # [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
    n = 4
    # [["Q"]]
    n = 1

Leetcode - 51. N 皇后

原文:https://www.cnblogs.com/Code2235/p/15239821.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!