请教：立体拼图游戏的问题

Question

要做的这个立体拼图游戏，它由几种不同形状的拼图片组成（有点像七巧板，但是它比较厚），每个拼图片的长宽都一样。每个拼图片用点和空格表示，如下图：  o  
 ooo 
ooooo 
 ooo 
  o     表示     给定6种形状的拼图片，把它们拼接成一个正立方体，要求给出最后拼出的这个正立方体的展开图，就是一个T形的6个拼图片的排列，每个拼图片也是用点和空格表示。
各位高手，这个该怎么去想？给个思路吧，谢谢！

Answer 1

奇怪，那个举例中上传的拼图片怎么看不到？
在我的相册里，试试这个链接   http://hi.csdn.net/space-9851045-do-album-picid-850627.html

Answer 2

我给的例子只是一个拼图片的形状，不过用点和空格来表示，它代表的实际的图形是2楼huntor帮忙贴出来的（怎么贴的，我没贴成）。
这里的所有拼图片都是用点和空格来表示，便于编程，每个拼图片的最大长和最大宽都是完全一样的。题目的要求是：
给定6种形状的拼图片，即一共6个拼图片，把它们拼接成一个正立方体，要求给出最后拼出的这个正立方体的展开图，是6个拼图片排成一个T形的图。

Answer 3

和这些是一样的：
http://en.wikipedia.org/wiki/Happy_Cube
http://www.amazon.com/Marble-Cube-Foam-Puzzle-Single/dp/B0034SGVF8/ref=sr_1_1?ie=UTF8&qid=1310216561&sr=8-1

Answer 4

嗯，要具体的图啊，不可以对任意组合进行分析吗？如果换了不同的6块拼图片，还要重新再分析？
我看能不能贴上来图，http://hi.csdn.net/attachment/201107/13/0_1310596021wdKK.gif

Answer 5

昨天开始试了个思路是T字形，排a,b,c,d,e,f六个图形，先求全排列然后测试12条棱是否都匹配，后来放弃了6个数全排列是720种，遍历起来不可怕，可怕的是要考虑旋转，翻转等因素，如果要写通用方法，那么就必须考虑每个面正面4种，反面4种的排列方式，6个面就是8的6次方=26W种，乘上720种全排列就是1.8亿多....效率实在不行。目前考虑是按一般人拼立方体的思路来找，先确定一个面，对其一条边找出与其匹配的另外一个面的一条边，然后形成一个 V 型，然后对两条相邻边找出第三个面能同时匹配这两条边...但是递归起来 面的旋转和翻转还是让我接近疯狂了。期待高人.....

Answer 6

写了一个，发现测试比写代码本身麻烦得多。
为了测试和显示效果方便，写了随机产生待拼图碎片的代码，每次运行时输入碎片大小，程序自动随机生成6张拼图碎片，并试图发现可能的拼图方案，然后输出拼图结果。
补充说明：
1）由于入口数据难得，本程序以6张图能不冲突地拼成一个立方体为标准，并未要求所有格子全是满的。如欲达到此要求，可在check()方法中稍做调整。
2）随机生成入口碎片的部分，立方体体积越大生成合格碎片的几率越低，目前只测试到5格，概率还可接受。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.Scanner;public class CubeMatch { // 返回整数数组is[]的全排列
public static List<int[]> permutation(List<int[]>list, int[] is) {
List<int[]> r = new ArrayList<int[]>();
if (list.size()==0) 
r.add(Arrays.copyOfRange(is, 0, 1));
else 
for (int i=0; i<list.size(); i++) {
int[] ois = list.get(i);
for (int j=0; j<=ois.length; j++) {
int[] nis = new int[ois.length+1];
for (int k=0; k<nis.length; k++) 
nis[k] = k==j? is[0] : (k<j? ois[k]: ois[k-1]);
r.add(nis);
}
}
if (is.length==1) return r;
else {
int[] nis = Arrays.copyOfRange(is, 1, is.length);
return permutation(r, nis);
}
} // 拼图匹配用的方法
public static Arris[] put(int[] permu, int[] edges) {
Arris[] as = new Arris[24];
for (int i=0; i<4; i++) {
as[i*2] = new Arris(0,i);
as[i*2+1]= new Arris(permu[i], edges[i]);
as[8+i*2]= new Arris(permu[i],edgePlus(edges[i],1));
as[8+i*2+1]= new Arris(permu[edgePlus(i,1)],edgePlus(edges[edgePlus(i,1)],3));
as[16+2*i] = new Arris(permu[4], edgePlus(edges[4],(4-i)%4));
as[16+2*i+1] = new Arris(permu[i], edgePlus(edges[i],2));
}
return as;
}
public static boolean check(Arris[] as, List<int[][]> ps) {
for (int i=0; i<12; i++) {
int[] e1 = edata(ps.get(as[2*i].piece), as[2*i].edge);
int[] e2 = edata(ps.get(as[2*i+1].piece), as[2*i+1].edge);
if (i<4||i>=8) {
for (int j=0; j<e1.length; j++)
if (e1[j]+e2[j]>1) return false;
}
else
for (int j=0; j<e1.length; j++)
if (e1[j]+e2[e1.length-1-j]>1) return false;
}
return true;
}
public static int edgePlus(int old, int addon) {
return old<4? (old+addon)%4 : 4+(old+addon)%4;
}
public static int[] edata(int[][] piece, int edge) {
int n=piece.length,x,y;
int[] is = new int[n];
for (int i=0; i<n; i++) {
if (edge%2==0) {
x = edge==0||edge==6? n-1-i: i;
y = edge==0||edge==4? 0 : n-1;
} else {
x = edge==1||edge==7? 0: n-1;
y = edge==1||edge==5? i: n-1-i;
}
is[i] = piece[x][y];
}
return is;
}

//************* 输出结果用的方法 ***********************/
public static void output(List<int[][]> ps, int[] permu, int[] edges) {
int n = ps.get(0).length;
int[][] out = new int[n*4][n*3];
for (int i=0; i<out.length; i++) Arrays.fill(out[i], -1);
print(out, ps.get(0), 0, n, n, 0);
print(out, ps.get(permu[0]), edgePlus(edges[0],0), n, 0, 1);
print(out, ps.get(permu[1]), edgePlus(edges[1],3), 0, n, 2);
print(out, ps.get(permu[2]), edgePlus(edges[2],2), n, 2*n, 1);
print(out, ps.get(permu[3]), edgePlus(edges[3],1), 2*n, n, 2);
print(out, ps.get(permu[4]), edgePlus(edges[4],0), 3*n, n, 0);
for (int i=0; i<out.length; i++) {
for (int j=0; j<out[0].length; j++)
System.out.print((j%n==0?"   ":" ") + (out[i][j]==1? "■" : (out[i][j]==0?"□":" ")));
System.out.println(i%n==n-1?"\r\n":"");
}
}
public static void outputOrigin(List<int[][]> ps) {
int n = ps.get(0).length;
int[][] out = new int[n][n*6];
for (int i=0; i<out.length; i++) Arrays.fill(out[i], -1);
print(out, ps.get(0), 0, 0, 0, 0);
print(out, ps.get(1), 0, 0, n, 0);
print(out, ps.get(2), 0, 0, 2*n, 0);
print(out, ps.get(3), 0, 0, 3*n, 0);
print(out, ps.get(4), 0, 0, 4*n, 0);
print(out, ps.get(5), 0, 0, 5*n, 0);
for (int i=0; i<out.length; i++) {
for (int j=0; j<out[0].length; j++)
System.out.print((j%n==0?"   ":" ") + (out[i][j]==1? "■" : (out[i][j]==0?"□":" ")));
System.out.println(i%n==n-1?"\r\n":"");
}
}
public static void print(int[][] out, int[][] piece, int edge, int x0, int y0, int flag) {
int n = piece.length, x, y;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (edge%2==0) {
x = edge==0||edge==6? i: n-1-i;
y = edge==0||edge==4? j : n-1-j;
} else {
x = edge==1||edge==7? j: n-1-j;
y = edge==3||edge==7? i: n-1-i;
}
if (flag==1)
out[x0+i][y0+n-1-j] = piece[x][y];
else if (flag==2) 
out[x0+n-1-i][y0+j] = piece[x][y];
else
out[x0+i][y0+j] = piece[x][y];
}
}
} //************* 生成随机拼图碎片用的方法 ***********************/
public static List<int[][]> getRandomOrigin(int n) {
List<int[][]> list = new ArrayList<int[][]>();
for (int i=0; i<6; i++) list.add(randomPiece(n));
return list;
}
public static int[][] randomPiece(int n) {
int[][] is = new int[n][n];
Random rd = new Random();
for (int i=0; i<n; i++) 
for (int j=0; j<n; j++) 
is[i][j] = i>0&&i<n-1&&j>0&&j<n-1? 1 : //调整这里可让随机碎片更容易成功拼图
((i+j)%(n-1)==0? rd.nextInt(4)/3 : rd.nextInt(2)); 
return is;
}

public static void main(String[] args) throws Exception{
System.out.println("请输入拼图碎片尺寸（大于等于2），将随机生成6块拼图碎片：\r\n");
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
List<int[][]> ps = getRandomOrigin(n); //生成6张随机拼图碎片

System.out.println("拼图碎片：");
outputOrigin(ps); //输出生成的随机拼图碎片

int[] is = {1,2,3,4,5};
List<int[]> r = permutation(new ArrayList<int[]>(),is); //获得5张碎片的全排列

int x = 1024*32;
boolean bfind=false;
int count = 0;
for (int i=0; i<r.size(); i++) {
for (int j=0; j<x; j++) { //每个循环对应5张碎片8种方向的拼接法
count++;
int[] edges = new int[5];
for (int k=0; k<edges.length; k++) edges[k] = j>>>(k*3)&7;
Arris[] as = put(r.get(i), edges); //产生本次拼接的所有棱边
if (check(as, ps)) { //检查拼接正确性
System.out.println("检查了" + count + "种可能，发现可行拼法如下：");
output(ps, r.get(i), edges); //输出可行的拼接方案
bfind=true;
break;
}
}
if (bfind) break;
}
if(bfind==false) System.out.println("检查了" + count + "种可能，未发现可行拼法。");
}
}//代表棱边的类
class Arris { 
public int piece, edge;
public Arris(int p, int e) {
piece=p;
edge=e;
}
}

Answer 7

原来的代码是：    public static void main(String[] args) throws Exception{
        System.out.println("请输入拼图碎片尺寸（大于等于2），将随机生成6块拼图碎片：\r\n");
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        List<int[][]> ps = getRandomOrigin(n); //生成6张随机拼图碎片
        ......
改成：    public static void main(String[] args) throws Exception{
        List<int[][]> ps = new ArrayList<int[][]>();
        //初始化6个二维数组is1~is6，每个数组代表一个碎片，1为有格，0为无格 
        ps.add(is1);
        ps.add(is2);
        ps.add(is3);
        ps.add(is4);
        ps.add(is5);
        ps.add(is6);
就可以了