●プログラムリスト１
/*
* trytry.c : ペグ・ソリテア「トライトライ」
*
* Copyright (C) 2002 Makoto Hiroi
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define SIZE 25
#define MAX_JUMP 23
/* 跳び先表 */
const char jump_table[][SIZE] = {
{ 2, 5, 3, 7, -1}, /* 0 */
{ 3, 6, 4, 8, -1}, /* 1 */
{ 3, 4, 5, 9, 6, 11, -1}, /* 2 */
{ 6, 10, 7, 12, -1}, /* 3 */
{ 3, 2, 7, 11, 8, 13, -1}, /* 4 */
{ 2, 0, 6, 7, 9, 14, 10, 16, -1}, /* 5 */
{ 3, 1, 7, 8, 10, 15, 11, 17, -1}, /* 6 */
{ 3, 0, 6, 5, 11, 16, 12, 18, -1}, /* 7 */
{ 4, 1, 7, 6, 12, 17, 13, 19, -1}, /* 8 */
{ 5, 2, 10, 11, 15, 21, -1}, /* 9 */
{ 6, 3, 11, 12, 15, 20, 16, 22, -1}, /* 10 */
{ 6, 2, 7, 4, 10, 9, 12, 13, 16, 21, 17, 23, -1}, /* 11 */
{ 7, 3, 11, 10, 17, 22, 18, 24, -1}, /* 12 */
{ 8, 4, 12, 11, 18, 23, -1}, /* 13 */
{ 9, 5, 15, 16, -1}, /* 14 */
{10, 6, 16, 17, -1}, /* 15 */
{10, 5, 11, 7, 15, 14, 17, 18, -1}, /* 16 */
{11, 6, 12, 8, 16, 15, 18, 19, -1}, /* 17 */
{12, 7, 17, 16, -1}, /* 18 */
{13, 8, 18, 17, -1}, /* 19 */
{15, 10, 21, 22, -1}, /* 20 */
{15, 9, 16, 11, 22, 23, -1}, /* 21 */
{16, 10, 17, 12, 21, 20, 23, 24, -1}, /* 22 */
{17, 11, 18, 13, 22, 21, -1}, /* 23 */
{18, 12, 23, 22, -1}, /* 24 */
};
/* corner */
const char corner[SIZE] = {
1, 1,
0, 0, 0,
0, 0, 0, 0,
0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 1,
1, 0, 0, 0, 1,
};
/* edge */
const char edge[SIZE] = {
0, 0,
1, 0, 2,
1, 0, 0, 2,
1, 0, 0, 0, 2,
0, 0, 0, 0, 0, 0,
0, 3, 3, 3, 0,
};
/* 初期状態 */
const char init_data[SIZE] = {
1, 1,
1, 1, 1,
1, 1, 1, 1,
1, 1, 0, 1, 1,
1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1,
};
/* 盤面 */
char board[SIZE];
/* 跳び手順を格納 */
char move[MAX_JUMP][2];
/* コーナーのペグ数 */
int lower_value = 6;
/* 計測用 */
int start;
/* 辺の下限値 */
const char edge_value[8] = {
0, /* 000 */
0, /* 001 */
0, /* 010 */
1, /* 011 */
0, /* 100 */
0, /* 101 */
1, /* 110 */
1, /* 111 */
};
/* 辺の下限値を求めるマクロ */
#define GET_EDGE_VALUE(a,b,c) edge_value[(board[(a)]<<2) + (board[(b)]<<1) + board[(c)]]
/* 下限値の計算 */
int get_lower_value( int prev )
{
int low = lower_value - corner[prev];
int eg = edge[prev];
/* 辺のチェック */
if( eg != 1 ) low += GET_EDGE_VALUE( 2, 5, 9 );
if( eg != 2 ) low += GET_EDGE_VALUE( 4, 8, 13 );
if( eg != 3 ) low += GET_EDGE_VALUE( 21, 22, 23 );
return low;
}
/* ペグを動かす */
void move_piece( int n, int from, int del, int to )
{
board[from] = 0;
board[del] = 0;
board[to] = 1;
move[n][0] = from;
move[n][1] = to;
/* corner check (corner は from か to しかない)*/
if( corner[from] ){
lower_value--;
} else if( corner[to] ){
lower_value++;
}
}
/* ペグを元に戻す */
void back_piece( int from, int del, int to )
{
board[from] = 1;
board[del] = 1;
board[to] = 0;
/* corner check (corner は from か to しかない)*/
if( corner[from] ){
lower_value++;
} else if( corner[to] ){
lower_value--;
}
}
/* 手順を表示 */
void print_move( void )
{
int i, j;
for( i = 0, j = 1; i < MAX_JUMP; i++, j++ ){
printf("(%d, %d", move[i][0], move[i][1] );
for( ; j < MAX_JUMP; i++, j++ ){
if( move[i][1] != move[j][0] ) break;
printf(", %d", move[j][1] );
}
printf(")");
}
printf("\n時間 %d\n", clock() - start );
}
/* 手順の探索（反復深化＋下限値枝刈り法） */
void search_move( int n, int jc, int limit )
{
int prev = move[n - 1][1];
if( (jc + get_lower_value( prev )) > limit ) return;
if( n == MAX_JUMP ){
print_move(); exit( 0 );
} else {
int from, del, to, i;
for( from = 0; from < SIZE; from++ ){
if( !board[from] ) continue; /* ペグが無い */
i = 0;
while( (del = jump_table[from][i++]) != -1 ){
to = jump_table[from][i++];
if( board[del] && !board[to] ){
/* 跳び越せる */
move_piece( n, from, del, to );
search_move( n + 1, (prev == from ? jc : jc + 1), limit );
back_piece( from, del, to );
}
}
}
}
}
int main()
{
int limit;
/* 初期化 */
start = clock();
memcpy( board, init_data, SIZE );
/* 初手は [2, 11] に決め打ち */
move_piece( 0, 2, 6, 11 );
/* 初期状態の下限値は 9 */
for( limit = 9; limit <= MAX_JUMP; limit++ ){
printf("・・・手数 %d を探索中・・・\n", limit );
search_move( 1, 1, limit );
}
return 0;
}
戻る
●プログラムリスト２
/*
* trytry.c : ペグ・ソリテア「トライトライ」中央補償型の解
*
* Copyright (C) 2002 Makoto Hiroi
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define SIZE 25
#define MAX_JUMP 23
#define HOLE 11
/* 跳び先表 */
const char jump_table[][SIZE] = {
{ 2, 5, 3, 7, -1}, /* 0 */
{ 3, 6, 4, 8, -1}, /* 1 */
{ 3, 4, 5, 9, 6, 11, -1}, /* 2 */
{ 6, 10, 7, 12, -1}, /* 3 */
{ 3, 2, 7, 11, 8, 13, -1}, /* 4 */
{ 2, 0, 6, 7, 9, 14, 10, 16, -1}, /* 5 */
{ 3, 1, 7, 8, 10, 15, 11, 17, -1}, /* 6 */
{ 3, 0, 6, 5, 11, 16, 12, 18, -1}, /* 7 */
{ 4, 1, 7, 6, 12, 17, 13, 19, -1}, /* 8 */
{ 5, 2, 10, 11, 15, 21, -1}, /* 9 */
{ 6, 3, 11, 12, 15, 20, 16, 22, -1}, /* 10 */
{ 6, 2, 7, 4, 10, 9, 12, 13, 16, 21, 17, 23, -1}, /* 11 */
{ 7, 3, 11, 10, 17, 22, 18, 24, -1}, /* 12 */
{ 8, 4, 12, 11, 18, 23, -1}, /* 13 */
{ 9, 5, 15, 16, -1}, /* 14 */
{10, 6, 16, 17, -1}, /* 15 */
{10, 5, 11, 7, 15, 14, 17, 18, -1}, /* 16 */
{11, 6, 12, 8, 16, 15, 18, 19, -1}, /* 17 */
{12, 7, 17, 16, -1}, /* 18 */
{13, 8, 18, 17, -1}, /* 19 */
{15, 10, 21, 22, -1}, /* 20 */
{15, 9, 16, 11, 22, 23, -1}, /* 21 */
{16, 10, 17, 12, 21, 20, 23, 24, -1}, /* 22 */
{17, 11, 18, 13, 22, 21, -1}, /* 23 */
{18, 12, 23, 22, -1}, /* 24 */
};
/* corner */
const char corner[SIZE] = {
1, 1,
0, 0, 0,
0, 0, 0, 0,
0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 1,
1, 0, 0, 0, 1,
};
/* edge */
const char edge[SIZE] = {
0, 0,
1, 0, 2,
1, 0, 0, 2,
1, 0, 0, 0, 2,
0, 0, 0, 0, 0, 0,
0, 3, 3, 3, 0,
};
/* Group */
const char group[SIZE] = {
0, 1,
3, 2, 3,
0, 1, 0, 1,
3, 2, 3, 2, 3,
0, 1, 0, 1, 0, 1,
2, 3, 2, 3, 2
};
/* 初期状態 */
const char init_data[SIZE] = {
1, 1,
1, 1, 1,
1, 1, 1, 1,
1, 1, 0, 1, 1,
1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1,
};
/* 盤面 */
char board[SIZE];
/* 跳び手順を格納 */
char move[MAX_JUMP][2];
/* コーナーのペグ数 */
int lower_value = 6;
/* Group ごとのペグの個数 */
int rest_peg[4] = { 6, 6, 6, 6 };
/* 計測用 */
int start;
/* 辺の下限値 */
const char edge_value[8] = {
0, /* 000 */
0, /* 001 */
0, /* 010 */
1, /* 011 */
0, /* 100 */
0, /* 101 */
1, /* 110 */
1, /* 111 */
};
/* 辺の下限値を求めるマクロ */
#define GET_EDGE_VALUE(a,b,c) edge_value[(board[(a)]<<2) + (board[(b)]<<1) + board[(c)]]
/* 下限値の計算 */
int get_lower_value( int prev )
{
int low = lower_value - corner[prev];
int eg = edge[prev];
/* 辺のチェック */
if( eg != 1 ) low += GET_EDGE_VALUE( 2, 5, 9 );
if( eg != 2 ) low += GET_EDGE_VALUE( 4, 8, 13 );
if( eg != 3 ) low += GET_EDGE_VALUE( 21, 22, 23 );
return low;
}
/* ペグを動かす */
void move_piece( int n, int from, int del, int to )
{
board[from] = 0;
board[del] = 0;
board[to] = 1;
move[n][0] = from;
move[n][1] = to;
rest_peg[ group[from] ]--;
rest_peg[ group[del] ]--;
rest_peg[ group[to] ]++;
/* corner check (corner は from か to しかない)*/
if( corner[from] ){
lower_value--;
} else if( corner[to] ){
lower_value++;
}
}
/* ペグを元に戻す */
void back_piece( int from, int del, int to )
{
board[from] = 1;
board[del] = 1;
board[to] = 0;
rest_peg[ group[from] ]++;
rest_peg[ group[del] ]++;
rest_peg[ group[to] ]--;
/* corner check (corner は from か to しかない)*/
if( corner[from] ){
lower_value++;
} else if( corner[to] ){
lower_value--;
}
}
/* 手順を表示 */
void print_move( void )
{
int i, j;
for( i = 0, j = 1; i < MAX_JUMP; i++, j++ ){
printf("(%d, %d", move[i][0], move[i][1] );
for( ; j < MAX_JUMP; i++, j++ ){
if( move[i][1] != move[j][0] ) break;
printf(", %d", move[j][1] );
}
printf(")");
}
printf("\n時間 %d\n", clock() - start );
}
/* 手順の探索 */
void search_move( int n, int jc, int limit )
{
int prev = move[n - 1][1];
if( (jc + get_lower_value( prev )) > limit ) return;
if( n == MAX_JUMP && board[HOLE] ){
print_move(); exit( 0 );
} else {
int from, del, to, i;
for( from = 0; from < SIZE; from++ ){
if( !board[from] ) continue; /* ペグが無い */
i = 0;
while( (del = jump_table[from][i++]) != -1 ){
to = jump_table[from][i++];
if( board[del] && !board[to] ){
/* 跳び越せる */
move_piece( n, from, del, to );
if( prev == from ){
search_move( n + 1, jc, limit );
} else {
if( jc < limit - 2 ||
(jc == limit - 2 && group[from] != 3) ||
(jc == limit - 1 && group[from] == 3 && rest_peg[3] == 1)){
search_move( n + 1, jc + 1, limit );
}
}
back_piece( from, del, to );
}
}
}
}
}
int main()
{
int limit;
/* 初期化 */
start = clock();
memcpy( board, init_data, SIZE );
/* 初手は [2, 11] に決め打ち */
move_piece( 0, 2, 6, 11 );
/* 初期状態の下限値は 9 */
for( limit = 9; limit <= MAX_JUMP; limit++ ){
printf("・・・手数 %d を探索中・・・\n", limit );
search_move( 1, 1, limit );
}
return 0;
}
戻る