Pythonでn個のルークが互いに攻撃し合わないように配置する方法の数を求めるプログラム

この記事では、n×n のチェス盤に n 個のルークを、互いに攻撃し合わないように配置する方法が何通りあるかを Python で求める方法を解説します。

問題の概要

サイズ n×n のチェス盤があるとします。ここに n 個のルークを、どのルークも他のルークを攻撃できないように配置するとき、その配置方法の総数を求めます。

ルークは同じ行または同じ列にある駒を攻撃できるため、「互いに攻撃し合わない」という条件は「すべてのルークがそれぞれ異なる行・異なる列に存在する」ことを意味します。

また、2つの配置方法は、あるマスが一方の配置では占められていて、もう一方では占められていない場合に「異なる」とみなされます。

入力例

例えば n = 3 の場合、答えは 6 通りになります。

解き方の考え方

1行目にルークを置ける列は n 通りあります。2行目ではすでに使った列を除いた n−1 通り、3行目では n−2 通りというように、行が下がるごとに選択肢が1つずつ減っていきます。

したがって、配置方法の総数は次のように表せます。

n × (n−1) × (n−2) × … × 1 = n!(n の階乗)

アルゴリズムの手順

• n の階乗 f を計算する
• f を返す

実装例(Python)

Python では標準ライブラリ math.factorial を使うことで、階乗を簡単に計算できます。

import math

class Solution:
    def solve(self, n):
        return math.factorial(n)

ob = Solution()
print(ob.solve(3))

入力

3

出力

6

計算量について

math.factorial(n) の計算時間は O(n) 回の乗算で済むため、非常に効率的です。n が大きくなっても高速に答えを求められる点が、この解法の大きなメリットです。