你有4个涂色的立方体。每个立方体的每一面涂有一种颜色。编写一个程序找出所有符合 要求的排列

fengxiuping
  • 330

你有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种颜色。编写一个程序找出所有符合 要求的排列。

回复
阅读 5.2k
4 个回答
✓ 已被采纳

我们可以先分析一下:
对于每个立方体,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']
moya
  • 2
新手上路,请多包涵

私以为此题应该是使用DLX来进行搜索。因为每一个立方体实质上只有三种摆法,而每一个立方体在某一列有四种颜色的可能性,所以dlx可初始化为12行16列,然后精确覆盖。

写贴代码

<?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>";

上面是找出颜色位置的所有组合
问题转成求排列组合,俺数学差,搞不定了,半成品
求更好思路

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏