total find = 8270
time = 23 sec
上面是 P4 3.0 单线程跑出来的结果,内存2G
简单说明一下上面的程序:
算法是普通的深度优先搜索,回溯算法
数据结构用数组
拼盘是 9*18的,9行,18列
BYTE Puzzle[MAXX][MAXY]={0};
每行有左右界
// 拼盘每行的左右界,大于等于左,小于右符合要求
CHAR BorderX[MAXX] = {0,0,0,0,0,0 ,0 , 1, 3};
CHAR BorderY[MAXX] = {0,3,5,7,9,11,13, 14, 14};
这样就规定了拼盘的范围,边界用
#define BORDER ' '
空白(就是可以填滑块)用
#define BLANK '+'
填进去的就用滑块序号
//每个滑块最多的状态
int bMaxSharp[MAXSHARP]={0};
滑块用一个 12 * 12 * 6的数组表示
work[12][12][6]
这个表示一共有12种滑块,每个滑块最多有12种状态,每个状态有6个数据(就是6个三角形)
6个数据用直角坐标表示,从00 - 36,0x12就表示 x=1,y=2
00 01 02 03 04 05 06
10 11 12 13 14 15 16
20 21 22 23 24 25 26
30 31 32 33 34 35 36
获取数据的xy坐标宏
#define GetSharpX(xy) ( (CHAR)(((BYTE)(xy))>>4) )
#define GetSharpY(xy) ( (CHAR)(((BYTE)(xy))&0x0F) )
规定列y mod 2 = 0的时候,表示是上三角,y mod 2 = 1的时候表示下三角
Puzzle的列y 也是这样规定的,这样的话,滑块的y 和 Puzzle的y 同余,即三角类型匹配
#define CanOverlap(PuzzleY,SharpY) ((BYTE)((PuzzleY)&1) == (BYTE)((SharpY)&1))?1:0
填入大拼盘Puzzle的时候,xy算法是
//x = xi-x0+NowX;
//y = yi-y0+NowY;
x0永远是0,所以可以省略