Pythonでチェスのナイトが目標位置に到達するまでの最小手数を求めるプログラム

問題の概要

2つの値 r と c が与えられているとします。無限に広いチェス盤上で、ナイト(騎士)が最初に座標 (0, 0) に配置されているとき、そのナイトが位置 (r, c) に到達するまでに必要な最小の移動回数を求めます。

ナイトの動きは通常のチェスと同じで、「横に2マス・縦に1マス」または「縦に2マス・横に1マス」という移動を行います。

例えば、入力が r = 6、c = 1 の場合、出力は 3 となります。下図では、赤が初期位置、緑が最終位置、黄色が途中の経由地点を表しています。

解法のアプローチ

この問題は、ナイトの移動パターンを数学的に分析することで、幅優先探索(BFS)のような反復処理を使わずに、定数時間 O(1) で答えを導けます。解法の手順は以下の通りです。

• ステップ1: もし r < c ならば、r と c を入れ替えます(盤面の対称性を利用)。
• ステップ2: (r, c) が (1, 0) と一致する場合は 3 を返します(例外的なケース)。
• ステップ3: (r, c) が (2, 2) と一致する場合は 4 を返します(例外的なケース)。
• ステップ4: delta := r − c を計算します。
• ステップ5: c > delta の場合、delta − 2 × ((delta − c) ÷ 3 の商) を返します。
• ステップ6: それ以外の場合、delta − 2 × ((delta − c) ÷ 4 の商) を返します。

実装例(Python)

以下のコードで、実際の実装を確認できます。

class Solution:
    def solve(self, r, c):
        if r < c:
            r, c = c, r
        if (r, c) == (1, 0):
            return 3
        if (r, c) == (2, 2):
            return 4
        delta = r - c
        if c > delta:
            return delta - 2 * ((delta - c) // 3)
        else:
            return delta - 2 * ((delta - c) // 4)
ob = Solution()
r = 6
c = 1
print(ob.solve(r, c))

入力

6, 1

出力

3

まとめ

このアルゴリズムのポイントは、ナイトの移動が持つ対称性と数学的な性質を活かしている点です。まず r と c を並べ替えて一般形に帰着させ、(1, 0) と (2, 2) という例外的なケースだけを個別に処理すれば、残りはすべて統一された公式で計算できます。これにより、盤面を実際に探索することなく、最小手数を高速に求めることが可能になります。