Python|行列式解‘黑白皇后’
问题描述
线性是人类少数研究得十分透彻的数学基础架构，上升到非线性的问题，我们并没有足够多的通用性质定理帮助解决问题。因此在面对一些“曲性”问题，我们常常“以直代曲”，将其划分成线性问题。而编程题中更是不乏此类，‘黑白皇后’便属其中：
1 例题
1.1 问题描述
给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
1.2 输入格式
输入的第一行为一个整数n，表示棋盘的大小。 接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
1.3 输出格式
输出一个整数，表示总共有多少种放法。
解决方案
初见此题，第一想法是一行行设置判断，最终符合再输出。由于本人技术不行，未能成功。但在课程“线性代数”关于行列式的讲解中，突然发现展开行列式似乎能解决本题。
（1）先找一种皇后有多少放法：
先让我们回顾上题几个条件：1.不同列2.不同行3.不在斜线4.位置为‘0’不能放。而行列式的展开有个特点（不同行与不同列），而第三个条件：不在同一斜线，这个要用到斜率的知识——斜率的绝对值不能为1即可。最后一个条件：先找出‘0’的坐标（x，y），把含有此坐标的行列展开式删去即可。
（2）最后再找两种皇后的放法：
条件：两种皇后不能重合——即不含相同坐标。假设一种皇后有8种放法，将8种放法按2种为一组划分，且不含相同坐标的组合就能成功。
代码示例：
1 输入部分
import itertools
n=int(input())
b=[]
for i in range(n):
B=list(map(int,input().split(' ')))
b.append(B)2 找缺失的坐标
c=[]
for i in range(n)
for ii in range(n):
if b[i][ii]==0:
c.append([i+1,ii+1])3 列表展开式（此部分运行时间长）
a=list(range(1,n+1))
a=list(itertools.permutations(a)
for i in range(len(a)):
a[i]=list(a[i])4 寻找能放下的列表展开式
s=[]
f=[]
for i in a:#寻找能放下的排列方式
i=list(i)
for ii in range(len(i)):
for iii in range(len(i)):
if ii!=iii:
g=(i[ii]-i[iii])/(ii+1-(iii+1))#斜率满足正负1就去掉
if g==1 or g==-1:
f.append(i)
break
for i in f:#去重
if i not in s:
s.append(i)
for i in s:
a.remove(i)
s=a5 查找含有不能放棋的坐标
d=[]
for i in c:
for ii in s:
if ii[i[0]-1]==i[1]:
d.append(ii)6 去掉不能放棋的展开式
for i in d:
if i in s:
s.remove(i)
else:
pass7 寻找黑白皇后同时放下次数
m=0
for i in range(len(s)):#寻找两个不占相同位置的
k=s[i+1:]
if k!=[]:
v=0
for ii in range(len(k)):
for iii in range(n):
if s[i][iii]==k[ii][iii]:
v+=1
break
v=(len(s)-i-1)-v#与s[i]满足没占相同位置的列表数......即使含有s[i]的组合数
m+=v#最终累加
else:
print(m*2)#单组黑白皇后可以互换位置
break结语
受线性代数课程启发，本题从行列式的角度出发得以解决，因此解题的思维并不难。‘天下难事必作于易，天下大事必作于细。’生活中小细节往往也有大作用，重视细节更是编写程序的严密逻辑的体现。而联系具有普遍性，往往重视事物之间的联系能为我们解决很多问题。也正是因为看到了行列式与上题的联系，这才得以成功解出。
腾讯云开发者
