「水差し問題」はいろいろな呼び方があって、「水をはかる問題」とか「水を測り出す問題」と呼ばれることもあります。
大きな容器に水が入っています。目盛の付いていない 8 リットルと 5 リットルの容器を使って、大きな容器から 4 リットルの水を汲み出してください。4 リットルの水は、どちらの容器に入れてもかまいません。水をはかる最短手順を求めてください。なお、水の総量に制限はありません。
Hoppers は「ペグ・ソリテア」と呼ばれるパズルのひとつです。出典は C magazine 2000 年 2 月号の「Ｃマガ電脳クラブ第 107 回 Hoppers」です。
ペグ・ソリテアは、盤上に配置されたペグ (駒) を、最後にはひとつ残るように取り除いていく古典的なパズルです。ペグは次のルールに従って移動し、除去することができます。
盤は今までに多数考案されていますが、33 穴英国盤、37 穴フランス盤、41 穴盤が有名でしょう。33 穴英国盤と Hoppers を図に示します。
●─●─●
│ │ │
●─●─● ●───●───●
│ │ │ │＼ ／│＼ ／│
●─●─●─●─●─●─● │ ● │ ● │
│ │ │ │ │ │ │ │／ ＼│／ ＼│
●─●─●─○─●─●─● ●───○───●
│ │ │ │ │ │ │ │＼ ／│＼ ／│
●─●─●─●─●─●─● │ ● │ ● │
│ │ │ │／ ＼│／ ＼│
●─●─● ●───●───●
│ │ │
●─●─● (2) Hoppers
(1) 33 穴英国盤
図：ペグ・ソリテア
それぞれのマスにペグがありますが、そこからひとつペグを取り除いてゲームを始めます。図では黒丸でペグを表し、白丸で空き場所を表しています。ルールに従ってペグを移動し、最後にひとつだけ残ればクリアとなります。ただし、ペグを取り除く位置によって、解けない場合もあるので注意してください。
それでは問題です。図 (2) に示したように、Hoppers の中央のペグを取り除きます。この状態から始めて、最後のペグが中央の位置に残る跳び方の最小手数を求めてください。
「マスターマインド」は 0 から 9 までの重複しない 4 つの数字からなる隠しコードを当てるゲームです。数字は合っているが位置が間違っている個数を cows で表し、数字も位置も合っている個数を bulls で表します。bulls が 4 になると正解です。
[6 2 8 1] : 正解
---------------------------------
1. [0 1 2 3] : cows 2 : bulls 0
2. [1 0 4 5] : cows 1 : bulls 0
3. [2 3 5 6] : cows 2 : bulls 0
4. [3 2 7 4] : cows 0 : bulls 1
5. [3 6 0 8] : cows 2 : bulls 0
6. [6 2 8 1] : cows 0 : bulls 4
図 : マスターマインドの動作例
マスターマインドを解くプログラムを作ってください。
水差し問題の場合、次に示す 3 通りの操作があります。
3 の操作は、容器が空になるまで水を移す場合と、もう一方の容器が満杯になるまで水を移す場合があります。容器は 2 つあるので、全部で 6 通りの操作があります。最初に、これらの操作を行う関数を定義します。プログラムは次のようになります。
リスト : 容器の操作
// 状態
typedef struct {
short a, b;
} State;
#define MAX_A 8
#define MAX_B 5
// A -> 0
State move1(State st)
{
return (State){0, st.b};
}
// A -> FULL
State move2(State st)
{
return (State){MAX_A, st.b};
}
// A -> B
State move3(State st)
{
int s = MAX_B - st.b;
if (st.a <= s) {
return (State){0, st.b + st.a};
} else {
return (State){st.a - s, st.b + s};
}
}
// B -> 0
State move4(State st)
{
return (State){st.a, 0};
}
// B -> FULL
State move5(State st)
{
return (State){st.a, MAX_B};
}
// B -> A
State move6(State st)
{
int s = MAX_A - st.a;
if (st.b <= s) {
return (State){st.a + st.b, 0};
} else {
return (State){st.a + s, st.b - s};
}
}
構造体 State で容器の状態 (局面) を表します。State のサイズが小さいので、今回は値渡しで行います。返り値も構造体で返します。MAX_A は 8 リットルの容器の最大値、MAX_B は 5 リットルの容器の最大値を表します。引数 st が容器に入っている水の量を表します。容器を水で満たす、または空にする操作は簡単ですね。他の容器へ移す場合、たとえば関数 move3 では、B の空き容量と A の水の量を比較して、少ない方が移す水の量になります。
これらの操作関数は配列 func に格納します。
リスト : 関数表
#define M 6
State (*func[M])(State) = {
move1, move2, move3, move4, move5, move6
};
次は操作手順の管理を考えましょう。最短手順を求めるだけならば、すべての手順を記憶しておく必要はありません。n 手目の操作で作られた局面が、n 手目以前の局面で出現しているのであれば、n 手より短い手数で到達する操作手順があるはずです。したがって、この n 手の手順を記憶しておく必要はないのです。
たとえば、容器を操作したら状態が st になりました。この st が新しく出現した局面ならば、これをキューに追加します。このとき、状態だけキューに格納すると、操作手順を表すことができないので、今回は状態を連結リストでつなぐことにします。次のリストを見てください。
リスト : 操作手順の管理
// リスト
typedef struct cell {
State st;
struct cell *prev;
} Cell;
// キュー
Cell buff[MAX_SIZE];
int rear, front;
構造体 Cell が連結リストのセルで、メンバ変数 st が状態を、prev が 1 手前の状態を格納するセルへのポインタです。キューの本体は配列 buff で、状態ではなくセル (Cell) を格納することにします。今回の水差し問題でとりうる状態は (8 + 1) * (5 + 1) = 54 通りしかありません。この値をマクロ MAX_SIZE で表します。キューの大きさは MAX_SIZE になります。
次はキューの操作関数を作ります。
リスト : キューの操作関数
// データの追加
void enq(State st, Cell *prev)
{
buff[rear].st = st;
buff[rear++].prev = prev;
}
// データの取り出し
Cell *deq(void)
{
return &buff[front++];
}
// キューは空か
bool is_empty(void)
{
return rear == front;
}
関数 enq は buff[rear] に引数の st と prev をセットします。関数 deq は buff[front] に格納されているセルを返します。関数 is_empty はキューが空であれば真を返します。
次は同一局面をチェックする関数 check_same_state を作ります。
リスト : 同一局面のチェック
bool check_same_state(State st)
{
for (int i = 0; i < rear; i++) {
Cell *cp = &buff[i];
if (st.a == cp->st.a && st.b == cp->st.b) return false;
}
return true;
}
新しく出現した状態はキューの本体に書き込まれています。したがって、buff を 0 から rear - 1 まで線形探索して、同じ状態があれば false を返します。同じ状態が見つからなければ true を返します。
手順を表示する関数 print_answer も簡単です。
リスト : 手順の表示
void print_answer(Cell *cp)
{
if (cp->prev != NULL) print_answer(cp->prev);
printf("(%d, %d)\n", cp->st.a, cp->st.b);
}
再帰呼び出しで最初の状態を格納しているセルまでたどります。あとは、再帰呼び出しから戻ってきたら、状態 st を printf で表示するだけです。
あとは幅優先探索で最短手順を求めるだけです。次のリストを見てください。
リスト : 水差し問題の解法
void solve(State st, int goal)
{
enq(st, NULL);
while (!is_empty()) {
Cell *cp = deq();
if (cp->st.a == goal || cp->st.b == goal) {
print_answer(cp);
return;
} else {
for (int i = 0; i < M; i++) {
State new_st = func[i](cp->st);
if (check_same_state(new_st)) {
enq(new_st, cp);
}
}
}
}
}
int main(void)
{
solve((State){0, 0}, 4);
return 0;
}
関数 solve の引数 goal は求める水の量です。最初に、enq で初期状態 st をキューに追加します。1 手前の状態はないので、引数には NULL を指定します。あとは、キューにデータがある間、while ループで探索を行います。
最初に、deq でキューからセルを取り出して変数 cp にセットします。cp の状態 st.a または st.b が goal と等しければゴールに到達しました。print_answer で手順を表示して、return で探索を終了します。
そうでなければ、移動関数に状態 cp->st を渡して新しい状態 new_st を作ります。new_st と同じ局面がないか check_same_state で確認し、新しく出現した状態ならば、enq でキューに追加します。このとき、1 手前の状態を格納しているセル cp を渡します。
これでプログラムは完成です。結果は次のようになりました。
$ clang water.c $ ./a.out (0, 0) (0, 5) (5, 0) (5, 5) (8, 2) (0, 2) (2, 0) (2, 5) (7, 0) (7, 5) (8, 4)
最短手順は 10 手になります。
//
// water.c : 水差し問題
//
// Copyright (C) 2015-2023 Makoto Hiroi
//
#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 54
// 状態
typedef struct {
short a, b;
} State;
// 操作関数
#define MAX_A 8
#define MAX_B 5
// A -> 0
State move1(State st)
{
return (State){0, st.b};
}
// A -> FULL
State move2(State st)
{
return (State){MAX_A, st.b};
}
// A -> B
State move3(State st)
{
int s = MAX_B - st.b;
if (st.a <= s) {
return (State){0, st.b + st.a};
} else {
return (State){st.a - s, st.b + s};
}
}
// B -> 0
State move4(State st)
{
return (State){st.a, 0};
}
// B -> FULL
State move5(State st)
{
return (State){st.a, MAX_B};
}
// B -> A
State move6(State st)
{
int s = MAX_A - st.a;
if (st.b <= s) {
return (State){st.a + st.b, 0};
} else {
return (State){st.a + s, st.b - s};
}
}
// 関数表
#define M 6
State (*func[M])(State) = {
move1, move2, move3, move4, move5, move6
};
// リスト
typedef struct cell {
State st;
struct cell *prev;
} Cell;
// キュー
Cell buff[MAX_SIZE];
int rear, front;
void enq(State st, Cell *prev)
{
buff[rear].st = st;
buff[rear++].prev = prev;
}
Cell *deq(void)
{
return &buff[front++];
}
bool is_empty(void)
{
return rear == front;
}
// 同一局面のチェック
bool check_same_state(State st)
{
for (int i = 0; i < rear; i++) {
Cell *cp = &buff[i];
if (st.a == cp->st.a && st.b == cp->st.b) return false;
}
return true;
}
// 手順の表示
void print_answer(Cell *cp)
{
if (cp->prev != NULL) print_answer(cp->prev);
printf("(%d, %d)\n", cp->st.a, cp->st.b);
}
// 幅優先探索
void solve(State st, int goal)
{
enq(st, NULL);
while (!is_empty()) {
Cell *cp = deq();
if (cp->st.a == goal || cp->st.b == goal) {
print_answer(cp);
return;
} else {
for (int i = 0; i < M; i++) {
State new_st = func[i](cp->st);
if (check_same_state(new_st)) {
enq(new_st, cp);
}
}
}
}
}
int main(void)
{
solve((State){0, 0}, 4);
return 0;
}
ペグ・ソリテアの場合、ペグの「跳び先表」を用意すると簡単にプログラムできます。座標は次のように定義します。
●───●───● ０───１───２
│＼ ／│＼ ／│ │＼ ／│＼ ／│
│ ● │ ● │ │ ３ │ ４ │
│／ ＼│／ ＼│ │／ ＼│／ ＼│
●───○───● ５───６───７
│＼ ／│＼ ／│ │＼ ／│＼ ／│
│ ● │ ● │ │ ８ │ ９ │
│／ ＼│／ ＼│ │／ ＼│／ ＼│
●───●───● 10───11───12
(1) Hoppers (2) 座標
図：Hoppers
リスト : 跳び先表
int jump_table[][10] = {
{1, 2, 3, 6, 5, 10, -1},
{3, 5, 6, 11, 4, 7, -1},
{1, 0, 4, 6, 7, 12, -1},
{6, 9, -1},
{6, 8, -1},
{3, 1, 6, 7, 8, 11, -1},
{3, 0, 4, 2, 8, 10, 9, 12, -1},
{4, 1, 6, 5, 9, 11, -1},
{6, 4, -1},
{6, 3, -1},
{5, 0, 8, 6, 11, 12, -1},
{8, 5, 6, 1, 9, 7, -1},
{11, 10, 9, 6, 7, 2, -1},
};
データは跳び越す位置と着地する位置の 2 個 1 セットで表しています。たとえば、10 のペグは 6 を跳び越して 2 に着地する、という跳び方があります。データの終端は -1 で表しています。
次に外部変数を定義します。
リスト : 外部変数の定義 #define SIZE 13 #define HOLE 6 #define MAX_JUMP 11 // 盤面 bool board[SIZE]; // 移動手順 int move[MAX_JUMP][2]; // 解の総数 int count;
盤面は bool 型の配列 board で表します。探索はこの配列を直接書き換え、バックトラックするときに元の値に戻します。移動手順は配列 move に格納します。ペグが 11 回移動すると盤上のペグはひとつになるので、MAX_JUMP は 11 となります。
次は単純な反復深化で最短手順を求めます。
リスト : Hoppers の解法
void dfs(int n, int jc, int limit)
{
if (jc > limit) return;
if (n == MAX_JUMP) {
if (board[HOLE]) print_move();
} else {
for (int from = 0; from < SIZE; from++) {
if (!board[from]) continue;
for (int i = 0; jump_table[from][i] != -1; i+= 2) {
int del = jump_table[from][i];
int to = jump_table[from][i + 1];
if (board[del] && !board[to]) {
// OK
move[n][0] = from;
move[n][1] = to;
board[from] = board[del] = false;
board[to] = true;
dfs(n + 1, move[n - 1][1] == from ? jc : jc + 1, limit);
board[to] = false;
board[from] = board[del] = true;
}
}
}
}
}
int main(void)
{
// 初手を 0 -> 6 に限定
for (int i = 0; i < SIZE; i++) board[i] = true;
board[0] = false;
board[3] = false;
move[0][0] = 0;
move[0][1] = HOLE;
for (int limit = 2; limit <= MAX_JUMP; limit++) {
printf("----- %d -----\n", limit);
dfs(1, 1, limit);
if (count > 0) break;
}
printf("%d\n", count);
return 0;
}
実際の処理は関数 dfs で行います。引数 n がペグの移動回数を表し、jc が跳んだ回数、limit が上限値を表します。jc が探索手数 limit より多くなったならば探索を打ち切ります。ここが重要なポイントですが、プログラム自体はいたって簡単ですね。n が MAX_JUMP に達したならば、盤上にはひとつのペグしか残っていません。それが中央の board[HOLE] にあるならば解の条件を満たします。関数 print_move で手順を表示します。
ペグが複数残っている場合は、探索を続行します。for 式の変数 from が跳び元の位置を表します。跳び先表から跳び越す位置を del に、着地する位置を to にセットします。from と del の位置にペグがあり、to の位置が空いているならば、ペグを移動することができます。
ペグの移動は簡単です。move[n][0] に from を、move[n][1] に to をセットします。そして、from, del の位置を false に、to の位置を true に書き換えて、dfs を再帰呼び出しします。このとき、前回移動したペグ move[n - 1][1] と同じペグならば、跳んだ回数 jc を +1 しないことに注意してください。再帰呼び出しから戻ってきたら、board を元の状態に戻します。
あとは関数 main で反復深化の上限値を増やしながら dfs を呼び出します。for ループの変数 limit が上限値を表します。最初の移動は、四隅にあるペグのひとつを中央に動かす手順しかありません。そこで、最初は 0 のペグを 6 へ動かすことに決めて、その状態から探索を開始します。count が 0 でなければ、解を見つけたので反復深化を終了します。
あとのプログラムは簡単なので説明は割愛します。詳細はプログラムリスト２をお読みください。
それでは実行してみましょう。
$ clang hoppers.c $ ./a.out ----- 2 ----- ----- 3 ----- ----- 4 ----- ----- 5 ----- ----- 6 ----- ----- 7 ----- ( 0, 6)( 9, 3)( 2, 0, 6)(11, 1)(10, 0, 2, 6)( 8, 4)(12, 2, 6) ( 0, 6)( 9, 3)( 2, 0, 6)(11, 1)(10, 6)( 4, 8)(12, 2, 0,10, 6) ( 0, 6)( 9, 3)( 2, 0, 6)(11, 1)(12, 2, 6)( 8, 4)(10, 0, 2, 6) ( 0, 6)( 9, 3)( 2, 6)( 8, 4)(10, 0, 2, 6)( 7, 5)(12,10, 0, 6) ( 0, 6)( 9, 3)( 2, 6)( 8, 4)(10, 0, 2, 6)(11, 1)(12, 2, 0, 6) ( 0, 6)( 9, 3)( 2, 6)( 8, 4)(10, 0, 6)( 7, 5)(12,10, 0, 2, 6) ( 0, 6)( 9, 3)( 2, 6)( 8, 4)(12, 2, 0, 6)( 5, 7)(10,12, 2, 6) ( 0, 6)( 9, 3)( 2, 6)( 8, 4)(12, 2, 0, 6)(11, 1)(10, 0, 2, 6) ( 0, 6)( 9, 3)( 2, 6)( 8, 4)(12, 2, 6)( 5, 7)(10,12, 2, 0, 6) ( 0, 6)( 9, 3)(10, 0, 6)( 7, 5)( 2, 0,10, 6)( 4, 8)(12,10, 6) ( 0, 6)( 9, 3)(10, 0, 6)( 7, 5)( 2, 6)( 8, 4)(12,10, 0, 2, 6) ( 0, 6)( 9, 3)(10, 0, 6)( 7, 5)(12,10, 6)( 4, 8)( 2, 0,10, 6) ( 0, 6)( 9, 3)(10, 6)( 4, 8)( 2, 0, 6)(11, 1)(12, 2, 0,10, 6) ( 0, 6)( 9, 3)(10, 6)( 4, 8)( 2, 0,10, 6)( 7, 5)(12,10, 0, 6) ( 0, 6)( 9, 3)(10, 6)( 4, 8)( 2, 0,10, 6)(11, 1)(12, 2, 0, 6) ( 0, 6)( 9, 3)(10, 6)( 4, 8)(12,10, 0, 6)( 1,11)( 2,12,10, 6) ( 0, 6)( 9, 3)(10, 6)( 4, 8)(12,10, 0, 6)( 7, 5)( 2, 0,10, 6) ( 0, 6)( 9, 3)(10, 6)( 4, 8)(12,10, 6)( 1,11)( 2,12,10, 0, 6) 18
7 手で解くことができました。解は全部で 18 通りになりました。最近のパソコンは高性能なので、穴の数が少ない盤面であれば、単純な反復深化でも高速に解くことができます。
/*
* hoppers.c : ペグ・ソリティア (13 穴盤)
*
* Copyright (C) 2015-2023 Makoto Hiroi
*/
#include <stdio.h>
#include <stdbool.h>
#define SIZE 13
#define HOLE 6
#define MAX_JUMP 11
// 跳び先表
int jump_table[][10] = {
{1, 2, 3, 6, 5, 10, -1},
{3, 5, 6, 11, 4, 7, -1},
{1, 0, 4, 6, 7, 12, -1},
{6, 9, -1},
{6, 8, -1},
{3, 1, 6, 7, 8, 11, -1},
{3, 0, 4, 2, 8, 10, 9, 12, -1},
{4, 1, 6, 5, 9, 11, -1},
{6, 4, -1},
{6, 3, -1},
{5, 0, 8, 6, 11, 12, -1},
{8, 5, 6, 1, 9, 7, -1},
{11, 10, 9, 6, 7, 2, -1},
};
// 盤面
bool board[SIZE];
// 移動手順
int move[MAX_JUMP][2];
// 解の総数
int count;
// 手順の表示
void print_move(void)
{
count++;
for (int i = 0, j = 1; i < MAX_JUMP; i++, j++) {
printf("(%2d,%2d", move[i][0], move[i][1]);
for (; j < MAX_JUMP; i++, j++) {
if (move[i][1] != move[j][0]) break;
printf(",%2d", move[j][1]);
}
printf(")");
}
printf("\n");
}
// 反復深化
void dfs(int n, int jc, int limit)
{
if (jc > limit) return;
if (n == MAX_JUMP) {
if (board[HOLE]) print_move();
} else {
for (int from = 0; from < SIZE; from++) {
if (!board[from]) continue;
for (int i = 0; jump_table[from][i] != -1; i+= 2) {
int del = jump_table[from][i];
int to = jump_table[from][i + 1];
if (board[del] && !board[to]) {
// OK
move[n][0] = from;
move[n][1] = to;
board[from] = board[del] = false;
board[to] = true;
dfs(n + 1, move[n - 1][1] == from ? jc : jc + 1, limit);
board[to] = false;
board[from] = board[del] = true;
}
}
}
}
}
int main(void)
{
// 初手を 0 -> 6 に限定
for (int i = 0; i < SIZE; i++) board[i] = true;
board[0] = false;
board[3] = false;
move[0][0] = 0;
move[0][1] = HOLE;
for (int limit = 2; limit <= MAX_JUMP; limit++) {
printf("----- %d -----\n", limit);
dfs(1, 1, limit);
if (count > 0) break;
}
printf("%d\n", count);
return 0;
}
このゲームは 10 個の数字の中から 4 個選ぶわけですから、全体では 10 * 9 * 8 * 7 = 5040 通りのコードしかありません。この中から正解を見つける方法ですが、質問したコードとその結果を覚えておいて、それと矛盾しないコードを作るようにします。具体的には、4 つの数字の順列を生成し、それが今まで質問したコードと矛盾しないことを確かめます。
矛盾しているかチェックする方法も簡単で、以前に質問したコードと比較して、bulls と cows が等しいときは矛盾していません。たとえば、次の例を考えてみてください。
[6 2 8 1] が正解の場合
[0 1 2 3] => bulls = 0, cows = 2
[0 1 2 3] と比較する
--------------------------------------------------------
[0 X X X] 0 から始まるコードは bulls = 1
になるので矛盾する。
・・・・
[1 0 3 4] cows = 3, bulls = 0 になるので矛盾する
・・・・
[1 0 4 5] cows = 2, bulls = 0 で矛盾しない。
--------------------------------------------------------
[1 0 4 5] => bulls = 0, cows = 1
次は、[0 1 2 3] と [1 0 4 5] に矛盾しない数字を選ぶ
図 : マスターマインドの推測アルゴリズム
[0 1 2 3] で bulls が 0 ですから、その位置にその数字は当てはまりません。したがって、[0 X X X] というコードは [0 1 2 3] と比較すると bulls が 1 となるので、矛盾していることがわかります。
次に [1 0 3 4] というコードを考えてみます。[0 1 2 3] の結果は cows が 2 ですから、その中で合っている数字は 2 つしかないわけです。ところが、[1 0 3 4] と [0 1 2 3] と比較すると cows が 3 になります。当たっている数字が 2 つしかないのに、同じ数字を 3 つ使うのでは矛盾していることになりますね。
次に [1 0 4 5] というコードと比較すると、bulls が 0 で cows が 2 となります。これは矛盾していないので、このコードを質問することにします。その結果が bulls = 0, cows = 1 となり、今度は [0 1 2 3] と [1 0 4 5] に矛盾しないコードを選択するのです。
それでは、プログラムを作りましょう。まず、質問したコードとその結果を格納するデータ型を定義します。
リスト : データ型の定義
// 質問したコードと結果
typedef struct {
int bulls, cows;
int code[CODE_SIZE];
} Query;
// 質問を格納するテーブル
#define M 16
Query query_table[M];
int query_count;
構造体 Query のメンバ変数 code に質問したコード、bulls とcows のその結果を格納します。Query は配列 query_table に格納します。
次は bulls を数える関数 count_bulls を作ります。
リスト : bulls を数える
int count_bulls(int *xs, int *ys)
{
int bulls = 0;
for (int i = 0; i < CODE_SIZE; i++) {
if (xs[i] == ys[i]) bulls++;
}
return bulls;
}
配列 xs, ys の要素を比較して、等しい場合は bulls をインクリメントします。最後に bulls を返します。
次は cows を数える処理を作ります。いきなり cows を数えようとすると難しいのですが、2 つのリストに共通の数字を数えることは簡単にできます。この方法では、bulls の個数を含んだ数を求めることになりますが、そこから bulls を引けば cows を求めることができます。関数名は count_same_number としましょう。プログラムは次のようになります。
リスト : 同じ数字の個数を数える
int count_same_number(int *xs, int *ys)
{
int c = 0;
for (int i = 0; i < CODE_SIZE; i++) {
for (int j = 0; j < CODE_SIZE; j++) {
if (xs[i] == ys[j]) c++;
}
}
return c;
}
最初の for ループで xs から要素を順番に取り出します。次の for ループで、xs[i] と ys の要素を比較して、等しい場合は変数 c をインクリメントします。最後に c を返します。
次は、今まで質問したコードと矛盾していないか調べる関数 check_query を作ります。
リスト : 今まで質問したコードと矛盾していないか
bool check_query(int *q)
{
for (int i = 0; i < query_count; i++) {
Query *p = &query_table[i];
int b = count_bulls(q, p->code);
int c = count_same_number(q, p->code) - b;
if (b != p->bulls || c != p->cows)
return false;
}
return true;
}
引数 q がこれから質問しようとするコードです。すべてのデータで矛盾がなければ true を返します。関数 count_bulls と count_same_number を使って bulls (変数 b) と cows (変数 c) を求めて、質問したときの bulls と cows と比較します。矛盾している場合は false を返します。
次はマスターマインドを解く関数 solver を作ります。
リスト : マスターマインドの解法
void solve(int *answer)
{
for (int i = 0; i < perm_count; i++) {
if (!check_query(perm_table[i])) continue;
Query *q = &query_table[query_count++];
q->bulls = count_bulls(answer, perm_table[i]);
q->cows = count_same_number(answer, perm_table[i]) - q->bulls;
for (int j = 0; j < CODE_SIZE; j++)
q->code[j] = perm_table[i][j];
// 表示
print_query(q);
if (q->bulls == CODE_SIZE) {
printf("おめでとう！\n");
return;
}
}
}
引数 answer が正解のコードです。質問するコードはあらかじめ作成しておいて配列 perm_table にセットしておきます。for ループでコードを順番に取り出し、check_query で矛盾していなかチェックします。矛盾していなければ、bulls と cows を求めて、その結果を query_table に追加し、関数 print_query で結果を表示します。もし、bulls が 4 であれば、答えを求めることができました。return で処理を終了します。
最後に main 関数を作ります。
リスト : main 関数
int main(void)
{
int answer[] = {9, 4, 3, 1};
int buff[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
make_perm(0, 4, buff, 10);
solve(answer);
return 0;
}
関数 make_perm で順列を生成して配列 perm_table にセットします。(9, 4, 3, 1) を解く場合は、それを solver に渡して呼び出すだけです。
これでプログラムは完成です。それでは実行例を示しましょう。
$ clang mastermind.c $ ./a.out 1, [ 0 1 2 3 ], bulls = 0, cows = 2 2, [ 1 0 4 5 ], bulls = 0, cows = 2 3, [ 2 3 5 4 ], bulls = 0, cows = 2 4, [ 3 4 0 6 ], bulls = 1, cows = 1 5, [ 3 5 6 1 ], bulls = 1, cows = 1 6, [ 6 5 0 2 ], bulls = 0, cows = 0 7, [ 7 4 3 1 ], bulls = 3, cows = 0 8, [ 8 4 3 1 ], bulls = 3, cows = 0 9, [ 9 4 3 1 ], bulls = 4, cows = 0 おめでとう！
(9, 4, 3, 1) は 9 回で当てることができました。ちなみに、5040 通りのコードすべて試してみることもできます。実際にプログラムを修正して試してみると、平均質問回数は 5.56 回になりました。これは参考文献『数当てゲーム (MOO, マスターマインド)』の結果と同じです。質問回数の最大値は 9 回で、そのときのコードは (9, 4, 3, 1), (9, 2, 4, 1), (5, 2, 9, 3), (9, 2, 0, 4), (9, 2, 4, 1) でした。
なお、参考文献には平均質問回数がこれよりも少なくなる方法が紹介されています。単純な数当てゲームだと思っていましたが、その奥はけっこう深いようです。興味のある方はいろいろ試してみてください。
[1] 田中哲郎 『数当てゲーム (MOO, マスターマインド)』, 松原仁、竹内郁雄 編 『bit 別冊 ゲームプログラミング』 pp150 - 157, 共立出版, 1997
/*
* mastermind.c : マスターマインドの解法
*
* Copyright (C) 2015-2023 Makoto Hiroi
*/
#include <stdio.h>
#include <stdbool.h>
#define CODE_SIZE 4
#define PERM_SIZE 5040
// 順列のテーブル
int perm_table[PERM_SIZE][CODE_SIZE];
int perm_count;
// 質問したコードと結果
typedef struct {
int bulls, cows;
int code[CODE_SIZE];
} Query;
// 質問を格納するテーブル
#define M 16
Query query_table[M];
int query_count;
// Bulls を数える
int count_bulls(int *xs, int *ys)
{
int bulls = 0;
for (int i = 0; i < CODE_SIZE; i++) {
if (xs[i] == ys[i]) bulls++;
}
return bulls;
}
// 同じ数字を数える
int count_same_number(int *xs, int *ys)
{
int c = 0;
for (int i = 0; i < CODE_SIZE; i++) {
for (int j = 0; j < CODE_SIZE; j++) {
if (xs[i] == ys[j]) c++;
}
}
return c;
}
// 順列の生成
void make_perm(int i, int k, int *buff, int n)
{
if (i == k) {
for (int j = 0; j < k; j++)
perm_table[perm_count][j] = buff[j];
perm_count++;
} else {
make_perm(i + 1, k, buff, n);
int temp = buff[i];
for (int j = i + 1; j < n; j++) {
buff[i] = buff[j];
buff[j] = temp;
make_perm(i + 1, k, buff, n);
buff[j] = buff[i];
buff[i] = temp;
}
}
}
// チェック
bool check_query(int *q)
{
for (int i = 0; i < query_count; i++) {
Query *p = &query_table[i];
int b = count_bulls(q, p->code);
int c = count_same_number(q, p->code) - b;
if (b != p->bulls || c != p->cows)
return false;
}
return true;
}
// 質問の表示
void print_query(Query *q)
{
printf("%d, [ ", query_count);
for (int i = 0; i < CODE_SIZE; i++)
printf("%d ", q->code[i]);
printf("], bulls = %d, cows = %d\n", q->bulls, q->cows);
}
void solve(int *answer)
{
for (int i = 0; i < perm_count; i++) {
if (!check_query(perm_table[i])) continue;
Query *q = &query_table[query_count++];
q->bulls = count_bulls(answer, perm_table[i]);
q->cows = count_same_number(answer, perm_table[i]) - q->bulls;
for (int j = 0; j < CODE_SIZE; j++)
q->code[j] = perm_table[i][j];
// 表示
print_query(q);
if (q->bulls == CODE_SIZE) {
printf("おめでとう！\n");
return;
}
}
}
int main(void)
{
int answer[] = {9, 4, 3, 1};
int buff[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
make_perm(0, 4, buff, 10);
solve(answer);
return 0;
}