巡回騎士問題：分散並列計算の題材として

現在、予定していたラズパイによるクラスター型マシンの製作に取りかかっています。
この並列マシンが動作したとき、どのような応用や計算実験が可能か、さまざまに検討してきました。
その結果、「巡回騎士問題（Knight's Tour）」を題材として選ぶことにしました。

巡回騎士問題とは？

これは古典的な組合せ探索問題で、チェスのナイト（桂馬）の動きを用いて、盤面上のすべてのマスを一度ずつ訪れる経路を探索するというものです。

この問題には以下の2つのバリエーションがあります：

巡回（open tour）：全マスを一度ずつ訪れる経路を探す。
周遊（closed tour）：上記に加えて、最後のマスから最初のマスにもう一度ナイトで戻れるようにする。

今回は、比較的扱いやすい巡回（open）のほうを対象にします。

コード

以下は、5×5 の盤面上で巡回騎士問題を解く N-Prolog のコードです。
スタート地点を与えると、もし解が見つかればその経路を表示して yes を返します。解がなければ no です。

% Knight tour
% 5*5


% tour start from (R,C), X is path
tour(R,C,X) :-
    move(R,C,[[R,C]],X).

safe(R,C) :- 
    R >= 1,R =< 5,
    C >= 1,C =< 5.

move(R,C,P,P) :-
    length(P,25).


move(R,C,P,A) :-
    R1 is R+2,
    C1 is C+1,
    safe(R1,C1),
    not(member([R1,C1],P)),
    move(R1,C1,[[R1,C1]|P],A).

move(R,C,P,A) :-
    R1 is R+1,
    C1 is C+2,
    safe(R1,C1),
    not(member([R1,C1],P)),
    move(R1,C1,[[R1,C1]|P],A).

move(R,C,P,A) :-
    R1 is R-2,
    C1 is C-1,
    safe(R1,C1),
    not(member([R1,C1],P)),
    move(R1,C1,[[R1,C1]|P],A).

move(R,C,P,A) :-
    R1 is R-1,
    C1 is C-2,
    safe(R1,C1),
    not(member([R1,C1],P)),
    move(R1,C1,[[R1,C1]|P],A).

move(R,C,P,A) :-
    R1 is R+2,
    C1 is C-1,
    safe(R1,C1),
    not(member([R1,C1],P)),
    move(R1,C1,[[R1,C1]|P],A).

move(R,C,P,A) :-
    R1 is R+1,
    C1 is C-2,
    safe(R1,C1),
    not(member([R1,C1],P)),
    move(R1,C1,[[R1,C1]|P],A).

move(R,C,P,A) :-
    R1 is R-2,
    C1 is C+1,
    safe(R1,C1),
    not(member([R1,C1],P)),
    move(R1,C1,[[R1,C1]|P],A).

move(R,C,P,A) :-
    R1 is R-1,
    C1 is C+2,
    safe(R1,C1),
    not(member([R1,C1],P)),
    move(R1,C1,[[R1,C1]|P],A).

実行時間の観察

N-Prolog インタプリタで動作させたところ、次のような傾向が得られました：

5×5盤面の場合、ナイトツアーが可能なのは4隅のスタート地点のみであることが知られています。

そのため、正しいスタート地点を与えれば数秒以内に解が得られます。

しかし、解が存在しないスタート地点では、1分〜数分かかる場合もありました。

なぜ並列に向いているのか？

この問題には以下の特徴があります：

ヒューリスティック（Warnsdorffの法則など）を使えば高速化可能ですが、今回はあえてそれを使いません。
数学的に完全に一般解を導けるような定理もなく、CLP（制約論理プログラミング）もあまり役に立ちません。
結果として、純粋なバックトラック探索に頼るしかない。

こうなると、探索の分岐を各プロセスに割り当てる並列化が非常に効果を発揮します。
探索木の上位ノードで枝を分け、それぞれを異なるプロセスで試す構成が自然です。
N-Prolog や Easy-ISLisp との親和性も高く、分散並列の題材として非常に適しています。

今後の展望

ラズパイクラスタの構成台数にもよりますが、5×5 盤面くらいであれば十分に扱えるでしょう。
まずはこの問題で動作確認と性能測定を行い、将来的には 6×6 や 8×8 といったより大きな盤面への挑戦、さらには CLP やヒューリスティックを導入した高度化も視野に入れています。