四色方柱问题

1、算法与分析课程设计报告题 目：四色方柱问题专 业：软件工程班 级：学 号：姓 名：太原工业学院计算机工程系2012年 11 月 23 日一、算法问题描述设有4个立方体，每个立方体得每一面用红、黄、蓝、绿4种颜色之一染色。 要把这4个立方体叠成一个方形柱体，使得柱体使得 4个侧面的每一侧均有4 种不同的颜色。同时，4个顶面和4个底面也有4种不同的颜色。试设计一个回 溯算法，计算出4个立方体的一种满足要求的叠置方案。二、算法问题形式化表示对于给定的四个立方体及每个立方体各面的颜色，给出一种叠置方案，使柱体的四个侧面都有四种不同的颜色。三、期望输入与输出期望输入：第一行输出1表示顶面，2表示底面3表

2、示左面，4表示右面，5表 示前面，6表示后面。期望输出：输出每个立方体每个面的着色方案，即问题的解决方案。四、算法分析与步骤描述事实上，这个四色方柱问题，如果用逆推想会好理解一些，现在设将这四个 立方体组合成了一个方形柱体，我们可以先选择一个立方体的符合条件的顶面和 底面，之后我们可以将它的侧面展开这样会形成一个4*4的矩阵，该4*4矩阵上每行的四个值相当于原小立方体的四个侧面的着色(左、右、前、后对应于1、2、3、4)列上的四个值就是表示四个小立方体合成方形柱体后柱体上某个侧面 的着色了，这样就可以利用类似于 N皇后的回溯算法的思路了， N皇后的要求是 不能相互攻击而这个题根据要求就是使每列

3、上的着色值都不同。用4元数组Xi，j,(i=1、2、3、4, j=1、2、3、4)表示第i个立方体第j个面所图颜色，由于不允许将两个颜色放在同一列，所以解向量中的Xi互不相同。将n*n格棋盘看作二维矩阵，其行号从上到下以此表示四个立方体，列号从左到右依次表示左、右、前、后立方体的六个面。从棋盘自上来下同一竖直线 上，因此，两个颜色放置的位置分别是(i,j )和(k，I),且i!=k、 j=l&X(l,j)!=X(k,I)，此条件下确保四方柱的每个侧面都有四种不同的颜色。由此可知，只要i=k、j=l&X(l,j)!=X(k,I)就说明两个颜色在同一侧面上。根据对四色方柱问题算法分析，我们用回朔法

4、求解，递归方法backtrack实现对整个解空间的回朔搜索。Backtrack(i)搜索解空间的第 i层树。类FourColorProblem的数据成员记录解空间中结点信息，以减少传给 backtrack 的参数。Sum记录当前已找到的可行方案数，result叩 记录可行方案。五、问题实例及算法运算步骤给定四个立方体和四种颜色红绿黄蓝，把它们放置成一个长方柱体，要求四个侧面、顶面、底面都有四种不同的颜色。把长方体的侧面展开，看成4*4的矩阵，这就相当于n皇后的问题，只需要 每一列的颜色不同即可。所以两个颜色放置的位置分别是( i,j )和(k，l), 且i!=k、j=l&X(l,j)!=X(k

5、,l)，就可以确保四方柱的每个侧面都有四种不同的颜色。六、算法运行截图felue yellow red green blue yellow green red tlue red yellow green bin亡 red green yellow blue green red yellow blue green yellow red green yellow blue red green yellow red blue green tine yellow red green blue red yellow green red blue yellow green red yellow bluered yellow 匕1口亡 green red yellow green blue red blue yell口坤 green red fclue green yellow red green blue yellow red green yellow blue yellow red bln皂 green yellow red green blue yellowred 卩工亡皂nyellow blue green red yellow green