四色立方体回溯法（迭代和递归）

原题来自某公司的一道面试题：

 

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种解的情况了。