贴一个自己的解法,思路很简单,就是以水平方向为X轴,60度那条斜线为Y轴,确定一个菱形块的位置,再对菱形块中的两个三角形按上下进行区分,确定好坐标后,对整个72格的空间进行递归搜索,最后对搜索出来的结果进行检查,发现是对称的就删除其中的一个。程序最终找到5885个结果。程序写的有点乱,期待大牛们的作品。
代码:
//DRAW 定义为1时可以在屏幕上输出彩色的解决方案 #define DRAW 0 #include "windows.h" #include "wincon.h" #include "stdlib.h" #include "stdio.h" #include "string.h" const int zh[12] = {0, 1, 6, 7, 2, 3, 8, 9, 4, 5, 10, 11}; const int cs[8] = {11, 13, 13, 11, 9, 7, 5, 3}; const int gs[13] = {0, 1, 4, 16, 22, 34, 40, 52, 64, 70, 76, 88, 94}; const short int color[12] = {1,2,3,4,5,6,9,10,11,12,13,14}; const unsigned int b[94][6] = { {0x000001,0x010000,0x010001,0x000100,0x000101,0x010100}, {0x010000,0x010001,0x020000,0x000101,0x010100,0x010101}, {0x010001,0x000100,0x000101,0x010100,0x010101,0x000200}, {0x010001,0x000101,0x010100,0x010101,0x020100,0x010200}, {0x020001,0x000100,0x000101,0x010100,0x010101,0x020100}, {0x000001,0x000100,0x000101,0x000200,0x000201,0x010200}, {0x010001,0x020000,0x000101,0x010100,0x000200,0x000201}, {0x000001,0x010000,0x010001,0x020000,0x020001,0x000100}, {0x000001,0x010000,0x010001,0x010100,0x010101,0x010200}, {0x020000,0x020001,0x010101,0x020100,0x000201,0x010200}, {0x010000,0x010001,0x010100,0x010101,0x000201,0x010200}, {0x020001,0x010101,0x020100,0x000200,0x000201,0x010200}, {0x000001,0x000100,0x000101,0x010100,0x010101,0x020100}, {0x000001,0x010000,0x000100,0x000101,0x000200,0x000201}, {0x010001,0x020000,0x020001,0x000101,0x010100,0x000200}, {0x000001,0x010000,0x010001,0x020000,0x020001,0x020100}, {0x010000,0x010001,0x000100,0x000101,0x010100,0x010101}, {0x000001,0x010001,0x000100,0x000101,0x010100,0x000200}, {0x010001,0x020000,0x000101,0x010100,0x010101,0x020100}, {0x000000,0x000001,0x010000,0x010001,0x000100,0x000101}, {0x010001,0x000101,0x010100,0x010101,0x000200,0x010200}, {0x000001,0x010000,0x010001,0x020000,0x000101,0x010100}, {0x000000,0x000001,0x010000,0x010001,0x000101,0x010100}, {0x010001,0x010100,0x010101,0x000200,0x000201,0x010200}, {0x000001,0x010001,0x020000,0x000100,0x000101,0x010100}, {0x000001,0x010000,0x000100,0x000101,0x010100,0x010101}, {0x000001,0x010000,0x010001,0x000100,0x000101,0x000200}, {0x010001,0x020000,0x020001,0x000101,0x010100,0x020100}, {0x000000,0x000001,0x010001,0x000100,0x000101,0x010100}, {0x010001,0x000101,0x010100,0x000200,0x000201,0x010200}, {0x000001,0x010000,0x010001,0x020000,0x000100,0x000101}, {0x000001,0x010000,0x010001,0x000100,0x010100,0x010101}, {0x000001,0x010000,0x010001,0x000101,0x010100,0x000200}, {0x020000,0x020001,0x000101,0x010100,0x010101,0x020100}, {0x000000,0x000001,0x000100,0x000101,0x010100,0x010101}, {0x010001,0x000101,0x010100,0x000200,0x000201,0x000300}, {0x010001,0x020000,0x020001,0x030000,0x000101,0x010100}, {0x000000,0x000001,0x010000,0x010001,0x010100,0x010101}, {0x010001,0x010100,0x010101,0x000201,0x010200,0x000300}, {0x020001,0x030000,0x000101,0x010100,0x010101,0x020100}, {0x010000,0x010001,0x020000,0x000100,0x000101,0x010100}, {0x000001,0x010001,0x000100,0x000101,0x010100,0x010101}, {0x000001,0x010000,0x000100,0x000101,0x010100,0x000200}, {0x010001,0x020000,0x020001,0x000101,0x010100,0x010101}, {0x000000,0x000001,0x010000,0x010001,0x000100,0x010100}, {0x010001,0x000101,0x010100,0x010101,0x000201,0x010200}, {0x010000,0x010001,0x000100,0x000101,0x010100,0x000200}, {0x010001,0x020001,0x000101,0x010100,0x010101,0x020100}, {0x000000,0x000001,0x010000,0x000100,0x000101,0x010100}, {0x010001,0x000101,0x010100,0x010101,0x000200,0x000201}, {0x000001,0x010000,0x010001,0x020000,0x000100,0x010100}, {0x000001,0x010000,0x010001,0x000101,0x010100,0x010101}, {0x010001,0x020000,0x000100,0x000101,0x010100,0x010101}, {0x000001,0x000100,0x000101,0x010100,0x010101,0x000200}, {0x010001,0x020000,0x000101,0x010100,0x010101,0x010200}, {0x010000,0x010001,0x020000,0x020001,0x000101,0x010100}, {0x010001,0x000100,0x000101,0x010100,0x010101,0x010200}, {0x010001,0x010100,0x010101,0x020100,0x000201,0x010200}, {0x010000,0x010001,0x000101,0x010100,0x010101,0x000200}, {0x020001,0x000101,0x010100,0x010101,0x020100,0x010200}, {0x010000,0x010001,0x000101,0x010100,0x010101,0x020100}, {0x010001,0x000100,0x000101,0x010100,0x000200,0x000201}, {0x010001,0x000101,0x010100,0x010101,0x020100,0x000200}, {0x000001,0x010000,0x010001,0x020000,0x010100,0x010101}, {0x010001,0x020000,0x020001,0x000100,0x000101,0x010100}, {0x000001,0x000100,0x000101,0x010100,0x010101,0x010200}, {0x010001,0x020000,0x010100,0x010101,0x000201,0x010200}, {0x010000,0x010001,0x000101,0x010100,0x000200,0x000201}, {0x020001,0x000101,0x010100,0x010101,0x020100,0x000200}, {0x000001,0x010000,0x010001,0x010100,0x010101,0x020100}, {0x010001,0x000100,0x000101,0x010100,0x010101,0x020100}, {0x000001,0x000100,0x000101,0x010100,0x000200,0x000201}, {0x010001,0x020000,0x000101,0x010100,0x010101,0x000200}, {0x000001,0x010000,0x010001,0x020000,0x020001,0x010100}, {0x010000,0x010001,0x000101,0x010100,0x010101,0x010200}, {0x020001,0x010100,0x010101,0x020100,0x000201,0x010200}, {0x010001,0x000101,0x010100,0x010101,0x020100,0x020101}, {0x000000,0x000001,0x010000,0x000100,0x000101,0x000200}, {0x020001,0x010101,0x020100,0x020101,0x000201,0x010200}, {0x000000,0x000001,0x010000,0x010001,0x020000,0x010100}, {0x010001,0x010100,0x010101,0x000201,0x010200,0x010201}, {0x010001,0x020000,0x000100,0x000101,0x010100,0x000200}, {0x010001,0x000101,0x010100,0x010101,0x010200,0x010201}, {0x010000,0x010001,0x020000,0x000101,0x010100,0x000200}, {0x020001,0x000101,0x010100,0x010101,0x020100,0x020101}, {0x000000,0x000001,0x000100,0x000101,0x010100,0x000200}, {0x020001,0x010101,0x020100,0x000201,0x010200,0x010201}, {0x000000,0x000001,0x010000,0x010001,0x020000,0x000100}, {0x000000,0x000001,0x010000,0x010001,0x020000,0x020001}, {0x000001,0x000100,0x000101,0x000200,0x000201,0x000300}, {0x020001,0x030000,0x010101,0x020100,0x000201,0x010200}, {0x000000,0x000001,0x000100,0x000101,0x000200,0x000201}, {0x020001,0x010101,0x020100,0x000201,0x010200,0x000300}, {0x000001,0x010000,0x010001,0x020000,0x020001,0x030000} }; const unsigned int qp[72] = { 0x010001,0x020000,0x020001,0x030000,0x030001,0x040000, 0x040001,0x050000,0x050001,0x060000,0x060001,0x000101, 0x010100,0x010101,0x020100,0x020101,0x030100,0x030101, 0x040100,0x040101,0x050100,0x050101,0x060100,0x060101, 0x000200,0x000201,0x010200,0x010201,0x020200,0x020201, 0x030200,0x030201,0x040200,0x040201,0x050200,0x050201, 0x060200,0x000300,0x000301,0x010300,0x010301,0x020300, 0x020301,0x030300,0x030301,0x040300,0x040301,0x050300, 0x000400,0x000401,0x010400,0x010401,0x020400,0x020401, 0x030400,0x030401,0x040400,0x000500,0x000501,0x010500, 0x010501,0x020500,0x020501,0x030500,0x000600,0x000601, 0x010600,0x010601,0x020600,0x000700,0x000701,0x010700 }; unsigned char tb[12000][72]; unsigned char space[16][16][2];//放置棋盘的空间,各偏移4 int jl1[12];//哪个形状已被使用 int jl2[12];//该形状对应的翻转和旋转后状态 int m;//用了几个形状 int w;//找到的解法个数 void search(int n)//n为目前搜索的棋盘位置 { int i, j, k; int x, y, z; while (space[((qp[n]>>16)&0xFF)+4][((qp[n]>>8)&0xFF)+4][qp[n]&0xFF] != 12) n = n+1;//找到下一个空位 x = ((qp[n]>>16)&0xFF)+4; y = ((qp[n]>> 8)&0xFF)+4; for(i=0; i<12; i++) { if (jl1[i]) continue;//该形状已被使用 for(j=gs[i]; j<gs[i+1]; j++) { if ((qp[n]&0xFF) != (b[j][0]&0xFF)) continue; for(k=1; k<6; k++) { if (space[x+((b[j][k]>>16)&0xFF)-((b[j][0]>>16)&0xFF)][y+((b[j][k]>>8)&0xFF)-((b[j][0]>>8)&0xFF)][b[j][k]&0xFF] != 12) break; } if (k == 6)//找到一个形状可以放下 { for(k=0; k<6; k++) space[x+((b[j][k]>>16)&0xFF)-((b[j][0]>>16)&0xFF)][y+((b[j][k]>>8)&0xFF)-((b[j][0]>>8)&0xFF)][b[j][k]&0xFF] = i; jl1[i] = 1; jl2[m] = j; m = m+1; if (m == 12)//找到一个解法 { for(z=0; z<72; z++) tb[w][z] = zh[space[((qp[z]>>16)&0xFF)+4][((qp[z]>>8)&0xFF)+4][qp[z]&0xFF]]; w = w+1; m = m-1; for(k=0; k<6; k++) space[x+((b[j][k]>>16)&0xFF)-((b[j][0]>>16)&0xFF)][y+((b[j][k]>>8)&0xFF)-((b[j][0]>>8)&0xFF)][b[j][k]&0xFF] = 12; jl1[i] = 0; return; } else { search(n+1); m = m-1; for(k=0; k<6; k++) space[x+((b[j][k]>>16)&0xFF)-((b[j][0]>>16)&0xFF)][y+((b[j][k]>>8)&0xFF)-((b[j][0]>>8)&0xFF)][b[j][k]&0xFF] = 12; jl1[i] = 0; } } } } } int main() { int i, j, k, l, r, v; unsigned char tt[72]; HANDLE h; DWORD ut; FILE *fp; h = GetStdHandle(STD_OUTPUT_HANDLE); for(i=0; i<16; i++) { for(j=0; j<16; j++) { space[i][j][0] = 0; space[i][j][1] = 0; } } for(i=0; i<72; i++) space[((qp[i]>>16)&0xFF)+4][((qp[i]>>8)&0xFF)+4][qp[i]&0xFF] = 12; for(i=0; i<12; i++) jl1[i] = 0; //开始搜索 ut = GetTickCount(); w = m = 0; search(0); //对结果去掉重复的对称方案 for(i=0; i<w; i++) { if (tb[i][0] == 12) continue; r = 0; for(k=0; k<8; k++) { for(l=0; l<cs[k]; l++) { tt[r+l] = tb[i][r+cs[k]-1-l]; } r += cs[k]; } for(j=i+1; j<w; j++) { if (tb[j][0] == 12) continue; if (memcmp(tb[j], tt, 72) == 0) tb[j][0] = 12; } } printf("使用时间:%dms\n", GetTickCount()-ut); //要输入到屏幕上看直观方案吗? if (DRAW) { for(l=0; l<w; l++) { if (tb[l][0] == 12) continue; r = 72; for(i=7; i>=0; i--) { for(j=0; j<(13-cs[i])/2; j++) printf(" "); for(k=0,j=r-cs[i]; j<r; j++,k++) { SetConsoleTextAttribute(h, color[tb[l][j]]); if (i>1) { if (k&1) printf(""); else printf("▲"); } else { if (k&1) printf("▲"); else printf(""); } SetConsoleTextAttribute(h, 0x7); } printf("\n"); r -= cs[i]; } printf("\n"); } } //输出结果到文本文件 fp = fopen("out.txt", "wt"); for(l=0; l<w; l++) { if (tb[l][0] == 12) continue; r = 72; v = 11; for(i=7; i>=0; i--) { if (i == 1) v = v+1; for(j=0; j<v; j++) fprintf(fp, " "); for(k=0,j=r-cs[i]; j<r; j++,k++) { if (i>1) { if (k&1) { fprintf(fp, "%1X%1X%1X", tb[l][j], tb[l][j], tb[l][j]); } else { fprintf(fp, "%1X", tb[l][j]); } } else { if (k&1) { fprintf(fp, "%1X", tb[l][j]); } else { fprintf(fp, "%1X%1X%1X", tb[l][j], tb[l][j], tb[l][j]); } } } if (i>1) v = v-1; else v = v+1; fprintf(fp, "\n"); for(j=0; j<v; j++) fprintf(fp, " "); for(k=0,j=r-cs[i]; j<r; j++,k++) { if (i>1) { if (k&1) { fprintf(fp, "%1X", tb[l][j]); } else { fprintf(fp, "%1X%1X%1X", tb[l][j], tb[l][j], tb[l][j]); } } else { if (k&1) { fprintf(fp, "%1X%1X%1X", tb[l][j], tb[l][j], tb[l][j]); } else { fprintf(fp, "%1X", tb[l][j]); } } } if (i>1) v = v-1; else v = v+1; fprintf(fp, "\n"); r -= cs[i]; } fprintf(fp, "\n"); } fclose(fp); }