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