vector xs の中から n 個の要素を選ぶ順列を生成する高階関数 permutations(xs, n, func) を定義してください。引数の関数 func には生成した順列 (vector) と要素数を渡すものとします。
順列の生成にはいろいろな方法がありますが、参考文献『Ｃ言語による最新アルゴリズム事典』によると、配列の要素を交換することで順列を簡単に生成することができるそうです。たとえば、i 番目の要素を選ぶことを考えてみましょう。この場合、0 番目から i - 1 番目の要素は選択済みで、i 番目から配列の末尾までの要素が未選択の要素になります。
i 番目の要素を選ぶときは、i 番目の要素と i 番目から末尾までの要素を交換します。i 番目と i 番目の要素の交換は、i 番目の要素を選択することに相当します。要素を交換したら、次は i + 1 番目の要素を i + 1 番目から末尾までの要素の中から選べばいいわけです。これを先頭から n 回繰り返せば、順列を生成することができます。
vector xs の中から n 個の要素を選ぶ組み合わせを生成する高階関数 combinations(xs, n, func) を定義してください。引数の関数 func には生成した組み合わせ (vector) と要素数を渡すものとします。
組み合わせの生成もいろいろな方法がありますが、今回は xs の要素を昇順に並べて、小さな要素から順番に選んでいくことにします。たとえば、i 番目の要素を選択するとき、0 番目から i - 1 番目の要素は選択済みで、i 番目からベクタの末尾の中から要素を選びます。このとき、i - 1 番目よりも大きな要素を選ぶようにします。小さな要素から順番に選択しているので、i - 1 番目よりも小さな要素は既に選んだことがあるからです。このように要素を選択すると、生成される組み合わせの要素は昇順に並べられます。つまり、組み合わせの要素が昇順に並ぶように選択すればいいわけです。
簡単な例を示しましょう。[1, 2, 3, 4, 5] から 3 つの要素を選ぶ組み合わせを生成します。小さな要素から順番に選んでいくと、最初に生成される組み合わせは [1, 2, 3] になります。そのあと、3 と 4, 5 を交換して [1, 2, 4], [1, 2, 5] が生成されます。
次は 1 番目の要素 2 を 3, 4, 5 と交換します。3 と交換するとベクタは [1, 3, 2, 4, 5] になります。次に、2 番目の要素を選択しますが、2 は 3 よりも小さいので、選択しません。4, 5 は 3 よりも大きいので、[1, 3, 4], [1, 3, 5] という組み合わせが生成されます。あとはこれを繰り返すことで、すべての組み合わせを求めることができます。
vector xs のべき集合を求める高階関数 power_set(xs, func) を定義してください。たとえば vector {1, 2, 3} のべき集合は {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} になります。引数の関数 func に生成したべき集合と要素数を渡すものとします。
ハノイの塔は、棒に刺さっている大きさが異なる複数の円盤を、次の規則に従ってほかの棒に移動させるパズルです。
ハノイの塔を解くプログラムを作ってください。
1 から 9 までの数字を順番に並べ、間に + と - を補って 100 になる式を作ってください。1 の前に - 符号はつけないものとします。
例 : 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
パズルの世界では、1 から 9 までの数字を 1 個ずつすべて使った数字を「小町数」といいます。たとえば、123456789 とか 321654987 のような数字です。「小町算」というものもあり、たとえば 123 + 456 + 789 とか 321 * 654 + 987 のようなものです。この問題は小町算の中でも特に有名なパズルです。
パズルの世界では小町数に 0 を加えた数を大町数といいます。そして、0 から 9 までの 10 個の数字を 1 個ずつ使った計算を大町算といいます。ただし、0123456789 のように最上位の桁に 0 を入れることはできません。それでは問題です。
Ｃ/Ｃ++でプログラムを作る場合、大町数は整数 (int) の範囲を超えますが、long long int を使えば簡単です。
計算式の数字を文字や記号に置き換えて、それを元の数字に戻すパズルを「覆面算」といいます。異なる文字は異なる数字を表し、同じ文字は同じ数字を表します。使用する数字は 0 から 9 までで、最上位の桁に 0 を入れることはできません。それでは問題です。
S E N D
+ M O R E
-------------
M O N E Y
図 : 覆面算
問題はデュードニーが 1924 年に発表したもので、覆面算の古典といわれる有名なパズルです。
下図の A から I の場所に 1 から 9 までの数字をひとつずつ配置します。縦横斜めの合計が等しくなるように数字を配置してください。
┌─┬─┬─┐ 式
│Ａ│Ｂ│Ｃ│ A + B + C = N, A + E + I = N
├─┼─┼─┤ D + E + F = N, C + E + G = N
│Ｄ│Ｅ│Ｆ│ G + H + I = N
├─┼─┼─┤ A + D + G = N
│Ｇ│Ｈ│Ｉ│ B + E + H = N
└─┴─┴─┘ C + F + I = N
図 : 魔方陣
「8 クイーン」はコンピュータに解かせるパズルの中でも特に有名な問題です。このパズルは 8 行 8 列のチェス盤の升目に、8 個のクイーンを互いの利き筋が重ならないように配置する問題です。クイーンは将棋の飛車と角をあわせた駒で、縦横斜めに任意に動くことができます。解答の一例を下図に示します。
列
1 2 3 4 5 6 7 8
*-----------------*
1 | Q . . . . . . . |
2 | . . . . Q . . . |
3 | . . . . . . . Q |
行 4 | . . . . . Q . . |
5 | . . Q . . . . . |
6 | . . . . . . Q . |
7 | . Q . . . . . . |
8 | . . . Q . . . . |
*-----------------*
図 : 8 クイーンの解答例
8 クイーンを解くプログラムを作ってください。
ナイト (騎士) はチェスの駒のひとつで将棋の桂馬の動きを前後左右にとることができます。次の図を見てください。
┌─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┐
│ │●│ │●│ │ │Ｋ│ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│●│ │ │ │●│ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│ │ │Ｋ│ │ │ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│●│ │ │ │●│ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│ │●│ │●│ │ │ │ │ │ │ │
└─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┘
●：ナイト (K) が動ける位置 問題
問題 : 騎士の巡歴
このナイトを動かして、N 行 M 列の盤面のどのマスにもちょうど一回ずつ訪れるような経路を求めるのが問題です。ちなみに、3 行 3 列、4 行 4 列の盤面には解がありませんが、5 行 5 列の盤面には解があります。5 行 5 列の盤面でナイトの移動経路の総数を求めてください。
リスト : 順列の生成
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;
}
}
}
// ベクタの表示
void print_vector(const vector<int>& v, int n)
{
for (int i = 0; i < n; i++) cout << v[i] << " ";
cout << endl;
}
関数 permutations の引数 v が vector、func が順列を受け取る関数、n が選択する要素の個数、m が選択した要素の個数です。m が n と等しい場合、順列が一つ完成したので、関数 func に渡して呼び出します。そうでなければ、m 番目の要素を m 番目から v の末尾までの要素と交換します。
最初に、v[m] を変数 temp に退避します。次に、for ループで v[i] と v[m] を交換して、permutations を再帰呼び出しします。再帰呼び出しから戻ってきたら、v[i] と v[m] の値を元に戻します。これで順列を生成することができます。とても簡単ですね。
リスト : 簡単なテスト
int main()
{
vector<int> a = {1, 2, 3, 4};
permutations(a, print_vector, 3);
}
1 2 3 1 2 4 1 3 2 1 3 4 1 4 3 1 4 2 2 1 3 2 1 4 2 3 1 2 3 4 2 4 3 2 4 1 3 2 1 3 2 4 3 1 2 3 1 4 3 4 1 3 4 2 4 2 3 4 2 1 4 3 2 4 3 1 4 1 3 4 1 2
リスト : 組み合わせの生成
template<class T, class F>
void combinations(vector<T>& v, F func, int n, int m = 0)
{
if (m == n) {
func(v, n);
} else {
T tmp = v[m];
for (int i = m; i < v.size(); i++) {
if (m == 0 || v[m - 1] < v[m]) {
v[m] = v[i];
v[i] = tmp;
combinations(v, func, n, m + 1);
v[i] = v[m];
v[m] = tmp;
}
}
}
}
関数 combinations の引数 v が vector で、func が組み合わせを受け取る関数で、n が選択する要素の個数、m が選択した要素の個数です。m が n と等しい場合、組み合わせが一つ完成したので、関数 func に渡して呼び出します。そうでなければ、m 番目の要素を m 番目から v の末尾までの要素と交換します。
最初に v[m] を変数 temp に退避します。次に、for ループで v[i] と v[m] を交換して、combinationss を再帰呼び出しします。このとき、一つ前の要素よりも大きな要素を選択します。再帰呼び出しから戻ってきたら、v[i] と v[m] の値を元に戻します。これで組み合わせを生成することができます。とても簡単ですね。
リスト : 簡単なテスト
int main()
{
vector<int> b = {1, 2, 3, 4, 5};
combinations(b, print_vector, 3);
}
1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
リスト : べき集合の生成
template<class T, class F>
void power_set_sub(vector<T>& xs, int m, F func, vector<T>& a)
{
if (m == xs.size()) {
func(a, a.size());
} else {
power_set_sub(xs, m + 1, func, a);
a.push_back(xs[m]);
power_set_sub(xs, m + 1, func, a);
a.pop_back();
}
}
template<class T, class F>
void power_set(vector<T>& xs, F func)
{
vector<T> a;
power_set_sub(xs, 0, func, a);
}
power_set は簡単です。実際の処理は関数 power_set_sub で行います。xs の m 番目の要素を選択する場合は、その要素を引数 a に追加して、power_set_sub を再帰呼び出しします。選択しない場合は、引数 a に要素を追加せずに power_set_sub を再帰呼び出しするだけです。これでべき集合の要素をすべて求めることができます。
リスト : 簡単なテスト
int main()
{
vector<int> a = {1, 2, 3, 4};
power_set(a, print_vector);
}
<-- 空集合
4
3
3 4
2
2 4
2 3
2 3 4
1
1 4
1 3
1 3 4
1 2
1 2 4
1 2 3
1 2 3 4
ハノイの塔は、再帰を使えば簡単に解ける問題です。たとえば、3 枚の円盤が左の棒に刺さっているとします。この場合、いちばん大きな円盤を中央の棒に移すには、その上の 2 枚の円盤を右の棒に移しておけばいいですね。いちばん大きな円盤を中央に移したら、右の棒に移した 2 枚の円盤を中央の棒に移すことを考えればよいわけです。したがって、n 枚の円盤を左から中央の棒に移すプログラムは次のように表現できます。
これを素直にプログラムすると次のようになります。
リスト：ハノイの塔
void hanoi(int n, char from, char to, char via)
{
if (n == 1) {
cout << from << " -> " << to << endl;
} else {
hanoi(n - 1, from, via, to);
cout << from << " -> " << to << endl;
hanoi(n - 1, via, to, from);
}
}
引数 n は動かす円盤の枚数、from は最初に円盤が刺さっている棒、to は円盤を移す棒、via は残りの棒を示します。動かす円盤の枚数が 1 枚の場合、from から to へ円盤に移動します。これが再帰の停止条件になっています。
円盤が複数枚ある場合、hanoi を再帰呼び出しして、n - 1 枚の円盤を棒 via に移動します。棒 from に残った円盤は 1 枚なので、それを棒 to に移動します。これを出力演算子 << で出力します。最後に、棒 via に移した円盤を棒 to に移動します。ここでも再帰呼び出しが行われます。
プログラムはこれで完成です。それでは実行してみましょう。
--- ３枚 --- A -> B A -> C B -> C A -> B C -> A C -> B A -> B --- ４枚 --- A -> C A -> B C -> B A -> C B -> A B -> C A -> C A -> B C -> B C -> A B -> A C -> B A -> C A -> B C -> B
それではプログラムを作りましょう。式は次のように + を '+' に、- を '-' として、整数の配列で表すことにします。
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 => [1, '+', 2, '+', 3, '-', 4, '+', 5, '+', 6, '+', 78, '+', 9]
あとは、式を生成して値を計算するだけです。次の図を見てください。
[1] => [1 + 2] => [1 + 2 + 3]
=> [1 + 2 - 3]
=> [1 + 23]
=> [1 - 2] => [1 - 2 + 3]
=> [1 - 2 - 3]
=> [1 - 23]
=> [12] => [12 + 3]
=> [12 - 3]
=> [123]
式を生成するとき、配列に数字と演算子を順番に追加していきます。数字と +, - を追加する処理は簡単です。プログラムのポイントは数字を連結する処理、たとえば 1 と 2 を連結して一つの数値 12 にする処理です。この処理は配列の末尾の数字 1 を 12 (1 * 10 + 2) に置き換えることで実現できます。配列が [1 + 2] であれば、数字 2 を 23 (2 * 10 + 3) に置き換えます。
式を生成するプログラムは次のようになります。
リスト：式の生成
void komachi(vector<int>& buff, int n, int m)
{
if (n == 10) {
if (calc_expr(buff, m) == 100) {
print_expr(buff, m);
}
} else {
buff[m] = '+';
buff[m + 1] = n;
komachi(buff, n + 1, m + 2);
buff[m] = '-';
buff[m + 1] = n;
komachi(buff, n + 1, m + 2);
int temp = buff[m - 1];
buff[m - 1] = buff[m - 1] * 10 + n;
komachi(buff, n + 1, m);
buff[m - 1] = temp;
}
}
komachi の引数 n が追加する数字、buff が生成する式、m が buff に書き込んだ要素の個数を表します。n が 10 の場合は、式が完成したので値を計算します。関数 calc_expr で式 buff を計算します。値が 100 になれば関数 print_expr で式を出力します。
n が 10 未満であれば、演算子 (+. -) と n を buff に追加して komachi を再帰呼び出しします。最後が数字を連結する処理です。この場合、配列の内容を破壊的に修正するので、配列末尾の数値 buff[m - 1] を変数 temp に保存しておきます。それから、buff[m - 1] の値を buff[m - 1] * 10 + n に書き換えます。これで数字を連結することができます。komachi を再帰呼び出しして戻ってきたら末尾の数字を元に戻します。この処理を忘れると正常に動作しません。ご注意くださいませ。
次は式を計算する calc_expr を作ります。今回の問題は演算子に + と - しかないので、配列で表現した式を計算することは簡単です。次のプログラムを見てください。
リスト : 式の計算 (+ と - だけ)
int calc_expr(vector<int>& buff, int m)
{
int sum = buff[0];
for (int i = 1; i < m; i += 2) {
switch(buff[i]) {
case '+':
sum += buff[i + 1];
break;
default:
sum -= buff[i + 1];
}
}
return sum;
}
buff[0] を変数 sum にセットします。あとは、for ループの中で配列から演算子を表す文字 (buff[i]) と数値を表す文字列 (buff[i + 1]) を順番に取り出して計算します。buff[i] が '+' であれば sum に buff[i + 1] を加算し、"-" であれば sum から buff[i + 1] を減算します。
komachi は次のように呼び出します。
リスト : komachi の呼び出し vector<int> buff(17); buff[0] = 1; komachi(buff, 2, 1);
数式を表す vector を用意して、先頭要素に 1 をセットします。それから、komachi(buff, 2, 1) と呼び出します。あとのプログラムは簡単なので説明は割愛します。詳細はプログラムリストをお読みください。
それでは実行結果を示します。
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100 1 + 23 - 4 + 5 + 6 + 78 - 9 = 100 1 + 23 - 4 + 56 + 7 + 8 + 9 = 100 12 + 3 + 4 + 5 - 6 - 7 + 89 = 100 12 + 3 - 4 + 5 + 67 + 8 + 9 = 100 12 - 3 - 4 + 5 - 6 + 7 + 89 = 100 123 + 4 - 5 + 67 - 89 = 100 123 + 45 - 67 + 8 - 9 = 100 123 - 4 - 5 - 6 - 7 + 8 - 9 = 100 123 - 45 - 67 + 89 = 100
全部で 11 通りの解が出力されます。
最初に整数 n の範囲を絞り込みます。大町数の最大値は 9876543210 で最小値は 1023456789 ですから、n の値は次の範囲内になります。
10234567891/3 => 1007.759 1006 * 1007 * 1008 => 1021146336 < 1023456789
98765432101/3 => 2145.532 2145 * 2146 * 2147 => 9883005990 > 9876543210
これらの計算結果から n は 1007 以上 2144 以下であることがわかります。n の範囲がぐっと狭くなりましたね。これならば、あとは単純に計算して大町数になるかチェックすればいいでしょう。プログラムは次のようになります。
リスト : パズル「３数で大町どうさま」の解法
void oomachi_sub(long long n)
{
bool used[10] = {};
long long m = n * (n + 1) * (n + 2);
for (long long x = m; x > 0; x /= 10) {
int y = x % 10;
if (used[y]) return;
used[y] = true;
}
cout << n << " * " << n + 1 << " * " << n + 2 << " = " << m << endl;
}
void oomachi()
{
for (int n = 1007; n <= 2144; n++)
oomachi_sub(n);
}
関数 oomachi で 1007 から 2144 までの数値を生成して、関数 oomachi_sub で大町数になるかチェックします。oomachi_sub は数値 n を受け取り、n * (n + 1) * (n + 2) を計算して変数 m にセットします。m は 10 桁の数値になるので、大町数であれば 10 個の数字がちょうどひとつずつあるはずです。したがって、数字が重複していないことを確認すればいいわけです。
for ループで 1 桁ずつ数字 y を取り出し、配列 used の y 番目の要素をチェックします。true であれば同じ数字があります。return で処理を終了します。false の場合は used[y] を true にセットして次の数字をチェックします。大町数の条件を満たしていれば、for ループを終了するので、最後に解を出力します。
これでプログラムは完成です。さっそく実行してみましょう。
1267 * 1268 * 1269 = 2038719564 1332 * 1333 * 1334 = 2368591704
2 通りの解を見つけることができました。
式 SEND + MORE = MONEY は足し算なので、M が 1 であることはすぐにわかります。ここでは、それ以外の数字を求めるプログラムを作ります。次のリストを見てください。
リスト : 覆面算
// 文字と添字の対応
// 0 1 2 3 4 5 6
// s e n d o r y
void hukumen_check(const vector<int>& v, int n)
{
int send = v[0] * 1000 + v[1] * 100 + v[2] * 10 + v[3];
int more = 1000 + v[4] * 100 + v[5] * 10 + v[1];
int money = 10000 + v[4] * 1000 + v[2] * 100 + v[1] * 10 + v[6];
if (send + more == money)
cout << send << " + " << more << " = " << money << endl;
}
void hukumen()
{
vector<int> v = {0, 2, 3, 4, 5, 6, 7, 8, 9};
permutations(v, hukumen_check, 7);
}
permutations は問題 31 で作成した関数です。あとは関数 hukumen_check で数値 send, more, money を計算して send + more = money を満たしているかチェックします。とても簡単なプログラムですね。さっそく実行してみましょう。
9567 + 1085 = 10652
答えは 9567 + 1085 = 10652 の 1 通りしかありません。興味のある方は、ほかの方法でも試してみてください。
リスト : 魔方陣の解法
// 直線
vector<vector<int>> line_table = {
{0, 1, 2}, {3, 4, 5}, {6, 7, 8},
{0, 3, 6}, {1, 4, 7}, {2, 5, 8},
{0, 4, 8}, {2, 4, 6}
};
// 直線の和
int line_sum(const vector<int>& line, const vector<int>& v)
{
return v[line[0]] + v[line[1]] + v[line[2]];
}
void check_magic(const vector<int>& v, int n)
{
int sum = line_sum(line_table[0], v);
for (int i = 1; i < 8; i++) {
if (sum != line_sum(line_table[i], v)) return;
}
// 表示
cout << v[0] << " " << v[1] << " " << v[2] << endl;
cout << v[3] << " " << v[4] << " " << v[5] << endl;
cout << v[6] << " " << v[7] << " " << v[8] << endl;
cout << endl;
}
void magic()
{
vector<int> buff = {1, 2, 3, 4, 5, 6, 7, 8, 9};
permutations(buff, check_magic, 9);
}
関数 permutations で 1 から 9 までの数字の順列を生成します。それを関数 check_magic に渡して、魔方陣の条件を満たしているかチェックします。関数 line_sum で各直線の和を求めて、すべて同じ値であれば魔方陣の条件を満たすので、盤面を表示します。
それでは実行結果を示します。
2 7 6 9 5 1 4 3 8 2 9 4 7 5 3 6 1 8 4 3 8 9 5 1 2 7 6 4 9 2 3 5 7 8 1 6 6 1 8 7 5 3 2 9 4 6 7 2 1 5 9 8 3 4 8 3 4 1 5 9 6 7 2 8 1 6 3 5 7 4 9 2
対称解を含めると、解は 8 通りあります。最近のパソコンはハイスペックなので、このままでも高速に解けるのですが、対称解を排除すると枝刈りの効果により、実行時間はもう少し速くなります。興味のある方はプログラムを改良してみてください。
8 クイーンを解くには、すべての置き方を試してみるしか方法はありません。最初のクイーンは、盤上の好きなところへ置くことができるので、64 通りの置き方があります。次のクイーンは 63 通り、その次は 62 通りあるので、置き方の総数は 64 から 57 までの整数を掛け算した 178,462,987,637,760 通りもあります。
ところが、解答例を見ればわかるように、同じ行と列に 2 つ以上のクイーンを置くことはできません。上図の解答例を配列を使って表すと、 次のようになります。
1 2 3 4 5 6 7 8 <--- 列の位置
---------------------------
[1, 7, 5, 8, 2, 4, 6, 3] <--- 要素が行の位置を表す
図 : 配列での行と列の表現方法
列を配列の位置に、行番号を要素に対応させれば、各要素には 1 から 8 までの数字が重複しないで入ることになります。すなわち、1 から 8 までの順列の総数である 8! = 40320 通りの置き方を調べるだけでよいのです。パズルを解く場合、そのパズル固有の性質をうまく使って、調べなければならない場合の数を減らすように工夫することが大切です。あとは、その順列が 8 クイーンの条件を満たしているかチェックすればいいわけです。
それでは、プログラムを作りましょう。次のリストを見てください。
リスト : 8 クイーンの解法
// 解の総数
int queen_count = 0;
// 衝突の検出
bool attack(vector<int>& board, int i, int m)
{
int n = 1;
int x = board[i++];
for (; i < m; i++, n++) {
int y = board[i];
if (x == y + n || x == y - n) return true;
}
return false;
}
// 安全か？
void safe(vector<int>& board, int m)
{
for (int i = 0; i < m - 1; i++) {
if (attack(board, i, m)) return;
}
queen_count++;
print_vector(board, m);
}
template<class T>
void iota(T& seq, int n)
{
for (auto& x : seq) x = n++;
}
void queen(int n)
{
vector<int> board(n);
iota(board, 1);
permutations(board, safe, n);
cout << queen_count << endl;
}
関数 queen で permutations を呼び出し、生成された順列 board が 8 クイーンの条件を満たしているかチェックします。関数 safe は board の先頭の要素から順番に衝突のチェックを行います。端にあるクイーンから順番に調べるとすると、斜めの利き筋は次のように表すことができます。
1 2 3 --> 調べる方向
*-------------
| . . . . . .
| . . . -3. . 5 - 3 = 2
| . . -2. . . 5 - 2 = 3
| . -1. . . . 5 - 1 = 4
| Q . . . . . Q の位置は 5
| . +1. . . . 5 + 1 = 6
| . . +2. . . 5 + 2 = 7
| . . . +3. . 5 + 2 = 8
*-------------
図 : 衝突の検出
図を見てもらえばおわかりのように、Q が行 5 にある場合、ひとつ隣の列は 4 と 6 が利き筋に当たります。2 つ隣の列の場合は 3 と 7 が利き筋に当たります。このように単純な足し算と引き算で、利き筋を計算することができます。この処理を関数 attack で行います。
attack は board の i 番目から斜めの利き筋に当たるか調べます。引数 m がクイーンの個数です。変数 x がクイーンの位置、変数 n が差分を表します。for ループで board からクイーン y を取り出し、y + n または y - n が x と等しいかチェックします。等しい場合は衝突しているので true を返します。そうでなければ、次のクイーンを調べます。このとき、差分 n を +1 することをお忘れなく。すべてのクイーンを調べたら false を返します。
これでプログラムは完成です。それでは実行してみましょう。
1 5 8 6 3 7 2 4 1 6 8 3 7 4 2 5 1 7 4 6 8 2 5 3 ・・ 省略 ・・ 8 2 5 3 1 7 4 6 8 3 1 6 2 5 7 4 8 4 1 3 6 2 7 5 92
8 クイーンの場合、回転解や鏡像解を含めると全部で 92 通りあります。なお、このプログラムはクイーンの個数を増やすと極端に遅くなります。興味のある方はプログラムを改良してみてください。
それではプログラムを作りましょう。今回は盤面を 2 次元配列で表すことにします。この場合、騎士の移動手順は 5 行 5 列の盤面に記録したほうが簡単です。騎士が訪れていないマスを 0 とし、騎士の移動手順を 1 から始めれば、移動できるマスの判定を簡単に行うことができます。また、経路の出力も盤面を表示した方が直感的でわかりやすいかもしれません。
次は盤面の構成を考えましょう。単純な 5 行 5 列の 2 次元配列にすると、騎士が盤面から飛び出さないようにするため座標の範囲チェックが必要になります。このような場合、盤面の外側に壁を設定するとプログラムが簡単になります。
騎士は最大で 2 マス移動するので、壁の厚さも 2 マス用意します。したがって、盤面を表す配列は 9 行 9 列の大きさになります。壁に 0 以外の値 (1) を設定しておけば、騎士が盤面から飛び出して壁の位置に移動しようとしても、盤面の値が 0 ではないので実際に移動することはできません。これで騎士を移動したときの範囲チェックを省略することができます。
プログラムは次のようになります。
リスト : 騎士の巡歴
// 盤面の初期化
void init_board(vector<vector<int>>& board)
{
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++ ) {
if (i >=2 && i < 7 && j >=2 && j < 7)
board[i][j] = 0;
else
board[i][j] = 1; // 壁
}
}
}
// 移動
int dx[8] = { 1, 2, 2, 1, -1, -2, -2, -1};
int dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
// 解の個数
int knight_count;
// 盤面の表示
void print_board(vector<vector<int>>& board)
{
knight_count++;
for (int i = 2; i < 7; i++) {
for (int j = 2; j < 7; j++)
cout << setw(2) << board[i][j] << " ";
cout << endl;
}
cout << endl;
}
// 解法
void solverk(vector<vector<int>>& board, int n, int x, int y)
{
if (n > 25)
print_board(board);
else
for (int i = 0; i < 8; i++) {
int x1 = x + dx[i];
int y1 = y + dy[i];
if (board[x1][y1] == 0) {
board[x1][y1] = n;
solverk(board, n + 1, x1, y1);
board[x1][y1] = 0;
}
}
}
void knight()
{
vector<vector<int>> board(9, vector<int>(9));
init_board(board);
board[2][2] = 1;
solverk(board, 2, 2, 2);
cout << knight_count << endl;
}
配列 dx は騎士の x 方向の変位、配列 dy は y 方向の変位を表します。現在の座標にこの値を加えることで、次の座標を決定します。配列 board は盤面を表します。関数 init_board で、壁の部分は 1 に、実際の盤面は 0 に初期化しておきます。
関数 solverk は引数として手数 n と騎士の座標 x, y を受け取ります。まず、n が 25 よりも大きくなったかチェックします。そうであれば、騎士はすべてのマスを訪れたので、print_board で盤面を出力します。
そうでなければ、次に移動するマスを選びます。for 文で dx と dy の要素を取り出して x と y の値に加え、solverk を再帰呼び出しします。再帰呼び出しから戻ってきたら、board[x1][y1] の値を 0 に戻すことをお忘れなく。あとはとくに難しいところはないと思います。
実行結果は次のようになります。
1 16 21 10 25 20 11 24 15 22 17 2 19 6 9 12 7 4 23 14 3 18 13 8 5 ・・・省略・・・ 1 16 11 6 3 10 5 2 17 12 15 22 19 4 7 20 9 24 13 18 23 14 21 8 25 304
解は全部で 304 通りあります。
//
// yacp4.cpp : Yet Another C++ Problems (4)
//
// Copyright (C) 2015-2023 Makoto Hiroi
//
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
// Q31
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;
}
}
}
// ベクタの表示
void print_vector(const vector<int>& v, int n)
{
for (int i = 0; i < n; i++) cout << v[i] << " ";
cout << endl;
}
// Q32
template<class T, class F>
void combinations(vector<T>& v, F func, int n, int m = 0)
{
if (m == n) {
func(v, n);
} else {
T tmp = v[m];
for (int i = m; i < v.size(); i++) {
v[m] = v[i];
v[i] = tmp;
if (m == 0 || v[m - 1] < v[m]) combinations(v, func, n, m + 1);
v[i] = v[m];
v[m] = tmp;
}
}
}
// Q33
template<class T, class F>
void power_set_sub(vector<T>& xs, int m, F func, vector<T>& a)
{
if (m == xs.size()) {
func(a, a.size());
} else {
power_set_sub(xs, m + 1, func, a);
a.push_back(xs[m]);
power_set_sub(xs, m + 1, func, a);
a.pop_back();
}
}
template<class T, class F>
void power_set(vector<T>& xs, F func)
{
vector<T> a;
power_set_sub(xs, 0, func, a);
}
// Q34
void hanoi(int n, char from, char to, char via)
{
if (n == 1) {
cout << from << " -> " << to << endl;
} else {
hanoi(n - 1, from, via, to);
cout << from << " -> " << to << endl;
hanoi(n - 1, via, to, from);
}
}
// Q35
void print_expr(vector<int>& buff, int m)
{
cout << buff[0] << " ";
for (int i = 1; i < m; i += 2) {
cout << char(buff[i]) << " " << buff[i + 1] << " ";
}
cout << "= 100\n";
}
int calc_expr(vector<int>& buff, int m)
{
int sum = buff[0];
for (int i = 1; i < m; i += 2) {
switch(buff[i]) {
case '+':
sum += buff[i + 1];
break;
default:
sum -= buff[i + 1];
}
}
return sum;
}
void komachi(vector<int>& buff, int n, int m)
{
if (n == 10) {
if (calc_expr(buff, m) == 100) {
print_expr(buff, m);
}
} else {
buff[m] = '+';
buff[m + 1] = n;
komachi(buff, n + 1, m + 2);
buff[m] = '-';
buff[m + 1] = n;
komachi(buff, n + 1, m + 2);
int temp = buff[m - 1];
buff[m - 1] = buff[m - 1] * 10 + n;
komachi(buff, n + 1, m);
buff[m - 1] = temp;
}
}
// Q36
void oomachi_sub(long long n)
{
bool used[10] = {};
long long m = n * (n + 1) * (n + 2);
for (long long x = m; x > 0; x /= 10) {
int y = x % 10;
if (used[y]) return;
used[y] = true;
}
cout << n << " * " << n + 1 << " * " << n + 2 << " = " << m << endl;
}
void oomachi()
{
for (int n = 1007; n <= 2144; n++)
oomachi_sub(n);
}
// Q37
// 文字と添字の対応
// 0 1 2 3 4 5 6
// s e n d o r y
void hukumen_check(const vector<int>& v, int n)
{
int send = v[0] * 1000 + v[1] * 100 + v[2] * 10 + v[3];
int more = 1000 + v[4] * 100 + v[5] * 10 + v[1];
int money = 10000 + v[4] * 1000 + v[2] * 100 + v[1] * 10 + v[6];
if (send + more == money)
cout << send << " + " << more << " = " << money << endl;
}
void hukumen()
{
vector<int> v = {0, 2, 3, 4, 5, 6, 7, 8, 9};
permutations(v, hukumen_check, 7);
}
// Q38
// 0 1 2
// 3 4 5
// 6 7 8
vector<vector<int>> line_table = {
{0, 1, 2}, {3, 4, 5}, {6, 7, 8},
{0, 3, 6}, {1, 4, 7}, {2, 5, 8},
{0, 4, 8}, {2, 4, 6}
};
int line_sum(const vector<int>& line, const vector<int>& v)
{
return v[line[0]] + v[line[1]] + v[line[2]];
}
void check_magic(const vector<int>& v, int n)
{
int sum = line_sum(line_table[0], v);
for (int i = 1; i < 8; i++) {
if (sum != line_sum(line_table[i], v)) return;
}
// 表示
cout << v[0] << " " << v[1] << " " << v[2] << endl;
cout << v[3] << " " << v[4] << " " << v[5] << endl;
cout << v[6] << " " << v[7] << " " << v[8] << endl;
cout << endl;
}
void magic()
{
vector<int> buff = {1, 2, 3, 4, 5, 6, 7, 8, 9};
permutations(buff, check_magic, 9);
}
// Q39
// 解の総数
int queen_count = 0;
// 衝突の検出
bool attack(vector<int>& board, int i, int m)
{
int n = 1;
int x = board[i++];
for (; i < m; i++, n++) {
int y = board[i];
if (x == y + n || x == y - n) return true;
}
return false;
}
// 安全か？
void safe(vector<int>& board, int m)
{
for (int i = 0; i < m - 1; i++) {
if (attack(board, i, m)) return;
}
queen_count++;
print_vector(board, m);
}
template<class T>
void iota(T& seq, int n)
{
for (auto& x : seq) x = n++;
}
void queen(int n)
{
vector<int> buff(n);
iota(buff, 1);
permutations(buff, safe, n);
cout << queen_count << endl;
}
// Q40
// 盤面の初期化
void init_board(vector<vector<int>>& board)
{
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++ ) {
if (i >=2 && i < 7 && j >=2 && j < 7)
board[i][j] = 0;
else
board[i][j] = 1; // 壁
}
}
}
// 移動
int dx[8] = { 1, 2, 2, 1, -1, -2, -2, -1};
int dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
// 解の個数
int knight_count;
// 盤面の表示
void print_board(vector<vector<int>>& board)
{
knight_count++;
for (int i = 2; i < 7; i++) {
for (int j = 2; j < 7; j++)
cout << setw(2) << board[i][j] << " ";
cout << endl;
}
cout << endl;
}
// 解法
void solverk(vector<vector<int>>& board, int n, int x, int y)
{
if (n > 25)
print_board(board);
else
for (int i = 0; i < 8; i++) {
int x1 = x + dx[i];
int y1 = y + dy[i];
if (board[x1][y1] == 0) {
board[x1][y1] = n;
solverk(board, n + 1, x1, y1);
board[x1][y1] = 0;
}
}
}
void knight()
{
vector<vector<int>> board(9, vector<int>(9));
init_board(board);
board[2][2] = 1;
solverk(board, 2, 2, 2);
cout << knight_count << endl;
}
int main()
{
// Q31
vector<int> a = {1, 2, 3, 4};
cout << "-- permutatios --\n";
permutations(a, print_vector, 3);
permutations(a, print_vector, 4);
// Q32
vector<int> b = {1, 2, 3, 4, 5};
cout << "-- combinations --\n";
combinations(b, print_vector, 3);
combinations(b, print_vector, 4);
// Q33
cout << "-- power_set--\n";
power_set(a, print_vector);
// Q34
cout << "--- hanoi ３枚 ---\n";
hanoi(3, 'A', 'B', 'C');
cout << "--- hanoi ４枚 ---\n";
hanoi(4, 'A', 'B', 'C');
// Q35
cout << "--- 小町算 ---\n";
vector<int> buff(17);
buff[0] = 1;
komachi(buff, 2, 1);
// Q36
cout << "--- 大町算 ---\n";
oomachi();
// Q37
cout << "--- 覆面算 ---\n";
hukumen();
// Q38
cout << "--- 魔方陣 ---\n";
magic();
// Q39
cout << "--- 8 Queens ---\n";
queen(8);
// Q40
cout << "--- 騎士の巡歴 ---\n";
knight();
}