【C言語】ナイト巡回問題（ナイトツアー）のバックラック法での解き方

このページにはプロモーションが含まれています

このページではチェスを利用したパズル「ナイト巡回問題（ナイトツアー）」をバックトラック法で解く方法およびそのプログラムの紹介を行っていきます。

同様にチェスを利用したパズルに「エイトクイーン問題」がありますが、プログラミングの難易度としては、このページで紹介する「ナイト巡回問題」の方が簡単だと思います。

アルゴリズムの授業や情報技術者試験等でも頻繁に出題される問題ですので、是非このページで理解して行ってください！

同様にチェスを利用したパズルである「エイトクイーン問題」については下記ページで解説していますので、こちらも是非併せてお読みください。バックトラック法の解説も行なっています。

【C言語】エイトクイーン問題（Nクイーン問題）のバックラック法での解き方

Contents

ナイト巡回問題
- ナイト巡回問題とは
- ナイト周遊問題とは
ナイト巡回問題の解き方
- 総当たりで調べる
- バックトラック法を用いる
ナイト巡回問題を解くプログラム
- プログラム
- プログラムの説明
ナイト周遊問題を解くプログラム
- プログラム
- プログラムの解説
ナイト巡回問題の解の数
まとめ

ナイト巡回問題

まずはナイト巡回問題がどのようなものであるかを解説していきます。同様の問題としてナイト周遊問題もありますので、こちらの解説も行います。

ナイト巡回問題とは

ナイト巡回問題とは「チェス盤上のナイトを巡回（移動）させて、全マスを１回ずつ巡回させるパズル」になります。

チェスにおけるナイトは、下図のように８つの箇所に巡回することができる駒になります。

この巡回可能箇所を辿りながら、チェス盤上の全マスを１回ずつ巡回させます。ナイトを同じマスに２回以上巡回させるのは NG です。

例えば５×５のチェス盤において、下図は１つのナイト巡回問題の解となります（左側は何回目にナイトが移動してきたかを数字で表し、右側はナイトの移動履歴を矢印で表したもの）。

ナイト周遊問題とは

ナイト周遊問題とは、ナイト巡回問題に「巡回が完了したナイトの位置から最初に置いたナイトの位置に移動可能であること」というルールを追加したパズルになります。

例えばナイト巡回問題とはで示した解はナイト巡回問題の解ではありますが、ナイト周遊問題の解ではありません。これは最後に移動したナイトの位置から最初に置いたナイトに移動することができないためです。

一方で下の図は、１０×３のチェス盤におけるナイト周遊問題の解です。

オレンジ色で示したナイトの最後の位置から、青色のナイトの最初の位置に移動することができるので、ナイト巡回問題の解であると同時にナイト周遊問題の解でもあります。

ナイト周遊問題はナイト巡回問題とほぼ同じ解き方で解くことができます（最後のナイトの位置から最初のナイトの位置に移動できるかどうかを判断する必要があるかどうかくらいの違い）。

ですので、このページでは基本的なナイト巡回問題に関して解説を行なっていきます。プログラムに関してはナイト周遊問題のものも紹介しようと思います。

ナイト巡回問題の解き方

続いてここまで説明してきたナイト巡回問題を解く方法について解説していきたいと思います。

総当たりで調べる

一つ目の方法はナイトの巡回パターン全てを総当たりで調べる方法です。

とりあえず同じマスに重複しようがしまいが関係なく、マス数分ナイトを巡回させます。

さらにマス数分の巡回が終了した時に、全マスを巡回できているかどうかを確認します。全マス巡回できていたら、それはナイト巡回問題の解となります。

そしてこれを全パターンに対して繰り返し行うことで、ナイト巡回問題の回を全て導くことができます。

ただし、ナイトの巡回パターン数が非常に多いので、全パターンの解を導く出すのに必要な処理時間も非常に長くなってしまいます。

バックトラック法を用いる

このパターン数を削減するために、バックトラック法を用いるのが有効です。

バックトラック法とは「手を進めるだけで進め、途中で解になり得ないと分かったら一手戻して別の手を試す」手法になります。

根底の考え方は総当たりで調べるのと同じです。

ですがナイト巡回問題におけるバックトラック法では、同じマスに重複して巡回することが分かった時点でナイトを一手戻し、違う場所にナイトを巡回させるようにします。

これにより、ナイトが同じマスに重複して巡回する場合のパターンを省いて解を導き出すことができます。つまり調べる必要のあるパターン数を大幅に削減することができます。

実例を見てみましょう。

５×５のチェス盤におけるナイトの初期位置を一番左上とすると、このナイトは下の図の青枠のマスに巡回可能です。

ナイト巡回問題を解くためには、この青枠の各マスにナイトを巡回させたパターンを調べて行く必要があります。まずは試しに上側のマスに移動してみましょう。

今度はナイトはピンク枠のマスに巡回可能です。

ここでナイトをチェス盤上の左上に巡回させることを考えてみましょう。

このマスは既にナイトが巡回済みのマスになります。ですので、このマスに再度巡回させ、その後の巡回パターンを調べたとしても絶対にナイト巡回問題の解にはなり得ません。調べるだけ無駄です。

ですので、ナイト巡回を一手分戻します。

そして、一手戻したナイトの位置から巡回可能な他のマスに巡回させるようにします。

この「途中で解になり得ないと分かったら一手戻して別の手を試す」というところがバックトラック法の特徴になります。

途中で解になり得ないと分かったら、その手を含んだパターンを調べる事を注視しますので、その分調べるパターン数を削減することができます。

ナイト巡回問題をバックトラック法で解く手順は下記のようになります。

あるマスへのナイトの巡回を試みる（★）
ナイトがそのマスへ巡回可能であるかを判断
1. チェス盤の外に出ないかを判断
2. 既にそのマスが巡回済みでないかを判断
巡回可能の場合
1. 1. そのマスにナイトを移動
  2. 全マス巡回済みかどうかを判断
  3. 全マス巡回済みの場合
    1. そこまでの巡回ルートを解として表示（☆）
    2. １手戻す（直前に移動させたナイトを元のマスに戻す）
    3. ★に戻って別のマスへの巡回を試みる
  4. 全マス巡回済みでない場合
    1. ★に戻って別のマスへの巡回を試みる
巡回不可の場合
1. ★に戻って別のマスへの巡回を試みる

ナイト巡回問題の解を一つだけ導出するのであれば、☆時点でプログラムを終了してやれば良いです。

ナイト巡回問題を解くプログラム

それではここまで説明してきたナイト巡回問題をどのようにプログラミングすれば良いかを解説していきたいと思います。

プログラム

ナイト巡回問題をバックトラック法で解くプログラムは下記のようになります。

ナイト巡回問題（バックトラック法）

#include <stdio.h>
#include <time.h>

/* チェスの盤の縦横サイズ */
#define WIDTH 5
#define HEIGHT 5

/* チェス盤を表す２次元配列 */
int board[HEIGHT][WIDTH];

/* 解の数 */
int resolve = 0;

/**
 * チェス盤の表示
 * width：横方向のマス数
 * height：縦方向のマス数
 */
void printKnight(int width, int height)
{
    int i, j;

    printf("%d個目の解\n", resolve);

    /* 全マスを表示 */
    for (j = 0; j < height; j++)
    {
        for (i = 0; i < width; i++)
        {
            printf("%2d ", board[j][i]);
        }
        printf("\n");
    }
    printf("\n\n");
}

/**
 * チェス盤の初期化
 * width：横方向のマス数
 * height：縦方向のマス数
 */
void initKnight(int width, int height)
{
    int i, j;
    for (j = 0; j < height; j++)
    {
        for (i = 0; i < width; i++)
        {
            /* マスを空にする */
            board[j][i] = 0;
        }
    }
}

/**
 * ナイトを巡回させる
 * num_knight：ナイトが巡回したマス数
 * width：チェス盤横方向のマス数
 * height：チェス盤縦方向のマス数
 * i, j：ナイトを巡回させるマス
 */
void KnightTour(int num_knight, int width, int height, int i, int j)
{

    if (i >= width || i < 0)
    {
        /* チェス盤外に出る場合ナイトは巡回させない */
        return;
    }

    if (j >= height || j < 0)
    {
        /* チェス盤外に出る場合ナイトは巡回させない */
        return;
    }

    if (board[j][i] != 0)
    {
        /* 既にその場所をナイトが巡回済みであれば巡回させない */
        return;
    }

    /* (i, j)にナイトがnum_knight+1手目に巡回したことを記録 */
    board[j][i] = num_knight + 1;

    /* ナイトの巡回マス数を増加 */
    num_knight++;

    if (width * height == num_knight)
    {
        /* 全マス巡回ずみの場合 */

        /* 解の数をインクリメント */
        resolve++;

        /* チェス盤を表示 */
        printKnight(width, height);

        /* ナイト巡回を１手戻す */
        board[j][i] = 0;
        return;
    }

    /* ナイトが移動可能なマスに移動させてみる */
    KnightTour(num_knight, width, height, i - 1, j - 2);
    KnightTour(num_knight, width, height, i - 1, j + 2);
    KnightTour(num_knight, width, height, i + 1, j - 2);
    KnightTour(num_knight, width, height, i + 1, j + 2);
    KnightTour(num_knight, width, height, i - 2, j - 1);
    KnightTour(num_knight, width, height, i - 2, j + 1);
    KnightTour(num_knight, width, height, i + 2, j - 1);
    KnightTour(num_knight, width, height, i + 2, j + 1);

    /* ナイト巡回を１手戻す */
    board[j][i] = 0;

    return;
}

int main(void)
{
    clock_t start, end;
    int i, j;

    /* チェス盤の初期化 */
    initKnight(WIDTH, HEIGHT);

    start = clock();

    for (j = 0; j < HEIGHT; j++)
    {
        for (i = 0; i < WIDTH; i++)
        {

            /* (i,j)を開始点としてナイト巡回問題を解く */
            KnightTour(0, WIDTH, HEIGHT, i, j);
        }
    }

    end = clock();

    /* 処理時間を表示 */
    printf("time = %f[s]", (double)(end - start) / CLOCKS_PER_SEC);
}

実行すると、下記のようにナイト巡回問題の解が表示されていきます。

1728個目の解
23 14 19  8 21 
 6  9 22 13 18 
15 24  7 20  3 
10  5  2 17 12 
25 16 11  4  1

またプログラム終了時にはナイト巡回問題の全ての解を導出するのに要した処理時間が表示されます。私の PC だと約２秒でした。

time = 2.546720[s]

プログラムの説明

プログラムについて簡単に解説しておきます。

チェス盤のサイズ

チェス盤の縦横サイズは下記で定数 WIDTH・HEIGHT を定義しています。これを変更することで様々なサイズのチェス盤におけるナイト巡回問題を解くことができます。

チェス盤のサイズ

/* チェスの盤の縦横サイズ */
#define WIDTH 5
#define HEIGHT 5

ナイト巡回情報の管理

ナイトがどこを巡回したかを二次元配列 board により管理しています。

ナイト巡回ルート管理用の配列

/* チェス盤を表す２次元配列 */
int board[HEIGHT][WIDTH];

そのマスに何回目の巡回時に通過したかの数字を格納するようにしています。

ナイトの巡回

ナイトの巡回は KnightTour 関数で行っています。

KnightTour 関数では、引数でナイトを巡回させるマスの位置（i, j）を指定し、このマスに対して下記を行っています。

まずナイトがそのマスの位置に巡回できるかどうかを判断します。具体的に「チェス盤からはみ出ないかどうか」「そのマスが巡回済みでないかどうか」を判断します。

巡回できない場合は、そのマスにはナイトを巡回させずにその時点で関数終了を終了します（一手戻す）。

巡回できるかどうかの判断

if (i >= width || i < 0)
{
    /* チェス盤外に出る場合ナイトは巡回させない */
    return;
}

if (j >= height || j < 0)
{
    /* チェス盤外に出る場合ナイトは巡回させない */
    return;
}

if (board[j][i] != 0)
{
    /* 既にその場所をナイトが巡回済みであれば巡回させない */
    return;
}

ちなみに最後の board[j][i] != 0 の比較を行わない場合は総当たりで全パターンを確認することになります。つまり、ここがバックトラック法と総当たり法の違いです。

巡回できる場合は、実際にそのマスにナイトを巡回させます。具体的には board[j][i] に何回目の巡回でそのマスに訪れたかの数値を格納します。

さらにナイトが巡回した回数をインクリメントします。

ナイトの巡回

/* (i, j)にナイトがnum_knight+1手目に巡回したことを記録 */
board[j][i] = num_knight + 1;

/* ナイトの巡回マス数を増加 */
num_knight++;

ナイトを巡回した時、ナイトの巡回数がチェス盤のマス数に一致した場合、ナイトが全マスを巡回したことになるので、その情報を表示します（printKnight 関数を実行）。

さらに他のパターンを試すために、ナイト巡回を一手戻して関数を終了します。

ナイト巡回終了時の処理

if (width * height == num_knight)
{
    /* 全マス巡回ずみの場合 */

    /* 解の数をインクリメント */
    resolve++;

    /* チェス盤を表示 */
    printKnight(width, height);

    /* ナイト巡回を１手戻す */
    board[j][i] = 0;
    return;
}

まだナイトの巡回が終了していない場合は、ナイトが巡回可能な８方向に対して再帰的に KnightTour 関数を実行します。

再帰的に KnightTour 関数を実行することで、どんどんナイトを巡回させていくイメージです。

新たなマスへのナイトの巡回

/* ナイトが移動可能なマスに移動させてみる */
KnightTour(num_knight, width, height, i - 1, j - 2);
KnightTour(num_knight, width, height, i - 1, j + 2);
KnightTour(num_knight, width, height, i + 1, j - 2);
KnightTour(num_knight, width, height, i + 1, j + 2);
KnightTour(num_knight, width, height, i - 2, j - 1);
KnightTour(num_knight, width, height, i - 2, j + 1);
KnightTour(num_knight, width, height, i + 2, j - 1);
KnightTour(num_knight, width, height, i + 2, j + 1);

８方向に対する KnightTour 関数の実行が完了すれば、次の新たな巡回パターンを試すために、ナイト巡回を一手戻して関数を終了します。

ナイト巡回を一手戻す処理

/* ナイト巡回を１手戻す */
board[j][i] = 0;

return;

ナイト周遊問題を解くプログラム

最後にナイト周遊問題を解くプログラムも紹介しておきます。

ナイト周遊問題とは、ナイト周遊問題とはで解説したように、ナイト巡回問題に「巡回が完了したナイトの位置から最初に置いたナイトの位置に移動可能であること」というルールを追加したパズルです。

ですので、ナイト巡回問題を解き終わった時に、最後に巡回したナイトの位置からナイトの最初の位置に移動できるかどうかをチェックする処理が必要になります。

プログラム

ナイト巡回問題を解くプログラムとの違いは KnightTour 関数のみですので KnightTour 関数のみを紹介します。

ナイト周遊問題をバックトラック法で解く際に使用する KnightTour 関数は下記のようになります。

ナイト周遊問題（バックトラック法）

/**
 * ナイトを巡回させる
 * num_knight：ナイトが巡回したマス数
 * width：チェス盤横方向のマス数
 * height：チェス盤縦方向のマス数
 * i, j：ナイトを巡回させるマス
 */
void KnightTour(int num_knight, int width, int height, int i, int j)
{

    if (width * height == num_knight)
    {
        /* 全マス巡回ずみの場合 */

        if (i >= width || i < 0) {
            /* チェス盤外に出る場合は周遊できてない*/
            return;
        }

        if (j >= height || j < 0) {
            /* チェス盤外に出る場合は周遊できてない */
            return;
        }

        if (board[j][i] == 1) {
            /* 周遊を満たしている場合 */

            /* 解の数をインクリメント */
            resolve++;

            /* チェス盤を表示 */
            printKnight(width, height);
        }

        return;
    }

    if (i >= width || i < 0) {
        /* チェス盤外に出る場合ナイトは巡回させない */
        return;
    }

    if (j >= height || j < 0) {
        /* チェス盤外に出る場合ナイトは巡回させない */
        return;
    }

    if (board[j][i] != 0) {
        /* 既にその場所をナイトが巡回済みであれば巡回させない */
        return;
    }

    /* (i, j)にナイトがnum_knight+1手目に巡回したことを記録 */
    board[j][i] = num_knight + 1;

    /* ナイトの巡回マス数を増加 */
    num_knight++;

    /* ナイトが移動可能なマスに移動させてみる */
    KnightTour(num_knight, width, height, i - 1, j - 2);
    KnightTour(num_knight, width, height, i - 1, j + 2);
    KnightTour(num_knight, width, height, i + 1, j - 2);
    KnightTour(num_knight, width, height, i + 1, j + 2);
    KnightTour(num_knight, width, height, i - 2, j - 1);
    KnightTour(num_knight, width, height, i - 2, j + 1);
    KnightTour(num_knight, width, height, i + 2, j - 1);
    KnightTour(num_knight, width, height, i + 2, j + 1);
    
    /* ナイト巡回を１手戻す */
    board[j][i] = 0;

    return;
}

プログラムの解説

次にプログラムの解説を行なっていきます。

ナイトの巡回

ナイトの巡回は KnightTour 関数で行っており、ナイト巡回問題の時に示した KnightTour 関数を比較すると、ほとんど同じであることを確認していただけると思います。

ただしナイト巡回問題の時とは異なり、ナイトを巡回させる前に、ナイトの巡回が完了したかどうかの判断を行っています。

巡回終了したかどうかの判断

if (width * height == num_knight)
{
    /* 全マス巡回ずみの場合 */

    /* 〜略〜 */

}

/* 〜略〜 */

/* (i, j)にナイトがnum_knight+1手目に巡回したことを記録 */
board[j][i] = num_knight + 1;

/* ナイトの巡回マス数を増加 */
num_knight++;

これにより、ナイトが巡回し終わってから更に＋１回 KnightTour 関数が実行されることになります。

この時に、ナイトが巡回できるかどうかではなく、ナイト周遊を満たしているかどうか（つまりナイトが最初の位置に移動できるかどうか）を判断しています。

周遊を満たしているかどうかの判断

if (board[j][i] == 1) {
    /* 周遊を満たしている場合 */

    /* 解の数をインクリメント */
    resolve++;

    /* チェス盤を表示 */
    printKnight(width, height);
}

具体的には上記のように board[j][i] == 1 を満たすかどうかを判断します（ナイトの初期位置にはナイトが１番目に巡回しているので “1” が格納されている）。

そして、これを満たすときのみチェス盤の情報を表示してやれば、ナイト周遊問題の解のみを表示することができるようになります。

ナイト巡回問題の解の数

チェス盤のサイズ毎のナイト巡回問題の解の数は下記のようなページで確認することができますので、実際に出来上がったプログラムの動作確認をする際に参考にしてください。

参考ナイトツアーニコニコ大百科参考 Knight's tourWikipedia（英語）

まとめ

このページではナイト巡回問題（ナイト周遊問題）について説明を行い、この問題の解き方を解説しました。

チェスを利用したパズルのですので、楽しみながらプログラミングできるところがこの問題の良いところだと思います！

また再帰処理を理解する上でも非常に役立つ問題だと思います。今回紹介したプログラムはナイト巡回問題を解くための１例ですので、他の方法で自力でプログラミングしてみることにも是非挑戦してみていただきたいです。

プログラミングした感じだと、個人的にはエイトクイーン問題よりも、このナイト巡回問題の方が簡単だと感じました。

エイトクイーン問題で挫折した人にも、まずバックトラック法を理解するためにこのナイト巡回問題に挑戦してみるのは良いと思います！

おまけですが、下記ページでは Python でナイト巡回問題が解かれていく様子の可視化を行っています。

ナイト巡回が一手進む・一手戻る様子がアニメーション的に確認することができます。興味のある方は是非こちらも読んでみてください。

【Python】ナイト巡回問題を解く様子を Tkinter で可視化

同じカテゴリのページ一覧を表示