/**************************************************/ /*  スライドパズル最長手数面の探索/幅優先探索(2) */ /*        Computer&Puzzle 2004/2 by takaken */ /**************************************************/ #include #include #include /* BOARD_SIZEが4以上12以下になること(MEM=128MB) */ #define BOARD_WIDTH 4 /* ボード横長さ */ #define BOARD_HEIGHT 3 /* ボード縦長さ */ #define BOARD_SIZE (BOARD_WIDTH * BOARD_HEIGHT) typedef unsigned long u32; int BOARD[BOARD_SIZE]; int MOVAL[BOARD_SIZE][5]; /* 移動可能テーブル */ int PASCAL[BOARD_SIZE][3]; /* パスカルの三角形 */ int FACTOR[BOARD_SIZE-2]; /* 階乗値テーブル */ int MAX_FACTOR; /* (BOARD_SIZE-2)! */ int TBLSIZE; u32 *TABLE1; /* フラグテーブル1 */ u32 *TABLE2; /* フラグテーブル2 */ /****************************************************/ /* 各種テーブル作成 */ /****************************************************/ void Initialize(void) { int i, j, c, vect, x1, y1, x2, y2, hashsize; int diffy[] = {-1, 0, 1, 0}; int diffx[] = { 0, 1, 0,-1}; /* 巨大なフラグテーブルを確保する */ for (hashsize=1,i=BOARD_SIZE; i>=3; i--) hashsize *= i; TBLSIZE = ((hashsize - 1) / 32 + 1); if (NULL == (TABLE1 = calloc(TBLSIZE, sizeof(u32)))) { printf("フラグテーブル作成に失敗(1)\n"); exit(1); } if (NULL == (TABLE2 = calloc(TBLSIZE, sizeof(u32)))) { printf("フラグテーブル作成に失敗(2)\n"); exit(1); } /* MOVAL[位置][添字] */ for (i=0; i=0 && y2=0 && x2=0; i--,c++) FACTOR[i] = FACTOR[i+1] * c; MAX_FACTOR = FACTOR[0] * c; } /****************************************************/ /* 最少完全ハッシュ関数(局面のhash値を求める) */ /****************************************************/ int ChangeNumber(void) { int hash = 0, i, j, n, r, work[BOARD_SIZE-2]; /* 組合せ */ for (j=i=0,n=BOARD_SIZE-1,r=2; i=0; i--) for (j=i+1; j= c) { hash1 -= c; r--; BOARD[i] = BOARD_SIZE-2; } else BOARD[i] = work[j++]; } } /****************************************************/ /* 最後に残った局面(最長手数面)を表示する */ /****************************************************/ void Result(void) { int idx, pos, result = 0; int i, j, space, invert, tb[2]; u32 bit; /* フラグテーブルをスキャンする */ for (idx=0; idxBOARD[j]) invert++; } if (invert % 2) { BOARD[tb[0]] = BOARD_SIZE-2; BOARD[tb[1]] = BOARD_SIZE-1; } /* 表示 */ printf("[%d]",++result); for (i=0; i [1,1] */ if (!(TABLE2[idx] & bit)) TABLE2[idx] |= bit; } else { /* [0,1] -> [1,0] */ if (TABLE2[idx] & bit) { TABLE1[idx] |= bit; TABLE2[idx] ^= bit; } } } } } /****************************************************/ /* 幅優先探索 (TABLE1[] -> TABLE2[]) */ /****************************************************/ int Search(void) { int space, piece, i, count = 0; int idx1, idx2, pos, hash; u32 bit1, bit2; /* フラグテーブルをスキャンする */ for (idx1=0; idx1