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

2013 年 7 月 5 日

点击上方蓝字关注我们

下面开始今天的学习～

背景介绍

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

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

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

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

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

解题方式

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

从第一列开始，为皇后找到安全位置，然后跳到下一列
如果在第 n 列出现死胡同，如果该列为第一列，棋局失败，否则后退到上一列，在进行回溯
如果在第 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