n皇后: 在n*n的格子中摆放n个皇后,并使每个皇后不能攻击到其他皇后,即同行,同列,对角线四条线上不能有其他皇后
算法:
考虑棋盘上所有位置
对于行为r,列为c的位置(r,c),若该点能放置,就在此放置,然后考虑r+1行,直到所有行被遍历
若对于(r,c)及其衍生情况考虑完毕,恢复在(r,c)放置棋子之前的棋盘,以同样方法考虑(r,c+1),直到该行的所有列被遍历
n=int(input())
count=0
def check(nowr,nowc,queue):
global n
#这里的queue是1×n的矩阵,下标代表行数,值代表列数
for i in range(nowr):
if nowc==queue[i] or abs(nowr-i)==abs(nowc-queue[i]):
return False
return True
#输入当前行,之前皇后的位置
def findmethod(nowr,queue):
global count,n
if nowr>n-1:
count+=1
return
for nowc in range(n):
#通过检测
if check(nowr,nowc,queue):
queue[nowr]=nowc
findmethod(nowr+1,queue)
board=[0 for _ in range(n)]
findmethod(0,board)
print(count)
由于我们只需要得知每一行的皇后位置,而每一行的皇后有且仅有一个,所以我们可以以一维数组的方式存放皇后的位置,元素下标为行数,值为列数
问题描述 给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，
任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
输入格式 输入的第一行为一个整数n，表示棋盘的大小。 接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
输出格式 输出一个整数，表示总共有多少种放法。
样例输入 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 样例输出 2
样例输入 4 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 样例输出 0
相较于n皇后
变化1:将皇后分为黑白两种,而只有同种的皇后会互相干扰[将算法分为两层,先放置其中一种,再放另一种]
变化2:棋盘有的地方不能放置皇后
由于两种变化,我们不能再使用一维数组来简化位置信息,需要实时传送一个二维数组来记录棋盘信息
n=int(input())
chessboard=[]
for i in range(n):
chessboard.append(list(map(int,input().split())))
count=0
#该函数用于检查传入的位置是否能放
def check(nowr,nowc,kind,board):
#当前行,当前列,皇后种类,棋盘
if board[nowr][nowc]!=1:
return False
for i in range(len(board)):
#同列
if board[i][nowc]==kind:
return False
#-45°对角线
if nowc-i-1>=0 and board[nowr-i-1][nowc-i-1]==kind:
return False
#45°对角线
if nowc+i+1<len(board) and board[nowr-i-1][nowc+i+1]==kind:
return False
return True
#该函数用于寻找方法数
def findmethod(nowr,kind,board):
global count
#当前的行数,皇后种类,棋盘
#当当前行数超过最下面一行
if nowr==len(board):
#一种皇后放置结束,放另一种
if kind==2:
findmethod(0,3,board)
#两种都放完
if kind==3:
count+=1
return
#没有放置完
else:
#对当前行每一列遍历
for i in range(len(board)):
if check(nowr,i,kind,board):
#检测通过在此处放上棋子
board[nowr][i]=kind
#对下一行进行检查
findmethod(nowr+1,kind,board)
#回溯到原来状态(只可能是1),进行下一列遍历
board[nowr][i]=1
findmethod(0,2,chessboard)
print(count)