C#でチェスのナイトが目的地に到達するまでの最小ステップ数を求める方法

本記事では、チェスのナイト（騎士）が盤上のすべてのマスを訪れ、かつ同じマスは一度しか通れないという条件で移動する「ナイト・ツアー」の考え方と、始点から目的地までの最小ステップ数をC#で求める方法について解説します。

ナイト・ツアーの種類

ナイトの移動には、完了時の形によって2つのタイプがあります。

• 閉路ツアー（Closed Tour）：最後にスタート地点からナイトの1手で戻れる位置に到達し、閉じたループを形成するツアー。
• 開放ツアー（Open Tour）：スタート地点に戻らず、盤上の任意の場所で終了するツアー。

有効な移動とは、移動先が盤面の内側にあり、かつそのマスがまだ訪問されていないことを指します。実装では、未訪問のセルをすべて -1 で初期化し、訪問済みかどうかを管理します。

最小ステップ数を求めるアルゴリズム

始点から目的地までの最短手数を求める場合、幅優先探索（BFS）を利用するのが定石です。BFSは近いマスから順に探索を広げていくため、目的地に最初に到達した時点での手数が必ず最小となります。以下のサンプルコードでは、30×30の盤面上でナイトが座標 (1, 1) から (30, 30) へ移動するケースを扱っています。

処理の流れ

1. 始点の座標と距離0をキューに追加します。
2. キューからセルを取り出し、目的地であればその時点の距離を返します。
3. ナイトが移動できる8方向（dx・dy の組み合わせ）について、盤内かつ未訪問のセルだけをキューに追加します。
4. これを繰り返し、目的地に到達した時点の手数を出力します。

C#による実装例

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace ConsoleApplication{
    public class KnightWalkProblem{
        public class cell{
            public int x, y;
            public int dis;
            public cell(int x, int y, int dis){
                this.x = x;
                this.y = y;
                this.dis = dis;
            }
        }
        static bool isInside(int x, int y, int N){
            if (x >= 1 && x <= N && y >= 1 && y <= N)
                return true;
            return false;
        }
        public int minStepToReachTarget(int[] knightPos, int[] targetPos, int N){
            int[] dx = { -2, -1, 1, 2, -2, -1, 1, 2 };
            int[] dy = { -1, -2, -2, -1, 1, 2, 2, 1 };
            Queue<cell> q = new Queue<cell>();
            q.Enqueue(new cell(knightPos[0], knightPos[1], 0));
            cell t;
            int x, y;
            bool[] visit = new bool[N + 1, N + 1];
            for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                visit[i, j] = false;
            visit[knightPos[0], knightPos[1]] = true;
            while (q.Count != 0){
                t = q.Peek();
                q.Dequeue();
                if (t.x == targetPos[0] && t.y == targetPos[1])
                    return t.dis;
                for (int i = 0; i < 8; i++){
                    x = t.x + dx[i];
                    y = t.y + dy[i];
                    if (isInside(x, y, N) && !visit[x, y]){
                        visit[x, y] = true;
                        q.Enqueue(new cell(x, y, t.dis + 1));
                    }
                }
            }
            return int.MaxValue;
        }
    }
    class Program{
        static void Main(string[] args){
            KnightWalkProblem kn = new KnightWalkProblem();
            int N = 30;
            int[] knightPos = { 1, 1 };
            int[] targetPos = { 30, 30 };
            Console.WriteLine(
                kn.minStepToReachTarget(
                    knightPos,
                    targetPos, N));
        }
    }
}

出力結果

20

このコードを実行すると「20」と出力されます。これは、30×30の盤面上でナイトが左上の (1, 1) から右下の (30, 30) に到達するために必要な最小手数を表しています。計算量は盤面のマス数に対して線形であり、BFSにより常に最短経路が保証されるのが大きな特徴です。