■ 「おしどり遊び」を解く
/*
* oshidori.c - 「おしどり遊び」を解く
*
* Copyright (c) 2001 AOK. (oshidori.c Rev.1 - 2001.5.25)
*
* 黒石３個，白石３個を次のように並べます。
*
* ｜●｜○｜●｜○｜●｜○｜ ｜ ｜
*
* 並んだ２個の碁石を、そのままの順で空いている所
* へ移動させることを繰り返し、下図のようにする。
*
* ｜ ｜ ｜○｜○｜○｜●｜●｜●｜
*
*/
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
/**** ●: 1 ○: 2 －: 0 ****/
#define MAX_LEN 8 /* 移動可能な範囲 */
#define QUE_LEN 100 /* 大きめにしないとオーバーフロー */
const char *start = "12121200";
const char *end = "00222111";
typedef struct {
char cond[MAX_LEN+1]; /* 石の状態 */
int prev; /* 手前の局面の位置 */
} NODE;
NODE que[QUE_LEN]; /* 局面の保存用 */
int sp; /* 探索位置 */
int mp; /* 局面数 */
/* 同一の局面を探す（手抜きです）*/
int search(const char* s)
{
int i;
for (i=0; i<mp; i++)
if (strcmp(que[i].cond, s)==0) return 1;
return 0;
}
/* 表示用 */
void display(int c)
{
static int n = 0;
int i, t;
if (c == -1) return;
display(que[c].prev);
t = strlen(que[c].cond);
printf("%d.", n++);
for (i=0; i<t; i++) {
switch (que[c].cond[i]) {
case '1': printf("●"); break;
case '2': printf("○"); break;
case '0': printf("－"); break;
}
}
putchar('\n');
}
/* 石を移動する */
void move(void)
{
int i, j;
char t[2], *f1, *f2, q[MAX_LEN+1], r[MAX_LEN+1];
for (i=0; i<MAX_LEN-1; i++) {
t[0]= que[sp].cond[i]; t[1] = que[sp].cond[i+1];
if ((t[0]=='0') || (t[1]=='0')) continue;
strcpy(r, que[sp].cond);
r[i] = '0'; r[i+1] = '0'; f1 = r;
while ((f2 = strstr(f1, "00"))!=NULL) {
if ((r==f2) && (*(f2+2)=='0')) {
f1 = ++f2; continue;
}
if ((r!=f2) && (*(f2-1)=='0') &&
((*(f2+2)=='0') || (*(f2+2)==0))) {
f1 = ++f2; continue;
}
strcpy(q, r);
q[(f2-r)/sizeof(char)] = t[0];
q[(f2-r)/sizeof(char)+1] = t[1];
if (!search(q)) {
if (mp >= QUE_LEN) {
puts("エラー：局面数がキューの上限を超えました。");
exit(1);
}
strcpy(que[mp].cond, q);
que[mp].prev = sp;
if (strcmp(q, end)==0) {
display(mp);
printf("\n--- 探索数=%d, 局面数=%d\n", sp, mp+1);
for (j=0; j<=mp; j++) {
printf("[%2d-%2d] %s ", que[j].prev, j, que[j].cond);
if (j%4==3) putchar('\n');
}
exit(0);
}
mp++;
}
f1 = ++f2;
}
}
}
/* メインルーチン */
int main()
{
strcpy(que[0].cond, start);
que[0].prev = -1; sp = 0; mp = 1;
while (sp != mp) { move(); ++sp; }
return 0;
}
/* --- 実行結果 -------------------------------------
0.●○●○●○－－
1.●－－○●○○●
2.●●○○－－○●
3.●●○○○●－－
4.－－○○○●●●
--- 探索数=20, 局面数=45
[-1- 0] 12121200 [ 0- 1] 00121212 [ 0- 2] 10021221 [ 0- 3] 12001212
[ 0- 4] 12100221 [ 1- 5] 21100212 [ 1- 6] 12120012 [ 1- 7] 21121002
[ 2- 8] 11220021 [ 2- 9] 12221001 [ 3-10] 12211002 [ 4-11] 00112221
[ 4-12] 12122001 [ 5-13] 20011212 [ 5-14] 21112200 [ 6-15] 10022112
[ 7-16] 20021112 [ 7-17] 21001122 [ 8-18] 00221121 [ 8-19] 11002221
[ 8-20] 11222100 [ 9-21] 12001221 [ 9-22] 12200211 [10-23] 00211122
[10-24] 10011222 [10-25] 12200112 [11-26] 22110021 [11-27] 22112001
[12-28] 00122121 [12-29] 10022211 [12-30] 12002121 [13-31] 21210012
[13-32] 22111002 [13-33] 21211200 [14-34] 20012211 [14-35] 21002211
[15-36] 11122002 [16-37] 22100112 [16-38] 21120012 [16-39] 21221100
[17-40] 21110022 [18-41] 21200121 [19-42] 11222001 [19-43] 11212200
[20-44] 00222111
------------------------------------------------- */