ナイトツアー問題（騎士の周遊）とは？バックトラッキングによる解法とC++実装を解説

ナイトツアー問題とは

チェスにおいて、ナイト（騎士）は特殊な動き方をする駒として知られています。ナイトは「横に2マス・縦に1マス」あるいは「縦に2マス・横に1マス」という移動がどの方向にも可能で、その軌跡は英語の字母「L」字のような形になります。

この問題では、空のチェス盤を用意し、盤上の任意のマスから出発したナイトが、盤上のすべてのマスを訪問できるかどうかを判定します。すべてのマスを訪問できる場合、各マスに出発点からそのマスに到達するまでの手数（ジャンプ回数）を記入していきます。

この問題には複数の解が存在しえますが、ここでは1つの有効な解を見つけることを目標とします。このような組合せ最適化問題は、バックトラッキング（探索の巻き戻し）を使うことで効率的に解くことができます。

入力と出力

Input:
チェス盤のサイズ。通常は 8（8 x 8 が一般的なチェス盤のサイズです）

Output:
ナイトの移動経路。各セルに入っている数字は、何手目にそのマスへ到達したかを示します。

   0  59  38  33  30  17   8  63
  37  34  31  60   9  62  29  16
  58   1  36  39  32  27  18   7
  35  48  41  26  61  10  15  28
  42  57   2  49  40  23   6  19
  47  50  45  54  25  20  11  14
  56  43  52   3  22  13  24   5
  51  46  55  44  53   4  21  12

アルゴリズム

isValid(x, y, solution)

入力： 座標 x と y、および解を格納する行列。

出力： 座標 (x, y) が盤面内にあり、まだ未割り当てであるかどうかを判定します。

Begin
    if 0 ≤ x ≤ 盤面サイズ かつ 0 ≤ y ≤ 盤面サイズ、かつ (x, y) が未訪問ならば
        return true
End

knightTour(x, y, move, sol, xMove, yMove)

入力： 現在の座標 (x, y)、手数、解行列、および x・y 方向の可能な移動量リスト。

出力： 解が存在すれば更新された解行列。

Begin
    if move = 盤面サイズ × 盤面サイズ ならば // すべてのマスを訪問済みの場合
        return true
    for k := 0 to 可能な移動数 - 1, do
        xNext := x + xMove[k]
        yNext := y + yMove[k]
        if isValid(xNext, yNext, sol) = true ならば
            sol[xNext, yNext] := move
            if knightTour(xNext, yNext, move+1, sol, xMove, yMove) ならば
                return true
            else
                バックトラッキングのため sol[xNext, yNext] から手数を削除する
    done
    return false
End

C++による実装例

#include <iostream>
#include <iomanip>
#define N 8

using namespace std;
int sol[N][N];

bool isValid(int x, int y, int sol[N][N]) {    //盤面内かつ未訪問のマスかどうかをチェック
    return ( x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}

void displaySolution() {
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++)
            cout << setw(3) << sol[x][y] << " ";
        cout << endl;
    }
}

int knightTour(int x, int y, int move, int sol[N][N], int xMove[N], int yMove[N]) {
    int xNext, yNext;
    if (move == N*N)     //盤面全体をカバーし終えたとき
        return true;

    for (int k = 0; k < 8; k++) {
        xNext = x + xMove[k];
        yNext = y + yMove[k];
        if (isValid(xNext, yNext, sol)) {    //そのマスが未訪問かどうかを確認
            sol[xNext][yNext] = move;
            if (knightTour(xNext, yNext, move+1, sol, xMove, yMove) == true)
                return true;
            else
                sol[xNext][yNext] = -1;// バックトラッキング
        }
    }
    return false;
}

bool findKnightTourSol() {
    for (int x = 0; x < N; x++)    //解行列の全値を初期値 -1 に設定
        for (int y = 0; y < N; y++)
            sol[x][y] = -1;
    //ナイトが可能なすべての移動
    int xMove[8] = {  2, 1, -1, -2, -2, -1,  1,  2 };
    int yMove[8] = {  1, 2,  2,  1, -1, -2, -2, -1 };
    sol[0][0]  = 0;     //(0, 0) のマスから開始

    if (knightTour(0, 0, 1, sol, xMove, yMove) == false) {
        cout << "Solution does not exist";
        return false;
    } else
        displaySolution();
    return true;
}

int main() {
    findKnightTourSol();
}

実行結果

  0  59  38  33  30  17   8  63
 37  34  31  60   9  62  29  16
 58   1  36  39  32  27  18   7
 35  48  41  26  61  10  15  28
 42  57   2  49  40  23   6  19
 47  50  45  54  25  20  11  14
 56  43  52   3  22  13  24   5
 51  46  55  44  53   4  21  12

まとめ

ナイトツアー問題は、ナイトの「L字型」の移動ルールを活かして盤上の全マスをちょうど1回ずつ訪問する経路を求める古典的なパズルです。今回紹介したように、再帰とバックトラッキングを組み合わせることで、有効な解を系統的に探索できます。8×8の標準的なチェス盤では解が存在することが知られており、上記のプログラムを実行すると、実際に64マスすべてを訪問する手順が数字付きの行列として出力されます。