n后问题（python实现）

偏执的太偏执、 2023-07-02 02:20 45阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzc3ODA0_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzc3ODA0_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzc3ODA0_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzc3ODA0_size_16_color_FFFFFF_t_70 3][]

**程序实现**

# 检测（x,y）这个位置是否合法（不会被其他皇后攻击到）
    def check(board, row, col):
        i = 0
        for i in range(row):
            if abs(board[i] - col) == 0 or abs(board[i] - col) == abs(i - row): #[i, j]与[row, col]处于同列或者同对角线上
                return False
        return True
    
    
    def eightqueen(board, row):
        border = len(board)
        if row >= border:    # 当行数等于最大边界时，递归
            for i, col in enumerate(board): #输出从第一行到第board行结果
                print('□ ' * col + '■ ' + '□ ' * (len(board) - 1 - col))#■为皇后位置
            print("")
        col = 0
        while col < border:
            for col in range(border):
                if check(board, row, col): #如果这个位置合法的话，进行如下操作
                    board[row] = col
                    eightqueen(board, row + 1) #进行递归，使得行加一，即进入下一行
            col += 1
    
    board = [0 for i in range(8)] # 8皇后问题 
    eightqueen(board, 0)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzc3ODA0_size_16_color_FFFFFF_t_70 4][]

首先我们要给定一个矩阵，来存放棋子，从第一行开始遍历，接着遍历这一行的每一列。假设我们在位置\[1, 2\]处已经放上棋子，我们开始遍历第二行，首先判断\[2,1\]位置存放棋子是否可行，调用check函数，显然与上一行棋子处于同一对角线，不行返回False,以此类推直到便利到位置\[2,4\]时这是一个可行的位置，再继续往下遍历。

总结的来说就是在遍历当前行时，之前行的棋子已经确定好了，从而以此判断该行的各个位置是否可行。

当然对于主函数来说我们需要一个递归终止的条件，很简单当当前行数大于N时，我们就已经得到了一个符合条件的矩阵。

除此之外，我们如果用矩阵存储，每次都要通过遍历来确定之前行棋子所在的位置，时间复杂度爆炸。所以这里做一个简化，我们用一个\[1, n\]的矩阵来存储，也就是说\[row, col\] = \[i, board\[i\]\]，这样我们只需要O(1)的时间复杂度就能知道上一行的信息。

再说check函数，首先我们是一行行进行遍历，一定不会存在同行的情况，同列也比较好判断，对于正负对角线，通过观察我们可以发现，我们设row，col为当前行当前列，那么对于位置\[i, j\]。如果符合等式|row- i| = |col-j|，那么\[i, j\]如\[row, col\]位于同一对角线。把上述两种情况合并，如果if abs(col - j) == 0 or abs(col - j) == abs(row-i)，那么\[i, j\]与\[row, col\]必处于同列或者同对角线上。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzc3ODA0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200123230424599.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzc3ODA0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzc3ODA0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200123230441597.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzc3ODA0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzc3ODA0_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200123230508817.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzc3ODA0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzc3ODA0_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200123230523197.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzc3ODA0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzc3ODA0_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200123230612388.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzc3ODA0,size_16,color_FFFFFF,t_70