问题描述
线性是人类少数研究得十分透彻的数学基础架构，上升到非线性的问题，我们并没有足够多的通用性质定理帮助解决问题。因此在面对一些“曲性”问题，我们常常“以直代曲”，将其划分成线性问题。而编程题中更是不乏此类，‘黑白皇后’便属其中：
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=a |
5 查找含有不能放棋的坐标
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: pass |
7 寻找黑白皇后同时放下次数
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 |
结语
受线性代数课程启发，本题从行列式的角度出发得以解决，因此解题的思维并不难。‘天下难事必作于易，天下大事必作于细。’生活中小细节往往也有大作用，重视细节更是编写程序的严密逻辑的体现。而联系具有普遍性，往往重视事物之间的联系能为我们解决很多问题。也正是因为看到了行列式与上题的联系，这才得以成功解出。
