欢迎访问Python教程网,我们的网址www.041b.com
Python|行列式解‘黑白皇后’ – python教程 - python编程学习交流
Python|行列式解‘黑白皇后’ – python教程 - python编程学习交流

Python|行列式解‘黑白皇后’

admin2020-08-18 发布 python教程

这里将告诉您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=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

结语

受线性代数课程启发,本题从行列式的角度出发得以解决,因此解题的思维并不难。‘天下难事必作于易,天下大事必作于细。’生活中小细节往往也有大作用,重视细节更是编写程序的严密逻辑的体现。而联系具有普遍性,往往重视事物之间的联系能为我们解决很多问题。也正是因为看到了行列式与上题的联系,这才得以成功解出。

Python|行列式解‘黑白皇后’就为您介绍到这里.欢迎访问python自学网 www.041b.com

转载原创文章请注明,转载自: python教程 - Python|行列式解‘黑白皇后’ (https://www.041b.com/40099.html)

留言

写下你的评论吧

近期评论