原题来自某公司的一道面试题：
You have four colored cubes. Each side of each cube is a single color,
and there are four colors: blue (B), red (R), green (G) and yellow (Y)
Describing the six faces as front, back, left, right, top, bottom, the
cube colors are:
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
The objective is to find ways to stack the four cubes as a vertical
column so that each side of the column is showing all four colors.
Use the language of your choice to write a program to find all
successful permutations.
大概意思是说给定4个指定好颜色的立方体，从第1个立方体开始垂直叠堆起来，即叠堆成拥有4层的垂直立方体，叠堆起来的垂直立方体需要确保每4面（4面即：左、前、右后，上和下这2面可以不考虑）都有不同的颜色。
思路解决：回溯尝试（迭代或者递归）法去尝试枚举所有情况直到满足条件。
关键点：
1、每个立方体共有4*4=16种翻转情况，需要存储下每个立方体的16中翻转情况，便于在不满足条件时换下一种翻转情况尝试；
2、在尝试当前层玩所有翻转情况后依旧不满足条件，则需要有一种回溯机制（即回退到原来的地方），继续尝试下一种可能；
3、定义了一个立方体类（Cube），属性关键的包括左、前、右、后、上、下这6个面的颜色，还有一个包括了16种翻转情况的Cube列表；然后再判断相邻2层的立方体，当有某一面的颜色相同时，就代表不满足条件，否则就代表满足条件；
具体实现代码（java）如下，分别使用了迭代和递归的方式去求解问题。
public class Test {
private static final Cube[] cubes = {
new Cube(Color.R, Color.B, Color.G, Color.Y, Color.B, Color.Y),
new Cube(Color.R, Color.G, Color.G, Color.Y, Color.B, Color.B),
new Cube(Color.Y, Color.B, Color.R, Color.G, Color.Y, Color.R),
new Cube(Color.Y, Color.G, Color.B, Color.R, Color.R, Color.R),
};
static{
for(Cube cube:cubes){
cube.generateRotations();
}
}
private enum Color {
B, R, G, Y;
}
private static class Cube {
private final Color front;
private final Color back;
private final Color left;
private final Color right;
private final Color top;
private final Color bottom;
private String name = "";
private List<Cube> rotations;
private int rotationIndex;
public Cube(Color front, Color back, Color left, Color right, Color top, Color bottom) {
this.front = front;
this.back = back;
this.left = left;
this.right = right;
this.top = top;
this.bottom = bottom;
}
public void resetRotation() {
rotationIndex = 0;
}
public boolean hasRotation() {
return rotationIndex < rotations.size();
}
public Cube rotation() {
Cube result = rotations.get(rotationIndex);
rotationIndex++;
//System.out.println(nextIndex/*+":"+result*/);
return result;
}
public boolean isOneSideColorSame(Cube cube){
return front == cube.front
|| back == cube.back
|| left == cube.left
|| right == cube.right;
}
@Override
public String toString() {
// return "Cube [front=" + front + ", back=" + back + ", left=" + left + ", right=" + right + ", top=" + top
// + ", bottom=" + bottom + "]";
return "Cube [top=" + top + ", bottom=" + bottom + ", front=" + front + ", back=" + back + ", left=" + left
+ ", right=" + right + "] "+name;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((back == null) ? 0 : back.hashCode());
result = prime * result + ((bottom == null) ? 0 : bottom.hashCode());
result = prime * result + ((front == null) ? 0 : front.hashCode());
result = prime * result + ((left == null) ? 0 : left.hashCode());
result = prime * result + ((right == null) ? 0 : right.hashCode());
result = prime * result + ((top == null) ? 0 : top.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Cube other = (Cube) obj;
if (back != other.back)
return false;
if (bottom != other.bottom)
return false;
if (front != other.front)
return false;
if (left != other.left)
return false;
if (right != other.right)
return false;
if (top != other.top)
return false;
return true;
}
public void generateRotations() {
Set<Cube> rotationSet = new LinkedHashSet<Cube>();
int i = 0;
Cube current = null;
do {
current = i == 0 ? this : current.turnLeft90Degree();
if(rotationSet.add(current)){
current.name = i > 0 ? i + " left90Degree" : "";
//System.out.println("i:"+i+" add "+left90Degree);
}
Cube down90Degree = current;
for(int j=0;j<3;j++){ //内嵌的循环为3是为了减去一次不必要的重复情况 ，因为第一个面在之前已经add了
down90Degree = down90Degree.turnDown90Degree();
if(rotationSet.add(down90Degree)){
down90Degree.name = (i > 0 ? i + " left90Degree and " : "") + (j + 1) + " down90Degree";
//System.out.println("i:"+i+",j:"+j+" add "+down90Degree);
}
}
i++;
} while (rotationSet.size() < 16); //立方体总的旋转共能产生4×4=16种情况
rotations = new ArrayList<Cube>(rotationSet);
}
public Cube turnLeft90Degree(){
return new Cube(right, left, front, back, top, bottom);
}
public Cube turnDown90Degree(){
return new Cube(top, bottom, left, right, back, front);
}
}
public static void main(String[] args) {
solveByIterator();
resetCubesRecursion();
solveByRecursion();
//print4CubeRotations();
}
private static void solveByIterator(){
print(solveByIterator(4), "solveByIterator resolution");
}
private static List<Cube> solveByIterator(final int level){
List<Cube> result = new ArrayList<Cube>();
boolean isAddNextCube = false;
Cube currentCube = cubes[0].rotation();
for(int i=0;i<level;){
if(isAddNextCube){
currentCube = cubes[i].rotation();
isAddNextCube = false;
}
if(addCube(result, currentCube)){
i++;
isAddNextCube = true;
}else{
while(!cubes[i].hasRotation()){ //当此层立方体的所有旋转情况都试过后依旧无解
cubes[i].resetRotation(); //重置此层的旋转情况，为下次拿到下一个旋转情况做准备
i--; //返回上一层
if(i < 0){
throw new IllegalArgumentException(level+"层四色立方体无解！");
}
result.remove(i); //因为下一层所有情况都尝试依旧无解，故重新清除之前已经存储的的立方体情况
}
currentCube = cubes[i].rotation(); //拿到下一个旋转情况再尝试
//失败的话拿另一个立方体尝试，这里没有必要，因为假设立方柱的叠放所拿的立方体顺序为1、2、3、4
}
}
return result;
}
private static void resetCubesRecursion(){
for (Cube cube : cubes) {
cube.resetRotation();
}
}
private static void solveByRecursion(){
List<Cube> result = new ArrayList<Cube>();
final int level = 4;
if(!solveByRecursion(level, cubes, cubes[0].rotation(), result)){
throw new IllegalArgumentException(level+"层四色立方体无解！");
}
print(result, "solveByRecursion resolution");
}
private static boolean solveByRecursion(final int level, Cube[] cubes, Cube current, List<Cube> result){
if(!tryAddCubeIterate(current, result)){
return false;
}
if(result.size() == level){
return true;
}
if(!solveByRecursion(level, cubes, cubes[result.size()].rotation(), result)){
result.remove(result.size()-1); //返回上一层
if(!cubes[result.size()].hasRotation()){
cubes[result.size()].resetRotation();
return false;
}
return solveByRecursion(level, cubes, cubes[result.size()].rotation(), result);
}
return true;
}
/** 尝试该层的所有翻转情况，还不行则重置此层的旋转情况，为下次拿到下一个旋转情况做准备 */
private static boolean tryAddCubeIterate(Cube current, List<Cube> result){
boolean isAddSucc = addCube(result, current);
while(!isAddSucc){
if(!cubes[result.size()].hasRotation()){
cubes[result.size()].resetRotation();
return false;
}
isAddSucc = addCube(result, cubes[result.size()].rotation());
}
return true;
}
private static boolean addCube(List<Cube> result, Cube cube){
if(!isSatisfy(result, cube)){
return false;
}
return result.add(cube);
}
private static boolean isSatisfy(List<Cube> result, Cube cube) {
if(result.isEmpty()){
return true;
}
for(Cube ele:result){
if(ele.isOneSideColorSame(cube)){
return false;
}
}
return true;
}
private static void print(List<Cube> result, String solveType) {
System.out.println("----------------------------------"+solveType+"----------------------------------");
for(int i=0;i<result.size();i++){
Cube ele = result.get(i);
System.out.println((i+1)+"_"+ele);
}
System.out.println("----------------------------------"+solveType+"----------------------------------");
}
private static void print4CubeRotations() {
for (Cube cube : cubes) {
System.out.println(cube.rotations.size());
for (Cube c : cube.rotations) {
System.out.println(c);
}
}
}
}
代码在求解出一种情况后就会退出，并打印该情况下4个立方体的6个面和到达该面需要做的翻转：
----------------------------------solveByIterator resolution---------------------------------- 1_Cube [top=G, bottom=Y, front=B, back=Y, left=R, right=B] 1 left90Degree and 1 down90Degree 2_Cube [top=B, bottom=B, front=Y, back=G, left=G, right=R] 3 left90Degree and 2 down90Degree 3_Cube [top=R, bottom=Y, front=G, back=R, left=B, right=Y] 3 left90Degree and 2 down90Degree 4_Cube [top=R, bottom=R, front=R, back=B, left=Y, right=G] 1 left90Degree ----------------------------------solveByIterator resolution---------------------------------- ----------------------------------solveByRecursion resolution---------------------------------- 1_Cube [top=G, bottom=Y, front=B, back=Y, left=R, right=B] 1 left90Degree and 1 down90Degree 2_Cube [top=B, bottom=B, front=Y, back=G, left=G, right=R] 3 left90Degree and 2 down90Degree 3_Cube [top=R, bottom=Y, front=G, back=R, left=B, right=Y] 3 left90Degree and 2 down90Degree 4_Cube [top=R, bottom=R, front=R, back=B, left=Y, right=G] 1 left90Degree ----------------------------------solveByRecursion resolution----------------------------------
求解出1种解的情况后，能横向翻转和纵向翻转，实际就有4*2=8种解的情况了。
相关推荐
n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---...
迭代与递归的区别
回溯法递归实现和非递归实现.解用向量表示，解分量集合有1、2两个元素，一表示放入背包，二表示不放入背包。具有一般性。
公司要求分享迭代和递归函数，在周末的时间整理了一个简单的PPT，在这里也分享给大家，互相学些，相互总结。
DNS迭代查询和递归查询的区别.docx
迭代与递归算法
//回溯前是否保存临时的背包。如果临时的价值大于现在的价值就保存 if(v) { v= tv; for(int j=0;j;j++) { r[j] = tr[j];//保存结果 } } if (add)//用到上面的 { tr[i] = 0; tw -=...
c语言-阶乘算法(迭代和递归).docx
C++：斐波那契数列（迭代和递归）
用回溯法求解八数码问题，使用的是递归的方法来求解。
递归回溯，像8皇后问题，本质上和多重for 循环是一样的
使用迭代和递归两种方法反转链表.docx
C语言实现 求二项式各项系数（迭代，递归法）
DNS递归和迭代
用回溯法实现子集和问题的完整代码
Oracle使用递归查询。查询树结构的sql。在Oracle中，递归查询要用到start with ……connect by prior……
迭代法、穷举搜索法、递推法、递归、回溯法、贪婪法、分治法、动态规划法
递归回溯法求解整数线性规划及MATLAB实现.pdf
牛顿迭代算法与递归算法的概念和区别 很有帮助
C++实现的快速幂算法-Pow(x,n)，本算法实现了迭代和递归两个版本。