[ 0135: Hit & Blow ]

「Hit and Blow」は数当てゲームです。MOO とも呼ばれています。「Cows and Bulls」という場合もあります。

相手が最初に考えた４桁の数字を相手との応答をヒントにして推測するゲーム。

まず、相手は 0-9 の数字からなる 4 桁の数字を考えます。これは：

　▪ 0 で始まってもよい。
　▪ 同じ数字を複数回使ってはいけない。

という条件に従います。

これに対して、こちらはなるべく少ない回数の質問で相手の考えた数字を当てることが目的です。

1 回のやりとりごとにこちらが 4 桁の推測を言い、それに対して、

　▪ 考えた数字と位置も値も一致している桁の数 (Hit)
　▪ 位置は違うがその数字は含まれているような桁の数 (Blow)

を答えてもらいます。

たとえば、相手が最初 4257 を考えた場合に 0274 を言うと、 2 は位置も一致。 4 と 7 は位置が違う。というわけで、1 Hit 2 Blows。これを 1H2B と表記することにします。

なお、上記の条件（0-9 の数字を使い、0 で始まってもよいが、同じ数字を複数個含んではならない）を満たす数は、5040 個あることは簡単にわかります。 5040 個の可能性を、正解（1 個）まで絞り込んでゆくわけです。

むかし早稲田大学の柏木先生は：

"自分が簡単なプログラムを作ったところ、平均 5.247 回というプログラムを作ることが出来た。少なくとも 5.3 回程度のプログラムを作って欲しい。"

と学生諸君に注文を出しました。

私が作ったプログラムでは平均 5.2131 回。理論的最強です。

これは、ちょっとインチキかも知れませんが、解の完全探索結果の構造をあらかじめ求めておいて、これを整数の配列 (array) としてプログラムに入れるという方法をとりました。

完全探索を自分でやるのも面倒なため、東京大学におられた田中先生が実行した探索結果を（別のプログラムでＣ言語のソースコードに変換して）利用しました。

ちょっと、わかりにくい出力形式ですが.....
階層構造になっていますね。

( ゲームプログラムも作っていた湯会老人 )

[ 三方先生のコメント ]

面白そうですね。今は 4 桁以外のバージョンもあるみたいです。

授業が再開しましたが、落ち着いたら私もやってみます。

[ 0135: Hit & Blow ]