「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 クイーンの解答例
N Queens Problem は「8 クイーン」の拡張バージョンで、N 行 N 列の盤面に N 個のクイーンを互いの利き筋が重ならないように配置する問題です。
8 クイーンは拙作のページ Yet Another Clang Problems (4) で取り上げました。回転解や鏡像解を含めると全部で 92 通りあります。このとき作成したプログラムはクイーンの個数を増やすと、プログラムの実行時間は極端に遅くなります。クイーンの個数を増やすのは簡単です。次のリストを見てください。
リスト : N Queens Problem
int main(void)
{
for (int i = 8; i < 13; i++) {
clock_t s = clock();
count = 0;
permutations(i, 0);
printf("%d, %d, %.3f\n", i, count, (double)(clock() - s) / CLOCKS_PER_SEC);
}
return 0;
}
プログラムは解を表示するのではなく、解の個数をカウントするように修正しています。
表 : 実行結果 (時間 : 秒)
個数 : 8 : 9 : 10 : 11 : 12
-----+-------+-------+-------+-------+-------
解 : 92 : 352 : 724 : 2680 : 14200
時間 : 0.003 : 0.023 : 0.196 : 2.120 : 25.813
実行環境 : clang version 14.0.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz 最適化オプション : -O2
実行結果は上表のようになりました。クイーンの個数をひとつ増やしただけでも、実行時間はとても遅くなります。実はこのプログラム、とても非効率なことをやっているのです。
実行速度が遅い理由は、失敗することがわかっている順列も生成してしまうからです。たとえば、最初 (1, 1) の位置にクイーンを置くと、次のクイーンは (2, 2) の位置に置くことはできませんね。したがって、[1, 2, X, X, X, X, X, X,] という配置はすべて失敗するのですが、順列を発生させてからチェックする方法では、このような無駄を省くことができません。
そこで、クイーンの配置を決めるたびに衝突のチェックを行うことにします。これをプログラムすると次のようになります。
リスト : N Queens Problem (改良版)
bool attack1(int x, int i)
{
int n = 1;
while (--i >= 0) {
int y = board[i];
if (x == y + n || x == y - n) return true;
n++;
}
return false;
}
void queen1(int n, int m)
{
if (n == m) {
count++;
} else {
for (int i = 1; i <= n; i++) {
if (used[i] || attack1(i, m)) continue;
board[m] = i;
used[i] = true;
queen1(n, m + 1);
used[i] = false;
}
}
}
関数 queen1 でクイーンを選択するとき、関数 attack1 を呼び出して選択したクイーンが衝突しないかチェックします。attack1 は配列 board の末尾から先頭に向かって衝突をチェックしていることに注意してください。あとは特に難しいところはないでしょう。
実行結果を示します。
表 : 実行結果 (時間 : 秒)
個数 : 10 : 11 : 12 : 13 : 14 : 15
-----+-------+-------+--------+-------+-------+--------
解 : 724 : 2680 : 14200 : 73712 :365596 : 2279184
(0) : 0.196 : 2.120 : 25.813 : ----- : ----- : ------
(1) : 0.004 : 0.018 : 0.098 : 0.557 : 3.464 : 22.911
実行時間は速くなりましたが、クイーンの個数が 15 を超えると実行時間が極端に遅くなります。これは、異なる数字（クイーンの位置）を選ぶために行う配列 used のチェックと、利き筋をチェックする関数 attack1 に時間がかかるからです。そこで、藤原博文さんの８クイーン＠勉強会のページ (http://www.pro.or.jp/~fuji/puzzlestudy/8queen.html) を参考にプログラムを改良してみましょう。
まず、配列 used のチェックですが、配列 board に数字をひとつずつ入れておいて、選んだ数字と未使用の数字を交換していくことで改良することができます。n 列目のクイーンを選ぶ場合、確定済みのクイーンは board の 0 から n - 1 までに格納されていて、残りの n から size - 1 までが未使用のクイーンになります。これで未使用のクイーンを簡単に選ぶことができます。
斜めの利き筋のチェックは、簡単な方法で高速化できます。次の図を見てください。
右斜め上の利き筋 左斜め上の利き筋
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
*-----------------* *-----------------*
|／／／／／／／／ | 8 -1 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 9 -2 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 10 -3 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 11 -4 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 12 -5 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 13 -6 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | 14 -7 |＼＼＼＼＼＼＼＼ |
|／／／／／／／／ | |＼＼＼＼＼＼＼＼ |
*-----------------* *-----------------*
x + y = constant x - y = constant
図 : 斜めの利き筋のチェック
斜めの利き筋は、行と列の位置を足す、または行から列を引くと一定の値になることを利用してチェックしています。attack は確定済みのクイーンと衝突していないかひとつずつチェックしていますが、斜めの利き筋を配列にセットしておけば、もっと簡単にチェックすることができます。
右斜め上の利き筋を配列 rUsed, 左斜め上の利き筋を配列 lUsed で表すことにすると、(x, y) にクイーンを置いた場合は次のようにセットします。
r_used[x + y] = l_used[x - y + n - 1] = true;
n は盤面の大きさ (クイーンの個数) です。バックトラックするときはリセットすることをお忘れなく。プログラムは次のようになります。
リスト : N Queens Problem (2)
#include <stdio.h>
#include <stdbool.h>
#include <time.h>
#define N 20
// 外部変数
int board[N];
bool r_used[N * 2 - 1];
bool l_used[N * 2 - 1];
int count;
// 解法
void queen2(int n, int m)
{
if (n == m)
count++;
else {
for (int i = n; i < m; i++) {
int x = board[i];
// チェック
if (r_used[x + n] || l_used[x - n + m - 1]) continue;
r_used[x + n] = l_used[x - n + m - 1] = true;
board[i] = board[n];
board[n] = x;
// 再帰する
queen2(n + 1, m);
// 元に戻す
r_used[x + n] = l_used[x - n + m - 1] = false;
board[n] = board[i];
board[i] = x;
}
}
}
int main()
{
for (int i = 12; i < 17; i++) {
// データの初期化
for (int j = 0; j < i; j++) board[j] = j;
count = 0;
clock_t s = clock();
queen2(0, i);
printf("%d, %d, %.3f\n", i, count, (double)(clock() - s) / CLOCKS_PER_SEC);
}
return 0;
}
説明をそのままプログラムしただけなので、難しいところはないと思います。説明は割愛しますので、詳細はリストをお読みくださいませ。
実行結果を示します。
表 : 実行結果 (時間 : 秒)
個数 : 12 : 13 : 14 : 15 : 16
-----+-------+-------+-------+---------+--------
解 : 14200 : 73712 :365596 : 2279184 :14772512
(1) : 0.098 : 0.557 : 3.464 : 22.911 : ------
(2) : 0.036 : 0.196 : 1.148 : 7.296 : 49.323
改良の効果は十分に出ていますね。
最後に、ビット演算を使って高速化する方法を紹介します。オリジナルは Jeff Somers さんのプログラムですが、高橋謙一郎さんが再帰を使って書き直したプログラムをＮクイーン問題（解の個数を求める） (http://www.ic-net.or.jp/home/takaken/nt/queen/index.html) で発表されています。今回は高橋さんのプログラムを参考にさせていただきました。高橋さんに感謝します。
プログラムのポイントは二つあります。一つはクイーンの選択処理をビット演算で行うこと、もう一つは斜めの利き筋のチェックをビット演算で行うことです。
クイーンの位置をビットオンで表すことします。つまり、i 行目のクイーンは i ビットを 1 にした値になります。この場合、未選択のクイーンは整数値で表すことができます。8 クイーンの場合、まだ一つもクイーンを選択していない状態は 255 になります。残っているクイーンを表す値を n とすると、次の処理でクイーンを順番に取り出していくことができます。
リスト : クイーンの選択処理
int m = n;
while (m > 0) {
int q = m & (-m);
...
m &= m - 1;
}
while ループの最後で m &= m - 1 とすれば、右端の 1 を 0 にクリアすることができます。そして、ループの中で q = m & (- m) とすれば、右端の 1 を取り出すことができます。n から取り出した q を削除するのも簡単で、排他的論理和 n ^ q を計算するだけです。
次は斜めの利き筋のチェックを説明します。下図を見てください。
0 1 2 3 4
*-------------
| . . . . . .
| . . . -3. . 0x02
| . . -2. . . 0x04
| . -1. . . . 0x08 (1 bit 右シフト)
| Q . . . . . 0x10 (Q の位置は 4)
| . +1. . . . 0x20 (1 bit 左シフト)
| . . +2. . . 0x40
| . . . +3. . 0x80
*-------------
図 : 斜めの利き筋のチェック
上図の場合、1 列目の右斜め上の利き筋は 3 番目 (0x08)、2 列目の右斜め上の利き筋は 2 番目 (0x04) になります。この値は 0 列目のクイーンの位置 0x10 を 1 ビットずつ右シフトすれば求めることができます。また、左斜め上の利き筋の場合、1 列目では 5 番目 (0x20) で 2 列目では 6 番目 (0x40) になるので、今度は 1 ビットずつ左シフトすれば求めることができます。
つまり、右斜め上の利き筋を right、左斜め上の利き筋を left で表すことにすると、right と left にクイーンの位置をセットしたら、隣の列を調べるときに right と left を 1 ビットシフトするだけで、斜めの利き筋を求めることができるわけです。
プログラムは次のようになります。
リスト : N Queens Problem (3)
#include <stdio.h>
#include <time.h>
int count;
void queen3(int n, int right, int left)
{
if (n == 0)
count++;
else {
for (int m = n; m > 0; m &= m - 1) {
int q = m & (-m);
if ((q & (right | left)) == 0)
queen3(n ^ q, (right | q) << 1, (left | q) >> 1);
}
}
}
int main()
{
for (int i = 12; i < 17; i++) {
count = 0;
clock_t s = clock();
queen3((1 << i) - 1, 0, 0);
printf("%d, %d, %.3f\n", i, count, (double)(clock() - s) / CLOCKS_PER_SEC);
}
return 0;
}
関数 queen3 の引数 n が未選択のクイーン、引数 right が右斜め上の利き筋、left が左斜め上の利き筋を表します。(rigth | left) のビットオンの位置が斜めの利き筋にあたります。そして、n から斜めの利き筋にあたらないクイーンを選びます。
queen3 を再帰呼び出しするときは、right と left にクイーンの位置をセットして、それを 1 ビットシフトします。right と left は局所変数なので、元の値に戻す処理は必要ありません。あとは、とくに難しいところはないでしょう。詳細はプログラムリストをお読みください。
実行結果を示します。
表 : 実行結果 (時間 : 秒)
個数 : 12 : 13 : 14 : 15 : 16
-----+-------+-------+-------+---------+--------
解 : 14200 : 73712 :365596 : 2279184 :14772512
(1) : 0.098 : 0.557 : 3.464 : 22.911 : ------
(2) : 0.036 : 0.196 : 1.148 : 7.296 : 49.323
(3) : 0.019 : 0.102 : 0.583 : 3.671 : 24.577
ビット演算の効果はきわめて大きいですね。ここまで速くなるとは M.Hiroi も大変驚きました。