用Python解决立方体的摆放问题

孤独雪鹰

　　用Python解决立方体的摆放问题
　　

　　近日编程解决了某人发在shlug上的一道面试题，当时的几条讨论的在这里：https://groups.google.com/group/shlug/browse_thread/thread/6fbdd7efa63b6d7a
　　

　　下面是我对该问题的整理和实现的代码
　　

　　－－－－－－－－－－－－－－－－－－
　　问题：
　　有4个彩色的立方体。立方体的6个面，每面都涂上了1种颜色。一共有4种颜色，蓝色(B)，红色(R)，绿色(G)和黄色(Y)。立方体的6个面称为前(front)、后(back)、左(left)、右(right)、上(top)、下(bottom)。
　　

　　这4个立方体的颜色排列为：
　　编号    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个侧面，要求每个侧面都有4种颜色。
　　用你最拿手的语言编程实现，算出有多少种摆放方式。
　　

　　－－－－－－－－－－－－－－－－－－
　　初始的想法：
　　

　　1. 考虑单个立方体的摆放方法，有6个面，也就是6种情况；将每种情况下的4个侧面的颜色保存到一个数组中，得到一个6X4的数组 a[6][4]; 此外，每种摆放方法还可以旋转4次
　　2. 不考虑颜色，只考虑立方体的重叠方式，一共有24种方法。
　　3. 针对24种情况中的每一种，从每一个立方体里分别取一个数组元素，比较之，一旦有相同的就失败，否则count+1；用回溯法解决。
　　4. 最终的count就是总共的可能性。
　　

　　复杂度：24 * (6*4) * (6*4) * (6*4) * (6*4) = 7962624; 其中的6*4是指立方体有6种摆放方法，而每种还可以旋转4次 但是由于一旦失败就会提前退出循环，所以实际次数很远远小于上面的数字。
　　

　　感觉算法不难，但是第一步的保存颜色到数组的过程绝对是一件容易出错的体力活
　　

　　－－－－－－－－－－－－－－－－－－
　　

　　然而，在编码的过程中，发现完全可以更简单一些，如下为简化之处：
　　

　　因为颜色与方块的位置无关，所以只要考虑一种组合即可
　　而最下面的方块的四种旋转方式其实是一样的，确定一种，旋转4次，即为4倍
　　所以如果在 "方块1，2，3，4顺便摆放，而且方块1不旋转" 的前提下有N种方法，
　　那么一共就有 4 * 4！* N = 96N 种方法
　　

　　用Python编程解决了一下，发现 "方块1，2，3，4顺便摆放，而且方块1不旋转" 的情况下只有2种摆放方式
　　为：
　　('R', 'Y', 'B', 'B')
　　('G', 'G', 'R', 'Y')
　　('B', 'R', 'Y', 'G')
　　('Y', 'B', 'G', 'R')
　　和：
　　('R', 'B', 'B', 'Y')
　　('G', 'Y', 'R', 'G')
　　('B', 'G', 'Y', 'R')
　　('Y', 'R', 'G', 'B')
　　

　　而最终循环的次数也只有145次。
　　

　　－－－－－－－－－－－－－－－－－－－－－－－－－－－
　　下面为实现的Python代码 (老规矩，前面添加'- '来保留前置空格 －－ 可恶的blog格式)：
　　- #!/usr/bin/python
　　- 
　　- # Chunis Deng @ 2010.05.12 (chunchengfh@gmail.com)
　　- 
　　- def accumulate(level):
　　-     #print_result(level)    # uncomment this to get debug info
　　- 
　　-     if level == 0:
　　-         for i in range(6):
　　-             flags[0] = [i, 0]
　　-             accumulate(level+1)
　　-     else:
　　-         for x in range(6):
　　-             for y in range(4):        
　　-                 flags[level] = [x, y]
　　-                 result = is_current_OK(level)
　　-                 if result:    # all sides with different colors
　　-                     if level == LEVEL:
　　-                         print "OK, Result is: "
　　-                         print_result(level)
　　-                     else:
　　-                         accumulate(level+1)
　　- 
　　- def print_result(lvl):
　　-     print "Level: ", lvl+1
　　-     for i in range(lvl+1):
　　-         print flags
　　-     for i in range(lvl+1):
　　-         (x, y) = flags
　　-         sqr = sqr_array
　　-         print sqr[x][y:] + sqr[x][:y]
　　-     print    # just print a blank line
　　- 
　　- def is_current_OK(lvl):
　　-     tmp_lst = []
　　-     for i in range(lvl+1):
　　-         (x, y) = flags
　　-         sqr = sqr_array
　　-         tmp_lst.append(sqr[x][y:] + sqr[x][:y])
　　-         
　　-     for i in range(4):
　　-         mylist = []
　　-         for j in range(lvl):
　　-             mylist.append(tmp_lst[j])
　　-         if tmp_lst[lvl] in mylist:
　　-             return 0
　　-     
　　-     return 1
　　- 
　　- 
　　- LEVEL = 3    # count from 0
　　- flags = [
　　-     [0, 0],
　　-     [0, 0],
　　-     [0, 0],
　　-     [0, 0] ]
　　- 
　　- sqr_color = (    ( 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' ) )
　　- 
　　- sqr_array = []
　　- 
　　- 
　　- # i: put_as_bottom:    sides:    sides_index:
　　- # -------------------------------------------------
　　- # a) front:        edfc        5463
　　- # b) back:        fdec        6453
　　- # c) left:        afbe        1625
　　- # d) right:        aebf        1526
　　- # e) top:        bdac        2413
　　- # f) bottom:        adbc        1423
　　- 
　　- for sqr in sqr_color:
　　-     tmp = []
　　-     tmp.append( (sqr[5], sqr[4], sqr[6], sqr[3]) )    # front
　　-     tmp.append( (sqr[6], sqr[4], sqr[5], sqr[3]) )    # back
　　-     tmp.append( (sqr[1], sqr[6], sqr[2], sqr[5]) )    # left
　　-     tmp.append( (sqr[1], sqr[5], sqr[2], sqr[6]) )    # right
　　-     tmp.append( (sqr[2], sqr[4], sqr[1], sqr[3]) )    # top
　　-     tmp.append( (sqr[1], sqr[4], sqr[2], sqr[3]) )    # bottom
　　-     sqr_array.append(tmp)
　　- 
　　- #for x in sqr_array: print x    # uncomment this to get debug info
　　- accumulate(0)