Yet Another C++ Problems (5)
●問題41
「水差し問題」はいろいろな呼び方があって、「水をはかる問題」とか「水を測り出す問題」と呼ばれることもあります。
大きな容器に水が入っています。目盛の付いていない 8 リットルと 5 リットルの容器を使って、大きな容器から 4 リットルの水を汲み出してください。4 リットルの水は、どちらの容器に入れてもかまいません。水をはかる最短手順を求めてください。なお、水の総量に制限はありません。
●問題42
Hoppers は「ペグ・ソリテア」と呼ばれるパズルのひとつです。ペグ・ソリテアは、盤上に配置されたペグ (駒) を、最後にはひとつ残るように取り除いていく古典的なパズルです。ペグは次のルールに従って移動し、除去することができます。
- ペグは隣にあるペグをひとつだけ跳び越して、空いている場所へ着地します。
- 跳び越されたペグは盤上から取り除かれます。
- 移動方向は、ふつう縦横のみの 4 方向ですが、 ルールによっては斜め方向の移動を許す場合もあります。
- 同じペグの連続跳び越しは 1 手と数えます。
盤は今までに多数考案されていますが、33 穴英国盤、37 穴フランス盤、41 穴盤が有名でしょう。33 穴英国盤と Hoppers を図に示します。
(1) 33 穴英国盤
(2) Hoppers 図 : ペグ・ソリテア
それぞれのマスにペグがありますが、そこからひとつペグを取り除いてゲームを始めます。図では黒丸でペグを表し、白丸で空き場所を表しています。ルールに従ってペグを移動し、最後にひとつだけ残ればクリアとなります。ただし、ペグを取り除く位置によって、解けない場合もあるので注意してください。
それでは問題です。図 (2) に示したように、Hoppers の中央のペグを取り除きます。この状態から始めて、最後のペグが中央の位置に残る跳び方の最小手数を求めてください。
- 出典 : 「Ｃマガ電脳クラブ第 107 回 Hoppers」, C magazine 2000 年 2 月号
●問題43
「マスターマインド」は 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
図 : マスターマインドの動作例
マスターマインドを解くプログラムを作ってください。
●解答41
●容器の操作
水差し問題の場合、次に示す 3 通りの操作があります。
- 容器いっぱいに水を満たす。
- 容器を空にする。
- 他の容器に水を移す。
3 の操作は、容器が空になるまで水を移す場合と、もう一方の容器が満杯になるまで水を移す場合があります。容器は 2 つあるので、全部で 6 通りの操作があります。最初に、これらの操作を行う関数を定義します。プログラムは次のようになります。
リスト : 容器の操作
// 状態
typedef pair<int,int> State;
// 容器の大きさ
const int MAX_A = 8;
const int MAX_B = 5;
// 移動関数
// A -> 0
State move1(const State& st)
{
return State(0, st.second);
}
// A -> FULL
State move2(const State& st)
{
return State(MAX_A, st.second);
}
// A -> B
State move3(const State& st)
{
int s = MAX_B - st.second;
if (st.first <= s) {
return State(0, st.second + st.first);
} else {
return State(st.first - s, st.second + s);
}
}
// B -> 0
State move4(const State& st)
{
return State(st.first, 0);
}
// B -> FULL
State move5(const State& st)
{
return State(st.first, MAX_B);
}
// B -> A
State move6(const State& st)
{
int s = MAX_A - st.first;
if (st.second <= s) {
return State(st.first + st.second, 0);
} else {
return State(st.first + s, st.second - s);
}
}
typedef で構造体 pair<int,int> に別名 State を付けて、容器の状態 (局面) を表します。関数の引数 st は参照型とし、返り値は構造体で返します。MAX_A は 8 リットルの容器の最大値、MAX_B は 5 リットルの容器の最大値を表します。容器を水で満たす、または空にする操作は簡単ですね。他の容器へ移す場合、たとえば関数 move3 では、B の空き容量と A の水の量を比較して、少ない方が移す水の量になります。
これらの操作関数は配列 func に格納します。
リスト : 移動関数表
State (*func[6])(const State&) = {
move1, move2, move3, move4, move5, move6
};
●操作手順の管理
次は操作手順の管理を考えましょう。最短手順を求めるだけならば、すべての手順を記憶しておく必要はありません。n 手目の操作で作られた局面が、n 手目以前の局面で出現しているのであれば、n 手より短い手数で到達する操作手順があるはずです。したがって、この n 手の手順を記憶しておく必要はないのです。
たとえば、容器を操作したら状態が st になりました。この st が新しく出現した局面ならば、これをキューに追加します。このとき、状態だけキューに格納すると、操作手順を表すことができないので、vector に State を格納して移動手順を表すことにします。typedef で別名 Moves を定義しておきます。
リスト : 移動手順のデータ型 typedef vector<State> Moves;
次は同一局面をチェックする処理を作ります。
リスト : 同一局面のチェック
bool visited[MAX_A + 1][MAX_B + 1];
bool is_visited(const State& st)
{
return visited[st.first][st.second];
}
void set_visited(const State& st)
{
visited[st.first][st.second] = true;
}
状態は最大で (MAX_A + 1) * (MAX_B + 1) = 54 通りしかありません。2 次元配列 visited を用意して、出現した状態には true をセットすることにします。この処理を関数 set_visited で行います。関数 is_visited は配列 visited の要素を返すだけです。
●幅優先探索のプログラム
あとは幅優先探索で最短手順を求めるだけです。次のリストを見てください。
リスト : 水差し問題の解法
// 新しい手順の生成
Moves make_new_moves(const Moves& moves, const State& x)
{
Moves new_moves = moves;
new_moves.push_back(x);
return new_moves;
}
// 幅優先探索
void solver(const State& start, int goal)
{
queue<Moves> q;
q.push(Moves{start});
set_visited(start);
while (!q.empty()) {
Moves moves = move(q.front());
q.pop();
if (check_goal(moves.back(), goal)) {
print_moves(moves);
return;
}
for (auto f : func) {
State x = f(moves.back());
if (!is_visited(x)) {
q.push(make_new_moves(moves, x));
set_visited(x);
}
}
}
}
基本的な処理は拙作のページ 経路の探索 で説明した幅優先探索と同じです。最初に、手順 Moves を格納するキューを変数 q にセットし、start を格納した手順をキューにセットします。キューにデータを追加するときは、set_visited で配列 visited に true をセットすることをお忘れなく。あとは、キューにデータがある間、探索処理を繰り返します。
while ループの中で、最初にキューから手順をひとつ取り出して変数 moves にセットします。手順の最後尾の状態がゴールの条件を満たしているか、関数 check_goal で確かめます。そうであれば、print_moves で手順を表示して探索処理を終了します。
そうでなければ、移動関数表 func の関数を末尾の状態に適用して状態 x を作ります。次に、状態 x を is_visited でチェックして、新しい状態であれば関数 make_new_moves で新しい移動手順を生成して、それをキューに追加します。
あとは特に難しいところはないでしょう。説明は割愛しますので、詳細は プログラムリスト１ をお読みください。
●実行結果
これでプログラムは完成です。結果は次のようになりました。
$ clang++ water.cpp $ ./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.cpp : 水差し問題
//
// Copyright (C) 2015-2023 Makoto Hiroi
//
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 状態
typedef pair<int,int> State;
// 手順
typedef vector<State> Moves;
// 容器の大きさ
const int MAX_A = 8;
const int MAX_B = 5;
// 同一局面のチェック
bool visited[MAX_A + 1][MAX_B + 1];
bool is_visited(const State& st)
{
return visited[st.first][st.second];
}
void set_visited(const State& st)
{
visited[st.first][st.second] = true;
}
//
// 移動関数
//
// A -> 0
State move1(const State& st)
{
return State(0, st.second);
}
// A -> FULL
State move2(const State& st)
{
return State(MAX_A, st.second);
}
// A -> B
State move3(const State& st)
{
int s = MAX_B - st.second;
if (st.first <= s) {
return State(0, st.second + st.first);
} else {
return State(st.first - s, st.second + s);
}
}
// B -> 0
State move4(const State& st)
{
return State(st.first, 0);
}
// B -> FULL
State move5(const State& st)
{
return State(st.first, MAX_B);
}
// B -> A
State move6(const State& st)
{
int s = MAX_A - st.first;
if (st.second <= s) {
return State(st.first + st.second, 0);
} else {
return State(st.first + s, st.second - s);
}
}
// 移動関数表
State (*func[6])(const State&) = {
move1, move2, move3, move4, move5, move6
};
// 新しい手順の生成
Moves make_new_moves(const Moves& moves, const State& x)
{
Moves new_moves = moves;
new_moves.push_back(x);
return new_moves;
}
// ゴールのチェック
bool check_goal(const State& st, int goal)
{
return st.first == goal || st.second == goal;
}
// 手順の表示
void print_moves(const Moves& moves)
{
for (auto& x : moves)
cout << "(" << x.first << "," << x.second << ")";
cout << endl;
}
// 幅優先探索
void solver(const State& start, int goal)
{
queue<Moves> q;
q.push(Moves{start});
set_visited(start);
while (!q.empty()) {
Moves moves = move(q.front());
q.pop();
if (check_goal(moves.back(), goal)) {
print_moves(moves);
return;
}
for (auto f : func) {
State x = f(moves.back());
if (!is_visited(x)) {
q.push(make_new_moves(moves, x));
set_visited(x);
}
}
}
}
int main(void)
{
solver(State{0, 0}, 4);
}
●解答42
ペグ・ソリテアの場合、ペグの「跳び先表」を用意すると簡単にプログラムできます。座標は次のように定義します。
図 : Hoppers
リスト : 跳び先表
vector<vector<pair<int,int>>> jump_table = {
{{1, 2}, {3, 6}, {5, 10}},
{{3, 5}, {6, 11}, {4, 7}},
{{1, 0}, {4, 6}, {7, 12}},
{{6, 9}},
{{6, 8}},
{{3, 1}, {6, 7}, {8, 11}},
{{3, 0}, {4, 2}, {8, 10}, {9, 12}},
{{4, 1}, {6, 5}, {9, 11}},
{{6, 4}},
{{6, 3}},
{{5, 0}, {8, 6}, {11, 12}},
{{8, 5}, {6, 1}, {9, 7}},
{{11, 10}, {9, 6}, {7, 2}}
};
データは跳び越す位置と着地する位置を pair<int,int> に格納して表しています。
次に大域変数を定義します。
リスト : 大域変数の定義 const int SIZE = 13; const int HOLE = 6; const int MAX_JUMP = 11; // 盤面 bool board[SIZE]; // 移動手順 int moves[MAX_JUMP][2]; // 解の総数 int count;
盤面は bool 型の配列 board で表します。探索はこの配列を直接書き換え、バックトラックするときに元の値に戻します。移動手順は配列 moves に格納します。ペグが 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 (auto& p : jump_table[from]) {
int del = p.first;
int to = p.second;
if (board[del] && !board[to]) {
// OK
moves[n][0] = from;
moves[n][1] = to;
board[from] = board[del] = false;
board[to] = true;
dfs(n + 1, moves[n - 1][1] == from ? jc : jc + 1, limit);
board[to] = false;
board[from] = board[del] = true;
}
}
}
}
}
int main()
{
// 初手を 0 -> 6 に限定
for (int i = 0; i < SIZE; i++) board[i] = true;
board[0] = false;
board[3] = false;
moves[0][0] = 0;
moves[0][1] = HOLE;
for (int limit = 2; limit <= MAX_JUMP; limit++) {
cout << "-----" << limit << "-----\n";
dfs(1, 1, limit);
if (count > 0) break;
}
cout << count << endl;
}
実際の処理は関数 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.cpp $ ./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.cpp : ペグソリティア (Hoppers)
//
// Copyright (C) 2015-2023 Makoto Hiroi
//
#include <iostream>
#include <vector>
using namespace std;
const int SIZE = 13;
const int HOLE = 6;
const int MAX_JUMP = 11;
// 跳び先表
vector<vector<pair<int,int>>> jump_table = {
{{1, 2}, {3, 6}, {5, 10}},
{{3, 5}, {6, 11}, {4, 7}},
{{1, 0}, {4, 6}, {7, 12}},
{{6, 9}},
{{6, 8}},
{{3, 1}, {6, 7}, {8, 11}},
{{3, 0}, {4, 2}, {8, 10}, {9, 12}},
{{4, 1}, {6, 5}, {9, 11}},
{{6, 4}},
{{6, 3}},
{{5, 0}, {8, 6}, {11, 12}},
{{8, 5}, {6, 1}, {9, 7}},
{{11, 10}, {9, 6}, {7, 2}}
};
// 盤面
bool board[SIZE];
// 移動手順
int moves[MAX_JUMP][2];
// 解の総数
int count;
// 手順の表示
void print_move(void)
{
count++;
for (int i = 0, j = 1; i < MAX_JUMP; i++, j++) {
cout << "(" << moves[i][0] << "," << moves[i][1];
for (; j < MAX_JUMP; i++, j++) {
if (moves[i][1] != moves[j][0]) break;
cout << "," << moves[j][1];
}
cout << ")";
}
cout << endl;
}
// 反復深化
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 (auto& p : jump_table[from]) {
int del = p.first;
int to = p.second;
if (board[del] && !board[to]) {
// OK
moves[n][0] = from;
moves[n][1] = to;
board[from] = board[del] = false;
board[to] = true;
dfs(n + 1, moves[n - 1][1] == from ? jc : jc + 1, limit);
board[to] = false;
board[from] = board[del] = true;
}
}
}
}
}
int main()
{
// 初手を 0 -> 6 に限定
for (int i = 0; i < SIZE; i++) board[i] = true;
board[0] = false;
board[3] = false;
moves[0][0] = 0;
moves[0][1] = HOLE;
for (int limit = 2; limit <= MAX_JUMP; limit++) {
cout << "-----" << limit << "-----\n";
dfs(1, 1, limit);
if (count > 0) break;
}
cout << count << endl;
}
●解答43
このゲームは 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] に矛盾しないコードを選択するのです。
●プログラムの作成
それでは、プログラムを作りましょう。まず、質問したコードとその結果を格納するデータ型を定義します。
リスト : データ型の定義
// コードのデータ型
const int CODE_SIZE = 4;
typedef array<int, CODE_SIZE> Code;
// 質問したコードと結果
struct Query {
int bulls, cows;
Code code;
};
// 質問を格納するテーブル
vector<Query> query_table;
// 正解
Code answer = {9, 4, 3, 1};
コードは STL の array を使って表します。typedef で Code という別名を付けておきます。構造体 Query のメンバ変数 code に質問したコード、bulls と cows のその結果を格納します。Query は query_table に格納します。正解のコードは answer にセットしておきます。
次は bulls を数える関数 count_bulls を作ります。
リスト : bulls を数える
int count_bulls(const Code& xs, const Code& ys)
{
int bulls = 0;
for (int i = 0; i < xs.size(); i++) {
if (xs[i] == ys[i]) bulls++;
}
return bulls;
}
Code xs, ys の要素を比較して、等しい場合は bulls をインクリメントします。最後に bulls を返します。
次は cows を数える処理を作ります。いきなり cows を数えようとすると難しいのですが、2 つの Code に共通の数字を数えることは簡単にできます。この方法では、bulls の個数を含んだ数を求めることになりますが、そこから bulls を引けば cows を求めることができます。関数名は count_same_number としましょう。プログラムは次のようになります。
リスト : 同じ数字の個数を数える
int count_same_number(const Code& xs, const Code& ys)
{
int c = 0;
for (int i = 0; i < xs.size(); i++) {
for (int j = 0; j < ys.size(); j++) {
if (xs[i] == ys[j]) c++;
}
}
return c;
}
最初の for ループで xs から要素を順番に取り出します。次の for ループで、xs[i] と ys の要素を比較して、等しい場合は変数 c をインクリメントします。最後に c を返します。
次は、今まで質問したコードと矛盾していないか調べる関数 check_query を作ります。
リスト : 今まで質問したコードと矛盾していないか
bool check_query(const Code& q)
{
for (const auto& p : query_table) {
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 がこれから質問しようとするコードです。query_table に格納されているすべてのデータで矛盾がなければ true を返します。count_bulls と count_same_number を使って bulls (変数 b) と cows (変数 c) を求めて、質問したときの bulls と cows と比較します。矛盾している場合は false を返します。
次はマスターマインドを解く関数 solver を作ります。
リスト : マスターマインドの解法
void solver(vector<int>& v, int m)
{
Query q;
for (int i = 0; i < CODE_SIZE; i++) {
q.code[i] = v[i];
}
if (check_query(q.code)) {
q.bulls = count_bulls(answer, q.code);
q.cows = count_same_number(answer, q.code) - q.bulls;
// 表示
query_table.push_back(q);
print_query(q);
if (q.bulls == CODE_SIZE) throw "おめでとう！\n";
}
}
引数 v に生成したコードがセットされています。これを Query q の code にコピーします。次に、check_query で矛盾がないかチェックします。OK ならば bulls と cows を求めて q のメンバ変数にセットし、push_back で query_table に追加します。print_query でコードと結果を表示したあと、q.bulls が CODE_SIZE (4) と等しいかチェックします。正解の場合は throw で大域脱出します。
最後に main 関数を作ります。
リスト : main 関数
int main(void)
{
vector<int> buff = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
try {
permutations(buff, solver, 4);
} catch (const char* e) {
cout << e;
}
}
関数 permutations で順列を生成します。solver は例外を送出するので、try - catch で例外を捕捉します。あとのプログラムは簡単なので説明は割愛します。詳細は プログラムリスト３ をお読みください。
●何回で当たるか
それでは実行例を示しましょう。
$ clang++ mastermind.cpp $ ./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 回になりました。これは 参考文献 1 の結果と同じです。質問回数の最大値は 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.cpp : マスターマインドの解法
//
// Copyright (C) 2015-2023 Makoto Hiroi
//
#include <iostream>
#include <array>
#include <vector>
using namespace std;
// Q31
// vector の中から n 個を選ぶ順列を生成
template<class T, class F>
void permutations(vector<T>& v, F func, int n, int m = 0)
{
if (n == m) {
func(v, m);
} else {
T temp = v[m];
for (int i = m; i < v.size(); i++) {
v[m] = v[i];
v[i] = temp;
permutations(v, func, n, m + 1);
v[i] = v[m];
v[m] = temp;
}
}
}
// コードのデータ型
const int CODE_SIZE = 4;
typedef array<int,CODE_SIZE> Code;
// 質問したコードと結果
struct Query {
int bulls, cows;
Code code;
};
// 質問を格納するテーブル
vector<Query> query_table;
// 正解
Code answer = {9, 4, 3, 1};
// Bulls を数える
int count_bulls(const Code& xs, const Code& ys)
{
int bulls = 0;
for (int i = 0; i < xs.size(); i++) {
if (xs[i] == ys[i]) bulls++;
}
return bulls;
}
// 同じ数字を数える
int count_same_number(const Code& xs, const Code& ys)
{
int c = 0;
for (int i = 0; i < xs.size(); i++) {
for (int j = 0; j < ys.size(); j++) {
if (xs[i] == ys[j]) c++;
}
}
return c;
}
// チェック
bool check_query(const Code& q)
{
for (const auto& p : query_table) {
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)
{
cout << query_table.size() << ": [ ";
for (auto x : q.code) cout << x << " ";
cout << "], bulls = " << q.bulls << ", cows = " << q.cows << endl;
}
void solver(vector<int>& v, int m)
{
Query q;
for (int i = 0; i < CODE_SIZE; i++) {
q.code[i] = v[i];
}
if (check_query(q.code)) {
q.bulls = count_bulls(answer, q.code);
q.cows = count_same_number(answer, q.code) - q.bulls;
// 表示
query_table.push_back(q);
print_query(q);
if (q.bulls == CODE_SIZE) throw "おめでとう！\n";
}
}
int main(void)
{
vector<int> buff = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
try {
permutations(buff, solver, 4);
} catch (const char* e) {
cout << e;
}
}
改訂 2023 年 4 月 15 日