黑白球排列问题1问题重述如图1所示,27个立方形空盒排成3×3×3的三维阵列.如果三个盒子在同一条水平线上,或同一条垂直线上,或同一条对角线上,则认为三盒一线.这样的线共有49条:水平线18条,垂直线9条,水平面对角线6条,垂直面对角线12条,对角面对角线4条.现有白球13个,黑球14个,每个盒子中放入一球,如何投放,使有单一色球的线数最少.图1:空盒排列2问题分析面对此题,从理论上分析要比直接利用穷举法寻找最优投放方法要好很多,13因为如果将每个盒子都编号的话,在不考虑旋转对称的情况下,应该有C27种投放方式,对于每一种情形都要进行横竖斜的判断,计算量非常大,所以理论上的分析是必要的,或者至少在程序上能够节省时间.13模型建立与求解如果将单一色球的线数记为k,那么在给定立方体的维数n,以及黑白球的个数n0;n1,那么,k就是黑白球排列∆的函数k=kn(n0;n1;∆)(1)这样问题就来了:如何用数学的语言描述球的排列∆???这样不容易考虑,下面换一种思路.对于3×3×3的三维阵列(记为A),所有的点不外乎四种:体中心(1个,记为Bc)、体顶点(8个,记为Bv)、面中心(6个,记为Pc)、棱中心(12个,记为Ec),称之为基本点型I;II;III;IV.为了解决原来的问题,可以先把所有的空盒都填成白球(用1表示),然后按照一定的办法将某些位置的白球换成黑球(用0表示),最终达到单一色球线数最少的目的,思路见图2.图2:思路图对于初始状态A0(x;y;z)≡1;(x;y;z=1;2;3),总线数k=49,k0,四种基本点型各自形成的单一色球线数分别为k0(Bc)=13;k0(Bv)=7;k0(Pc)=5;k0(Ec)=4,显然要保证k很快的减小,应该将Bc换成黑球,这样得到状态A1(x;y;z)≡1;(x;y;z)=6(2;2;2);A1(2;2;2)=0.对于状态A1,总线数k1=36,四种基本点型对应的线数分别为k1(Bc)=0;k1(Bv)=6;k1(Pc)=4;k1(Ec)=3,所以下一步应该替换某一个顶点,不妨设为A(1;1;3),这样使得总线数减少6,而没有引入其他的线数.对于A2,四种基本点型对应的线数分别为k1(Bc)=0;k1(Bv)=(0;5;5;5;5;5;5;6);k1(Pc)=(3;3;3;4;4;4);k1(Ec)=(2;2;2;3;3;3;3;3;3;3;3;3)再一次替换顶点,四种基本点型对应的线数分别为k2(Bc)=0;k2(Bv)=(0;0;4;4;4;4;5;5);k2(Pc)=(3;3;3;3;3;4);k2(Ec)=(2;2;2;2;2;2;3;3;3;3;3;3)如此进行下去应该是可以得到最终答案的,但是后续的分析太过复杂,这里不再进行下去.24结果分析利用Matlab编程序,最终得到,最少的线数为4,对应的投放方法有很多种,下面给出一种:01B100CBCA(:;:;1)=@010A(2)10101B011CBCA(:;:;2)=@101A(3)10001B010CBCA(:;:;3)=@101A(4)010%%程序部分%%白色为1，黑色为0,3*3*3，白色13个，黑色14个clc;clear;num=0;forl=0:(2^27-1)temp=dec2bin(l,27);forj=1:27l1(j)=str2double(temp(j));endcount=sum(l1);ifcount==13n=0;num=num+1;f=reshape(l1,3,3,3);fori=1:3forj=1:3fork=1:3%平行于坐标轴的ifsum(f(i,j,:))==3||sum(f(i,j,:))==0||sum(f(:,j,k))==3||sum(f(:,j,k))==0||sum(f(i,:,k))==3||sum(f(i,:,k))==03n=n+1;endendendendfork=1:3%面对角线，沿ziff(1,1,k)==f(2,2,k)==f(3,3,k)n=n+1;elseiff(3,1,k)==f(2,2,k)==f(1,3,k)n=n+1;endendfori=1:3%面对角线，沿xiff(i,1,1)==f(i,2,2)==f(i,3,3)n=n+1;elseiff(i,1,3)==f(i,2,2)==f(i,3,1)n=n+1;endendforj=1:3%面对角线，沿yiff(1,j,1