Pythonでチェスのナイトが盤内に留まり続ける確率を求めるプログラム

n、x、y、k の4つの値が与えられたとします。n は n×n のチェス盤のサイズ、(x, y) はナイトが置かれている初期座標、k はナイトが正確に動く手数を表します。ナイトは各手ごとに、8方向のいずれかへ等しい確率でランダムに移動します。求めたいのは、k 手動いた後もナイトがチェス盤の中に留まっている確率（最も近い整数に丸めたパーセント値）です。ただし、一度でも盤の外に出てしまうと、その後は二度と盤に戻れないという条件があります。

例えば、入力が n = 8、(x, y) = (1, 1)、k = 1 の場合を考えてみましょう。8×8 のチェス盤の (1, 1) に置かれたナイトが、ちょうど1手だけ動きます。8通りの移動先のうち、盤内に収まるのは4箇所だけで、残りの4箇所は盤外に出てしまいます。したがって、答えは 50% となります。

解き方のアプローチ

この問題は、深さ優先探索（DFS）を用いて解くことができます。手順は次の通りです。

• ナイトの8通りの移動パターン [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)] をリストとして定義します。
• x、y、k を引数に取る関数 dfs() を定義します。
• (x, y) が盤の範囲外にある場合は 0 を返します（盤外に出た時点で失敗）。
• k が 0 の場合は 1 を返します（すべての手を盤内で完走できた成功ケース）。
• それ以外の場合は、8つの移動先それぞれについて dfs(x + dx, y + dy, k - 1) / 8 を計算し、その合計を返します。各移動を選ぶ確率は 1/8 だからです。
• メイン処理では dfs(x, y, k) × 100 を計算し、結果を最も近い整数に丸めて返します。

それでは、実際の実装を見ていきましょう。

Pythonでの実装例

moves = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]

class Solution:
   def solve(self, n, x, y, k):
      def dfs(x, y, k):
         if x < 0 or y < 0 or x >= n or y >= n:
            return 0
         if k == 0:
            return 1
         return sum(dfs(x + dx, y + dy, k - 1) / 8 for dx, dy in moves)
      return round(dfs(x, y, k) * 100)

ob = Solution()
n = 8
x = 1
y = 1
k = 1
print(ob.solve(n, x, y, k))

入力

n = 8, x = 1, y = 1, k = 1

出力

50

出力は 50 となります。(1, 1) から1手で到達できる8箇所のうち、(2, 3)、(0, 3)、(3, 2)、(3, 0) の4箇所が盤内に含まれるため、4 ÷ 8 = 50% となるわけです。

計算量の注意点と高速化

上記の素朴なDFS実装では、1手ごとに8通りの分岐が生じるため、計算量は O(8^k) となり、k が大きくなると実行時間が爆発的に増加します。実用的な規模の入力に対応するには、同じ (x, y, k) の組の結果をキャッシュするメモ化、あるいは動的計画法を用いるのが効果的です。これにより、計算量を O(n² × k) 程度まで抑えることができます。

Pythonであれば functools.lru_cache を使うことで、最小限の変更でメモ化を実現できます。

from functools import lru_cache

class Solution:
   def solve(self, n, x, y, k):
      moves = [(1, 2), (1, -2), (-1, 2), (-1, -2),
               (2, 1), (2, -1), (-2, 1), (-2, -1)]

      @lru_cache(maxsize=None)
      def dfs(x, y, k):
         if x < 0 or y < 0 or x >= n or y >= n:
            return 0.0
         if k == 0:
            return 1.0
         return sum(dfs(x + dx, y + dy, k - 1) for dx, dy in moves) / 8

      return round(dfs(x, y, k) * 100)