一题征服面试官：N 皇后最优解

点击上方 蓝字 关注我们

下面开始今天的学习～

背景介绍

历史上有一个著名的问题：八皇后问题，题目大意如下：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？

八个皇后在 8x8 棋盘上共有 4,426,165,368（64C8）种摆放方法，但只有 92 个互不相同的解。

对应扩展开来就有我们 N 皇后问题，也就是：  %s/8/n/g   啦~

在一个 n * n 的棋盘上放置 n 个皇后，要求不能有两个皇后位于同一行、同一列，或同一条 45 度斜线上。问共有多少种放法？

从八皇后问题开始，对于每一个 “皇后” 而言，当它被放置的时候，有以下绿色区域是不能放其他的 “皇后的”：

解题方式

这道题本质是考察对于递归算法的掌握程度，对于每一行而言，我们按照规则摆放一个皇后，如果没有和之前的皇后冲突的话，就到下一行，以此类推，直到某一个皇后在一行中任何地方都无法正确摆放的时候，我们就回到上一行，把上一行的皇后向右移动一格，然后再尝试摆放这一行的皇后，可能比较拗口，我们按照流程来描述一下：

1. 从第一列开始，为皇后找到安全位置，然后跳到下一列

2. 如果在第 n 列出现死胡同，如果该列为第一列，棋局失败，否则后退到上一列，在进行回溯

3. 如果在第 8 列上找到了安全位置，则棋局成功。

8 皇后问题代码实现

首先是判断板子是否安全（即，是否有碰撞）的算法（顺便定义板子大小）：

global N

N = 8

def isSafe(board, row, col):

# Check this row on left side

for i in range(col):

if board[row][i] == 1:

return False

# Check upper diagonal on left side

for i,j in zip(range(row,-1,-1), range(col,-1,-1)):

if board[i][j] == 1:

return False

# Check lower diagonal on left side

for i,j in zip(range(row,N,1), range(col,-1,-1)):

if board[i][j] == 1:

return False

return True

然后递归求解：

def solveNQUtil(board, col):

# base case: If all queens are placed

# then return true

if col >= N:

return True

# Consider this column and try placing

# this queen in all rows one by one

for i in range(N):

if isSafe(board, i, col):

# Place this queen in board[i][col]

board[i][col] = 1

# recur to place rest of the queens

if solveNQUtil(board, col+1) == True:

return True

# If placing queen in board[i][col

# doesn't lead to a solution, then

# queen from board[i][col]

board[i][col] = 0

# if the queen can not be placed in any row in

# this colum col then return false

return False

最后我们可以写一个驱动程序，然后怼一个板子进去运行：

def solveNQ():

board = [ [0, 0, 0, 0, 0 ,0 ,0],

[0, 0, 0, 0, 0 ,0 ,0],

[0, 0, 0, 0, 0 ,0 ,0],

[0, 0, 0, 0, 0 ,0 ,0]

]

if solveNQUtil(board, 0) == False:

print "Solution does not exist"

return False

printSolution(board)

return True

N 皇后问题代码实现

推广到 N 皇后问题，也是一样，以下有一个递归的写法：

class NQueens:

"""Generate all valid solutions for the n queens puzzle"""

def __init__(self, size):

# Store the puzzle (problem) size and the number of valid solutions

self.size = size

self.solutions = 0

self.solve()

def solve(self):

"""Solve the n queens puzzle and print the number of solutions"""

positions = [-1] * self.size

self.put_queen(positions, 0)

print("Found", self.solutions, "solutions.")

def put_queen(self, positions, target_row):

"""

Try to place a queen on target_row by checking all N possible cases.

If a valid place is found the function calls itself trying to place a queen

on the next row until all N queens are placed on the NxN board.

"""

# Base (stop) case - all N rows are occupied

if target_row == self.size:

self.show_full_board(positions)

self.solutions += 1

else:

# For all N columns positions try to place a queen

for column in range(self.size):

# Reject all invalid positions

if self.check_place(positions, target_row, column):

positions[target_row] = column

self.put_queen(positions, target_row + 1)

def check_place(self, positions, ocuppied_rows, column):

"""

Check if a given position is under attack from any of

the previously placed queens (check column and diagonal positions)

"""

for i in range(ocuppied_rows):

if positions[i] == column or \

positions[i] - i == column - ocuppied_rows or \

positions[i] + i == column + ocuppied_rows:

return False

return True

def show_full_board(self, positions):

"""Show the full NxN board"""

for row in range(self.size):

line = ""

for column in range(self.size):

if positions[row] == column:

line += "Q "

else:

line += ". "

print(line)

print("\n")

def main():

"""Initialize and solve the n queens puzzle"""

NQueens(8)

if __name__ == "__main__":

# execute only if run as a script

main()

看完这篇文章，你有啥更好的解法吗？可以在评论区留言哦～

本文作者：Nova Kwok

编辑&版式：霍霍

声明：本文归 “力扣” 版权所有，如需转载请联系。

推荐阅读