贴一个自己的解法,思路很简单,就是以水平方向为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);
}
[课程]Android-CTF解题方法汇总!