ホームに戻る
総当り式さめがめ自動解法検索
#include <stdio.h>
/*
さめがめを総当りによって自動で解くプログラムです。
ステージの横幅と縦幅を設定して、
stage_data の配列にコマの状態をセットしてください。
コマの種類は KOMA_1 〜 KOMA_5 の最大５種類までとなっています。
なおこのアルゴリズムでは 20×12 のステージなどの場合、
解法を導き出すまでに１０時間超の時間を要する場合があり、
その場合ステージを分割する等のアルゴリムの変更が望まれます。
*/
#define STAGE_WIDTH 6
#define STAGE_HEIGHT 10
/*
6*10 のステージの場合のメモリ状態の模式図です。
K はコマが置かれている部分 0 は空白です
P はステージの先頭ポインタ位置
E は P からのステージサイズの終端です
探索は P から E まで行います。
0000000
PKKKKK0
KKKKKK0
KKKKKK0
KKKKKK0
KKKKKK0
KKKKKK0
KKKKKK0
KKKKKK0
KKKKKK0
KKKKKKE
000000
*/
#define SPACE 0
#define KOMA_1 (1 << 0)
#define KOMA_2 (1 << 1)
#define KOMA_3 (1 << 2)
#define KOMA_4 (1 << 3)
#define KOMA_5 (1 << 4)
#define KOMA_ALL (KOMA_1 | KOMA_2 | KOMA_3 | KOMA_4 | KOMA_5)
#define KOMA_TAKEN (1 << 5)
#define LEFT (-1)
#define RIGHT (1)
#define UP (-STAGE_WIDTH-1)
#define DOWN (STAGE_WIDTH+1)
#define LIST_SIZE (KOMA_5 + 1)
#define STAGE_SIZE ((STAGE_WIDTH*STAGE_HEIGHT)+STAGE_HEIGHT-1)
#define MEMORY_SIZE ((STAGE_WIDTH*(STAGE_HEIGHT+2))+STAGE_HEIGHT+1)
typedef char stage;
static stage stage_data[STAGE_WIDTH * STAGE_HEIGHT] = {
KOMA_1,KOMA_1,KOMA_1,KOMA_1,KOMA_2,KOMA_4
,KOMA_1,KOMA_1,KOMA_1,KOMA_1,KOMA_4,KOMA_1
,KOMA_2,KOMA_1,KOMA_1,KOMA_3,KOMA_4,KOMA_2
,KOMA_5,KOMA_1,KOMA_4,KOMA_3,KOMA_4,KOMA_2
,KOMA_1,KOMA_3,KOMA_4,KOMA_1,KOMA_1,KOMA_1
,KOMA_2,KOMA_3,KOMA_1,KOMA_1,KOMA_1,KOMA_2
,KOMA_2,KOMA_1,KOMA_1,KOMA_3,KOMA_2,KOMA_2
,KOMA_1,KOMA_1,KOMA_1,KOMA_1,KOMA_1,KOMA_1
,KOMA_1,KOMA_1,KOMA_1,KOMA_1,KOMA_1,KOMA_5
,KOMA_3,KOMA_3,KOMA_1,KOMA_1,KOMA_2,KOMA_2
};
// 残りコマ数を記録するリスト
static int first_list[LIST_SIZE]; // 初期状態のリスト
static int now_list[LIST_SIZE]; // 現在の状態のリスト
// コマが配置されるステージ
static stage first_stage[MEMORY_SIZE]; // 初期状態のステージ
static stage now_stage[MEMORY_SIZE]; // 現在のステージ
// ステージアクセス用の先頭ポインタ
static stage *pfirst_stage = &first_stage[STAGE_WIDTH + 1];
static stage *pnow_stage = &now_stage[STAGE_WIDTH + 1];
void initStage(stage *sd);
void resetStage();
int takeKoma(int index);
void printList();
void printStage();
static void clearList(int num);
static inline void addList(stage koma);
static inline void subList(stage koma);
static inline int getListTotal();
static void clearStage(stage *pstage, int num);
static inline stage getKoma(int index);
static inline int cantTakeKoma(int index);
static inline void checkRoundKoma(int index);
static inline void downKoma(int index, int d);
static inline void downSlideKoma(int index);
static inline void leftKoma(int index, int d);
static inline void leftSlideKoma(int index, int d);
// 初期状態、現在のリストを num でクリア
void clearList(int num){
int i;
for(i = 0; i < LIST_SIZE; i++){
first_list[i] = num;
now_list[i] = num;
}
}
// 現在のリストにおいて koma について１を足す
inline void addList(stage koma){
first_list[koma]++;
return;
}
// 現在のリストにおいて koma について１を引く
inline void subList(stage koma){
now_list[koma]--;
return;
}
// 現在の全コマ数を返す
inline int getListTotal(){
return (now_list[KOMA_1] + now_list[KOMA_2] + now_list[KOMA_3] + now_list[KOMA_4] + now_list[KOMA_5]);
}
// ステージの全メモリ領域を num で埋める
void clearStage(stage *pstage, int num){
int i;
for(i = 0; i < MEMORY_SIZE; i++){
pstage[i] = num;
}
return;
}
// 初期状態の設定 resetStage で現在の状態へのコピーをしている
void initStage(stage *sd){
int i, t;
int index;
clearList(0);
clearStage(first_stage, 0);
clearStage(now_stage, 0);
for(t = 0; t < STAGE_HEIGHT; t++){
for(i = 0; i < STAGE_WIDTH; i++){
index = t * STAGE_WIDTH + i;
addList(sd[index]);
pfirst_stage[index + t] = sd[index];
}
}
resetStage();
return;
}
// 現在の状態に初期状態をコピー 要は現在の状態を初期状態に
void resetStage(){
int i;
now_list[KOMA_1] = first_list[KOMA_1];
now_list[KOMA_2] = first_list[KOMA_2];
now_list[KOMA_3] = first_list[KOMA_3];
now_list[KOMA_4] = first_list[KOMA_4];
now_list[KOMA_5] = first_list[KOMA_5];
for(i = 0; i < STAGE_SIZE; i++){
pnow_stage[i] = pfirst_stage[i];
}
return;
}
// インデックスからコマを返す
inline stage getKoma(int index){
return pnow_stage[index];
}
// コマがとれれば 0 を返す とれなければ 1 を返す
inline int cantTakeKoma(int index){
if(getKoma(index) & SPACE)return 1;
if(getKoma(index) & getKoma(index + LEFT))return 1;
if(getKoma(index) & getKoma(index + UP))return 1;
if(getKoma(index) & getKoma(index + RIGHT))return 0;
if(getKoma(index) & getKoma(index + DOWN))return 0;
return 1;
}
// とれるコマを縦横探索する とれる場合は KOMA_TAKEN のフラグをたてる
inline void checkRoundKoma(int index){
if(getKoma(index) & KOMA_TAKEN)return;
subList(getKoma(index));
pnow_stage[index] |= KOMA_TAKEN;
if(getKoma(index) & getKoma(index + UP))checkRoundKoma(index + UP);
if(getKoma(index) & getKoma(index + LEFT))checkRoundKoma(index + LEFT);
if(getKoma(index) & getKoma(index + DOWN))checkRoundKoma(index + DOWN);
if(getKoma(index) & getKoma(index + RIGHT))checkRoundKoma(index + RIGHT);
return;
}
inline void downKoma(int index, int d){
if(getKoma(index)){
if(getKoma(index) & KOMA_TAKEN){
downKoma(index + UP, d + DOWN);
}
else{
pnow_stage[index + d] = getKoma(index);
downKoma(index + UP, d);
}
return;
}
if(d == 0)return;
pnow_stage[index + d] = SPACE;
downKoma(index, d + UP);
return;
}
inline void downSlideKoma(int index){
if(!getKoma(index))return;
downKoma(index, 0);
downSlideKoma(++index);
}
inline void leftKoma(int index, int d){
if(!getKoma(index + d))return;
pnow_stage[index] = getKoma(index + d);
pnow_stage[index + d] = SPACE;
leftKoma(index + UP, d);
return;
}
inline void leftSlideKoma(int index, int d){
if(index + d == STAGE_SIZE)return;
if(getKoma(index)){
leftSlideKoma(++index, 1);
}
else if(!getKoma(index + d)){
leftSlideKoma(index, ++d);
}
else{
leftKoma(index, d);
leftSlideKoma(++index, 1);
}
return;
}
// インデックスのコマを取る とれない場合は 0 を返す とれれば現在の状態を更新して 1 を返す
int takeKoma(int index){
if(cantTakeKoma(index))return 0;
checkRoundKoma(index);
downSlideKoma(STAGE_SIZE - STAGE_WIDTH);
leftSlideKoma(STAGE_SIZE - STAGE_WIDTH, 1);
return 1;
}
void printList(){
printf("KOMA_1= %d ", now_list[KOMA_1]);
printf("KOMA_2= %d ", now_list[KOMA_2]);
printf("KOMA_3= %d ", now_list[KOMA_3]);
printf("KOMA_4= %d ", now_list[KOMA_4]);
printf("KOMA_5= %d ", now_list[KOMA_5]);
putchar('\n');
return;
}
void printStage(){
int i, t;
for(t = 0; t < STAGE_HEIGHT; t++){
for(i = 0; i < STAGE_WIDTH; i++){
switch(getKoma(t * (STAGE_WIDTH + 1) + i) & KOMA_ALL){
case SPACE:
putchar(' ');
break;
case KOMA_1:
putchar('A');
break;
case KOMA_2:
putchar('B');
break;
case KOMA_3:
putchar('C');
break;
case KOMA_4:
putchar('D');
break;
case KOMA_5:
putchar('E');
break;
default:
break;
}
}
putchar('\n');
}
return;
}
int main(){
int i;
int index = 0;
int take_flag;
int buffer[STAGE_SIZE >> 1];
for(i = 0; i < (STAGE_SIZE >> 1); i++){
buffer[i] = 0;
}
initStage(stage_data);
for(;;){
take_flag = takeKoma(buffer[index]);
if(take_flag){
index++;
continue;
}
buffer[index]++;
if(buffer[index] - STAGE_SIZE == 0){
if(!getKoma(STAGE_SIZE - STAGE_WIDTH)){
printf("\nClear!\n");
for(i = 0; i < index; i++){
printf("(%d,%d),", buffer[i] % (STAGE_WIDTH + 1), buffer[i] / (STAGE_WIDTH + 1));
}
break;
}
if(index == 0){
printf("\nThis stage cannot be solved!\n");
break;
}
buffer[index - 1]++;
for(i = index; i < (STAGE_SIZE >> 1); i++){
buffer[i] = 0;
}
index = 0;
resetStage();
}
}
return 0;
}
