●プログラムリスト１
/*
* mms.c : Master Mind Square (Level 1) の解法
*
* 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 9
#define PS 6
#define LNUM 6
#define MAX_Q 20
/* 問い合わせの結果を格納 */
typedef struct {
char oldcode[SIZE];
int bulls[LNUM];
int cows[LNUM];
} Query;
Query query_table[MAX_Q];
int query_count;
/* 駒の数 */
char piece[PS];
char piece_data[PS] = {
2, 2, 2, 2, 2, 2,
};
/* 盤面 */
char board[SIZE];
/* 問題 */
char collect[SIZE];
/*
* 盤面
* ０１２
* ３４５
* ６７８
*/
/* 直線の定義 */
const char line[LNUM][4] = {
0, 1, 2, -1,
3, 4, 5, -1,
6, 7, 8, -1,
0, 3, 6, -1,
1, 4, 7, -1,
2, 5, 8, -1,
};
/* collect の作成 */
void make_collect( void )
{
int count = 0;
char work[PS];
memcpy( work, piece_data, PS );
while( count < SIZE ){
int p = rand() % PS;
if( work[p] ){
collect[count++] = p;
work[p]--;
}
}
}
/* bulls を求める */
int count_bulls( int n, char *c1, char *c2 )
{
const char *p;
int bulls = 0;
for( p = line[n]; *p != -1; p++ ){
if( c1[*p] == c2[*p] ) bulls++;
}
return bulls;
}
/* 同じ数字を求める */
int count_same_number( int n, char *c1, char *c2 )
{
const char *p1, *p2;
char flag[SIZE];
int c = 0;
memset( flag, 0, SIZE );
for( p1 = line[n]; *p1 != -1; p1++ ){
for( p2 = line[n]; *p2 != -1; p2++ ){
if( c1[*p1] == c2[*p2] && !flag[*p2] ){
c++;
flag[*p2] = 1;
break;
}
}
}
return c;
}
/* 今までの問い合わせと矛盾しないかチェックする */
int check_query( int n, char *q )
{
int i;
for( i = 0; i < query_count; i++ ){
char *code = query_table[i].oldcode;
int bulls = count_bulls( n, q, code );
int cows = count_same_number( n, q, code ) - bulls;
if( bulls != query_table[i].bulls[n] || cows != query_table[i].cows[n] ){
return FALSE;
}
}
return TRUE;
}
/* コードの出力 */
void print_code( char *code )
{
int i, j;
for( i = 0; i < 3; i++ ){
for( j = 0; j < 3; j++ ){
printf("%d ", *code++ );
}
printf("\n");
}
printf("\n");
}
/* 問い合わせ */
int ask( char *code )
{
int i;
Query *q = &query_table[query_count++];
if( query_count >= MAX_Q ){
fprintf(stderr, "Query Table Overflow\n" ); exit( 1 );
}
printf("***** %d 回 *****\n", query_count );
print_code( code );
if( !memcmp( code, collect, SIZE ) ) return TRUE; /* 正解！ */
/* データセット */
memcpy( q->oldcode, code, SIZE );
for( i = 0; i < LNUM; i++ ){
q->bulls[i] = count_bulls( i, code, collect );
q->cows[i] = count_same_number( i, code, collect ) - q->bulls[i];
printf("%d: bulls = %d, cows = %d\n", i, q->bulls[i], q->cows[i] );
}
printf("\n");
return FALSE;
}
/* チェックライン */
char check_line_table[SIZE + 1] = {
-1, /* DUMMY */
-1, -1, 0,
-1, -1, 1,
3, 4, 2,
};
/* Master Mind Square を解く */
int solve( int n )
{
if( check_line_table[n] >= 0 && !check_query( check_line_table[n], board ) )
return FALSE;
if( n == SIZE ){
if( check_query( 5, board ) ){ /* 最後のチェック */
if( ask( board ) ){
printf("おめでとう！正解です！！\n");
return TRUE;
}
}
} else {
int i;
for( i = 0; i < PS; i++ ){
if( piece[i] ){
board[n] = i;
piece[i]--;
if( solve( n + 1 ) ) return TRUE;
piece[i]++;
}
}
}
return FALSE;
}
int main()
{
int i, count = 0, max = 0, min = MAX_Q;
srand( time( NULL ) );
for( i = 0; i < 100; i++ ){
make_collect();
printf("***** 正解 *****\n");
print_code( collect );
printf("****************\n");
query_count = 0;
memcpy( piece, piece_data, PS );
solve( 0 );
count += query_count;
if( max < query_count ) max = query_count;
if( min > query_count ) min = query_count;
}
fprintf(stderr, "最小 %d 回、最大 %d 回、平均 %g 回\n", min, max, (double)count/(double)i);
return 0;
}
●プログラムリスト２
/*
* mms2.c : Master Mind Square (Level 2) の解法
*
* 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 12
#define PS 6
#define LNUM 7
#define MAX_Q 20
/* 問い合わせの結果を格納 */
typedef struct {
char oldcode[SIZE];
int bulls[LNUM];
int cows[LNUM];
} Query;
Query query_table[MAX_Q];
int query_count;
/* 駒の数 */
char piece[PS];
char piece_data[PS] = {
3, 3, 3, 2, 2, 2,
};
/* 盤面 */
char board[SIZE];
/* 問題 */
char collect[SIZE];
/*
* 盤面
* ０ ３ ６ ９
* １ ４ ７ 10
* ２ ５ ８ 11
*/
/* 直線の定義 */
const char line[LNUM][5] = {
0, 1, 2, -1, -1,
3, 4, 5, -1, -1,
6, 7, 8, -1, -1,
9, 10, 11, -1, -1,
0, 3, 6, 9, -1,
1, 4, 7, 10, -1,
2, 5, 8, 11, -1,
};
/* collect の作成 */
void make_collect( void )
{
int count = 0;
char work[PS];
memcpy( work, piece_data, PS );
while( count < SIZE ){
int p = rand() % PS;
if( work[p] ){
collect[count++] = p;
work[p]--;
}
}
}
/* bulls を求める */
int count_bulls( int n, char *c1, char *c2 )
{
const char *p;
int bulls = 0;
for( p = line[n]; *p != -1; p++ ){
if( c1[*p] == c2[*p] ) bulls++;
}
return bulls;
}
/* 同じ数字を求める */
int count_same_number( int n, char *c1, char *c2 )
{
const char *p1, *p2;
char flag[SIZE];
int c = 0;
memset( flag, 0, SIZE );
for( p1 = line[n]; *p1 != -1; p1++ ){
for( p2 = line[n]; *p2 != -1; p2++ ){
if( c1[*p1] == c2[*p2] && !flag[*p2] ){
c++;
flag[*p2] = 1;
break;
}
}
}
return c;
}
/* 今までの問い合わせと矛盾しないかチェックする */
int check_query( int n, char *q )
{
int i;
for( i = 0; i < query_count; i++ ){
char *code = query_table[i].oldcode;
int bulls = count_bulls( n, q, code );
int cows = count_same_number( n, q, code ) - bulls;
if( bulls != query_table[i].bulls[n] || cows != query_table[i].cows[n] ){
return FALSE;
}
}
return TRUE;
}
/* コードの出力 */
void print_code( char *code )
{
int i, j;
for( i = 0; i < 4; i++ ){
for( j = 0; j < 3; j++ ){
printf("%d ", *code++ );
}
printf("\n");
}
printf("\n");
}
/* 問い合わせ */
int ask( char *code )
{
int i;
Query *q = &query_table[query_count++];
if( query_count >= MAX_Q ){
fprintf(stderr, "Query Table Overflow\n" ); exit( 1 );
}
printf("***** %d 回 *****\n", query_count );
print_code( code );
if( !memcmp( code, collect, SIZE ) ) return TRUE; /* 正解！ */
/* データセット */
memcpy( q->oldcode, code, SIZE );
for( i = 0; i < LNUM; i++ ){
q->bulls[i] = count_bulls( i, code, collect );
q->cows[i] = count_same_number( i, code, collect ) - q->bulls[i];
printf("%d: bulls = %d, cows = %d\n", i, q->bulls[i], q->cows[i] );
}
printf("\n");
return FALSE;
}
/* チェックライン */
char check_line_table[SIZE + 1] = {
-1, /* DUMMY */
-1, -1, 0,
-1, -1, 1,
-1, -1, 2,
4, 5, 3,
};
/* Master Mind Square を解く */
int solve( int n )
{
if( check_line_table[n] >= 0 && !check_query( check_line_table[n], board ) )
return FALSE;
if( n == SIZE ){
if( check_query( 6, board ) ){ /* 最後のチェック */
if( ask( board ) ){
printf("おめでとう！正解です！！\n");
return TRUE;
}
}
} else {
int i;
for( i = 0; i < PS; i++ ){
if( piece[i] ){
board[n] = i;
piece[i]--;
if( solve( n + 1 ) ) return TRUE;
piece[i]++;
}
}
}
return FALSE;
}
int main()
{
int i, count = 0, max = 0, min = MAX_Q;
srand( time( NULL ) );
for( i = 0; i < 100; i++ ){
make_collect();
printf("***** 正解 *****\n");
print_code( collect );
printf("****************\n");
query_count = 0;
memcpy( piece, piece_data, PS );
solve( 0 );
count += query_count;
if( max < query_count ) max = query_count;
if( min > query_count ) min = query_count;
}
fprintf(stderr, "最小 %d 回、最大 %d 回、平均 %g 回\n", min, max, (double)count/(double)i);
return 0;
}
●プログラムリスト３
/*
* mms3.c : Master Mind Square (Level 3) の解法
*
* 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 16
#define PS 6
#define LNUM 8
#define MAX_Q 20
/* 問い合わせの結果を格納 */
typedef struct {
char oldcode[SIZE];
int bulls[LNUM];
int cows[LNUM];
} Query;
Query query_table[MAX_Q];
int query_count;
/* 駒の数 */
char piece[PS];
/* 盤面 */
char board[SIZE];
/* 問題 */
char collect[SIZE];
/*
* 盤面
* ０ １ ２ ３
* ４ ５ ６ ７
* ８ ９ 10 11
* 12 13 14 15
*/
/* 直線の定義 */
const char line[LNUM][5] = {
0, 1, 2, 3, -1,
4, 5, 6, 7, -1,
8, 9, 10, 11, -1,
12, 13, 14, 15, -1,
0, 4, 8, 12, -1,
1, 5, 9, 13, -1,
2, 6, 10, 14, -1,
3, 7, 11, 15, -1,
};
/* collect の作成 */
void make_collect( void )
{
int count = 0;
char work[PS];
memset( work, 3, PS );
while( count < SIZE ){
int p = rand() % PS;
if( work[p] ){
collect[count++] = p;
work[p]--;
}
}
}
/* bulls を求める */
int count_bulls( int n, char *c1, char *c2 )
{
const char *p;
int bulls = 0;
for( p = line[n]; *p != -1; p++ ){
if( c1[*p] == c2[*p] ) bulls++;
}
return bulls;
}
/* 同じ数字を求める */
int count_same_number( int n, char *c1, char *c2 )
{
const char *p1, *p2;
char flag[SIZE];
int c = 0;
memset( flag, 0, SIZE );
for( p1 = line[n]; *p1 != -1; p1++ ){
for( p2 = line[n]; *p2 != -1; p2++ ){
if( c1[*p1] == c2[*p2] && !flag[*p2] ){
c++;
flag[*p2] = 1;
break;
}
}
}
return c;
}
/* 今までの問い合わせと矛盾しないかチェックする */
int check_query( int n, char *q )
{
int i;
for( i = 0; i < query_count; i++ ){
char *code = query_table[i].oldcode;
int bulls = count_bulls( n, q, code );
int cows = count_same_number( n, q, code ) - bulls;
if( bulls != query_table[i].bulls[n] || cows != query_table[i].cows[n] ){
return FALSE;
}
}
return TRUE;
}
/* コードの出力 */
void print_code( char *code )
{
int i, j;
for( i = 0; i < 4; i++ ){
for( j = 0; j < 4; j++ ){
printf("%d ", *code++ );
}
printf("\n");
}
printf("\n");
}
/* 問い合わせ */
int ask( char *code )
{
int i;
Query *q = &query_table[query_count++];
if( query_count >= MAX_Q ){
fprintf(stderr, "Query Table Overflow\n" ); exit( 1 );
}
printf("***** %d 回 *****\n", query_count );
print_code( code );
if( !memcmp( code, collect, SIZE ) ) return TRUE; /* 正解！ */
/* データセット */
memcpy( q->oldcode, code, SIZE );
for( i = 0; i < LNUM; i++ ){
q->bulls[i] = count_bulls( i, code, collect );
q->cows[i] = count_same_number( i, code, collect ) - q->bulls[i];
printf("%d: bulls = %d, cows = %d\n", i, q->bulls[i], q->cows[i] );
}
printf("\n");
return FALSE;
}
/* チェックライン */
char check_line_table[SIZE + 1] = {
-1, /* DUMMY */
-1, -1, -1, 0,
-1, -1, -1, 1,
-1, -1, -1, 2,
4, 5, 6, 3,
};
/* マスターマインドを解く */
int solve( int n )
{
if( check_line_table[n] >= 0 && !check_query( check_line_table[n], board ) )
return FALSE;
if( n == SIZE ){
if( check_query( 7, board ) ){ /* 最後のチェック */
if( ask( board ) ){
printf("おめでとう！正解です！！\n");
return TRUE;
}
}
} else {
int i;
for( i = 0; i < PS; i++ ){
if( piece[i] ){
board[n] = i;
piece[i]--;
if( solve( n + 1 ) ) return TRUE;
piece[i]++;
}
}
}
return FALSE;
}
int main()
{
int i, count = 0, max = 0, min =MAX_Q;
srand( time( NULL ) );
for( i = 0; i < 50; i++ ){
make_collect();
printf("***** 正解 *****\n");
print_code( collect );
printf("****************\n");
query_count = 0;
memset( piece, 3, PS );
solve( 0 );
count += query_count;
if( max < query_count ) max = query_count;
if( min > query_count ) min = query_count;
}
fprintf(stderr, "最小 %d 回、最大 %d 回、平均 %g 回\n", min, max, (double)count/(double)i);
return 0;
}