你有4个涂色的立方体。每个立方体的每一面涂有一种颜色。
颜色共有4种：蓝(B)，红(R)，绿(G)，黄(Y)。
将这六个面描述为前，后，左，右，顶，底。
这4个立方体的颜色如下：
Cube Front Back Left Right Top Bottom
1 R B G Y B Y
2 R G G Y B B
3 Y B R G Y R
4 Y G B R R R
现在把这4个立方体堆成垂直的一列，我们的目标是找到那些方法，使得这一列 的每一面都显示全部4种颜色。编写一个程序找出所有符合 要求的排列。
写贴代码
<?php
$a = [
'front' => 'r',
'back' => 'b',
'left' => 'g',
'right' => 'y',
'top' => 'b',
'bottom' => 'y',
];
$b = [
'front' => 'r',
'back' => 'g',
'left' => 'g',
'right' => 'y',
'top' => 'b',
'bottom' => 'b',
];
$c = [
'front' => 'y',
'back' => 'b',
'left' => 'r',
'right' => 'g',
'top' => 'y',
'bottom' => 'r',
];
$d = [
'front' => 'y',
'back' => 'g',
'left' => 'b',
'right' => 'r',
'top' => 'r',
'bottom' => 'r',
];
$pos = [];
foreach(['r', 'g', 'b', 'y'] as $v)
{
$pos[$v] = [];
foreach(['a' => $a, 'b' => $b, 'c' => $c, 'd' => $d] as $k1 => $v1)
{
$i = array_keys($v1, $v);
if(is_array($i))
{
foreach($i as $v2)
{
$pos[$v]["{$k1}_{$v2}"] = $v2;
}
}
else
{
$pos[$v]["{$k1}_{$i}"] = $i;
}
}
}
echo "<pre>";
print_r($pos);
echo "</pre>";
上面是找出颜色位置的所有组合
问题转成求排列组合，俺数学差，搞不定了，半成品
求更好思路
我们可以先分析一下：
对于每个立方体，front面可能有6种，确定front之后其实就确定了back面，所以每个立方体一共有6x4=24种排列方式，4个立方体就有24x24x24x24=331776种。33W的数量级那就试试用穷举的方式吧。
对于每个立方体的24种所有排列，可以旋转的方式生成。具体流程可以看看后面的Python代码。这个程序会产生18种结果，大家看看有没有问题？
# *-* coding: utf-8 -*-
data = '''
1 R B G Y B Y
2 R G G Y B B
3 Y B R G Y R
4 Y G B R R R
'''
def gen_order(row): # 对每个立方体生成24种顺序
for i in range(6): # 一共6个面
for j in range(4): # 顺进针旋转4次
yield row # 生成一个排列
row = [row[0], row[1], row[5], row[4], row[2], row[3]] # rotate
if i < 4: # 向上旋转
row = [row[5], row[4], row[2], row[3], row[0], row[1]]
elif i == 4: # 向右转
row = [row[2], row[3], row[1], row[0], row[4], row[5]]
else: # 再向右转2次
row = [row[1], row[0], row[3], row[2], row[4], row[5]]
data = [d.split()[1:] for d in data.split('\n') if d]
def illegal(a, b):
for i in range(len(a)):
if a[i] == b[i]:
return True
return False
result = []
for i0 in gen_order(data[0]):
for i1 in gen_order(data[1]):
if illegal(i0[:4], i1[:4]): # 前4个面要各不相同
continue
for i2 in gen_order(data[2]):
if illegal(i0[:4], i2[:4]) or illegal(i1[:4], i2[:4]):
continue
for i3 in gen_order(data[3]):
if illegal(i0[:4], i3[:4]) or illegal(i1[:4], i3[:4])\
or illegal(i2[:4], i3[:4]):
continue
result.append((i0, i1, i2, i3)) # 到这里的都是好样的
print 'total', len(result)
a,b,c,d = result[0]
print 'plan1 is'
print a
print b
print c
print d
输出
total 18
plan1 is
['R', 'B', 'Y', 'B', 'G', 'Y']
['G', 'R', 'G', 'Y', 'B', 'B']
['B', 'Y', 'R', 'G', 'R', 'Y']
['Y', 'G', 'B', 'R', 'R', 'R']
私以为此题应该是使用DLX来进行搜索。因为每一个立方体实质上只有三种摆法，而每一个立方体在某一列有四种颜色的可能性，所以dlx可初始化为12行16列，然后精确覆盖。