C++で解くチェス盤上のナイトが盤内に残る確率の求め方

問題概要

N×Nのチェス盤があるとします。ナイトはr行c列目のマスからスタートし、ちょうどK回の移動を試みます。行と列は0始まりのインデックスで表されるため、左上のマスは(0, 0)、右下のマスは(N-1, N-1)となります。

ナイトは1つのマスから8種類の異なるマスへ移動することができます。その移動パターンは下図の通りです。

ナイトは移動のたびに、8つの可能な移動の中からランダムに1つを選択します。そして、ちょうどK回の移動を完了するか、チェス盤の外に出てしまうまで移動を続けます。この問題では、ナイトが移動を終えた時点で盤上に残っている確率を求めます。

例えば、入力が「3, 2, 0, 0」の場合、出力は0.0625になります。これは、最初の移動で盤内に留まれるのが(1, 2)と(2, 1)への2通りのみであり、さらにそれぞれの位置からも2通りの移動しか盤内に留まれないためです。したがって、ナイトが最後まで盤上に残り続ける確率は0.0625となります。

解法のアプローチ

この問題は、メモ化再帰(動的計画法)を用いることで効率的に解くことができます。手順は以下の通りです。

• 方向配列dirを [[-2,-1], [-2,1], [2,-1], [2,1], [1,2], [1,-2], [-1,2], [-1,-2]] として定義します。
• 再帰メソッドsolve()を定義します。引数はx、y、n、k、および3次元配列dpです。
• x >= n または y >= n または x < 0 または y < 0 の場合は0を返します(盤外に出たことを意味します)。
• kが0の場合は1を返します(移動回数を使い切った状態)。
• dp[k][x][y]が-1でない場合(計算済み)、その値を返します。
• dp[k][x][y]を0で初期化します。
• iを0から7までループさせ、各方向について dp[k][x][y] += solve(x + dir[i][0], y + dir[i][1], n, k - 1, dp) を実行します。
• dp[k][x][y]を返します。

メイン関数での処理

• (K + 1) × N × N のサイズを持つ3次元配列dpを作成し、全要素を-1で初期化します。
• solve(r, c, N, K, dp) / 8^K を結果として返します。

以下の実装例を見ると、より理解が深まるでしょう。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int dir[8][2] = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
class Solution {
    public:
    double solve(int x, int y, int n, int k, vector<vector<vector<double>>>& dp){
        if(x >= n || y >= n || x < 0 || y < 0) return 0.0;
        if(k == 0) return 1.0;
        if(dp[k][x][y] != -1) return dp[k][x][y];
        dp[k][x][y] = 0;
        for(int i = 0; i < 8; i++){
            dp[k][x][y] += solve(x + dir[i][0], y + dir[i][1], n, k - 1, dp);
        }
        return dp[k][x][y];
    }
    double knightProbability(int N, int K, int r, int c) {
        vector<vector<vector<double>>> dp(K + 1, vector<vector<double>>(N, vector<double>(N, -1)));
        return solve(r, c, N, K, dp) / pow(8, K);
    }
};
main(){
    Solution ob;
    cout << (ob.knightProbability(3, 2, 0, 0));
}

入力

3
2
0
0

出力

0.0625

計算量の評価

時間計算量は O(K × N²) です。状態(k, x, y)の組み合わせは最大 (K+1) × N × N 個であり、メモ化によって各状態は一度しか計算されません。各状態から8方向への遷移を行うため、全体としても O(K × N²) に収まります。空間計算量も、メモ用の3次元配列の分である O(K × N²) となります。単純な全探索では8^K通りの経路を調べる必要がありますが、メモ化により指数オーダーから多項式オーダーへ大幅に削減できる点が、この手法の大きな利点です。