- シンクタンクならニッセイ基礎研究所 >
- 保険 >
- 保険計理 >
- 15パズルの確率-ランダムに設定したパズルが解ける確率は?
15パズルの確率-ランダムに設定したパズルが解ける確率は?

保険研究部 主席研究員 兼 気候変動リサーチセンター チーフ気候変動アナリスト 兼 ヘルスケアリサーチセンター 主席研究員 篠原 拓也
文字サイズ
- 小
- 中
- 大
他にも、迷路、ロジックパズル、ジグソーパズルから詰将棋や詰碁に至るまで、インターネットや雑誌などではパズルにことかかない。こうしたパズルのよい点として、1人で手軽にできること、ちょっとした空き時間に簡単にできること、そして適度に頭を使うこと、などが挙げられるだろう。
そうしたパズルの1つとして、「15パズル」がある。空白部分にブロックをタテまたはヨコに動かしていって、ゴールの配置になることを目指すというもので、スライディングブロックパズルの1種だ。例えば、下記の左図の「スタート」の状態から始めて、右図の「ゴール」の状態にできれば完成ということになる。(一番右下の白い部分はブロックがない空白部分を表す。)
上記の例では、「15」を右に、「7」を下に、「8」を左に、「15」を上に、「7」を右に、「8」を下に、「11」を下に、「12」を左に、「15」を上に、「7」を上に、「8」を右に、「11」を下に、「12」を下に、「15」を左に、「7」を上に、「8」を上に、「11」を右に、「12」を下に、「15」を下に、「7」を左に、「8」を上に、「11」を上に、「12」を右に、「15」を下に、「11」を左に、「12」を上に、という順にブロックを動かしていけば、完成できる。このように一手ずつ書き出していくと何か大変そうだが、パズルを実際にやってみるとそれほどの苦労はなく、楽しむことができる。
今回は、この15パズルについて見ていこう。
◇ 「スタート」の状態によっては、完成できない場合もある
それもそのはず。実は、このサム・ロイド氏の出題した問題は、後に、完成できないことが示されている。「スタート」の状態によっては、「ゴール」の状態にできない、つまり完成できない場合もあるということになる。
◇ 完成できる確率は?
(15パズルの確率の問題)
15パズルで、一番右下を空白として、それ以外の場所に「1」から「15」の15個のブロックをランダムに置いて、「スタート」の状態を作ります。このとき、ブロックを動かしていって「ゴール」の状態にできる、つまり完成できる確率は、どれぐらいでしょうか?
だが、すべての「スタート」のパターンの数は、15の階乗(15!)通りある。数字で表すと、1兆3076億7436万8000通りとなる。スーパーコンピューターでも使えば、あっという間に計算できるかもしれないが、1人で1つ1つ調べることは、時間と体力と精神力の面からほぼ不可能とみてよいだろう。
さらに、そもそも完成できるかどうかをどうやって調べるのか、という問題もある。完成できることを示すには、実際にブロックを動かしていって、「ゴール」の状態にできればよい。問題は、完成できない場合だ。この場合は、実際にブロックを動かして「ゴール」の状態にならないからといって、完成できないとは言い切れない。他に「ゴール」に至るうまい動かし方があるかもしれないからだ。つまり、なにか別の形で、完成できないことを示す必要がある。
◇ 15パズルを解くということは、互換を何度も繰り返すこと
1番目の例で、まず空白部分を「16」のブロックと考えることにしよう。そして、「15」のブロックを右の空白部分に動かす、という動作を「15」と「16」を取り換える ― 「15」と「16」を互換する、と考える。
このように考えると、15パズルを解くということは、「スタート」の状態から、あるブロックと「16」のブロックの互換を何度も繰り返していって「ゴール」の状態にすることと同じと言える。互換を繰り返していって、「スタート」の状態を「ゴール」の状態に置換する、という風に考えるわけだ。
◇ 置換全部のうち、偶置換がどれだけあるかということ
もう一度、完成できる1番目の例と、完成できない2番目のサム・ロイド氏の問題の例を見てみよう。2つのパズルでは何が違うのだろうか?
1番目の例では、「7」と「11」、「8」と「12」の2つの互換をすればよい。一方、サム・ロイド氏の問題の例では、「14」と「15」の1つの互換をすればよい。
互換が2つの場合は完成できて、1つの場合は完成できないことになる。そもそも「ゴール」の状態から何も置換しない場合、つまり互換が0個の場合は、当然完成できる(というか、完成している)。こう考えてみると、「どうやら互換が偶数個の置換は完成できるが、奇数個の置換は完成できないのではないか」ということが“予想”できる。
そして、実はこの“予想”は正しい。ここからは、数学的な厳密さをやや欠くが、そのエッセンス部分をとらえる、という態度で話を進めていく。
かなり唐突だが、15個のものからできる置換全部からなる群は「15次対称群」と言われる。15パズルで言えば、一番右下を空白として、考えられる全ての「スタート」の状態を要素に持つ集合が、その一例となっている。(本稿では、この集合が群になることの証明は行わない。) これは、数で言えば、15の階乗(15!)、1兆3076億7436万8000個もの要素(置換)からなる巨大な集合だ。
次に、偶数個の互換で表すことのできる置換(これを「偶置換」という)の全部からなる集合を考えると、これも群論でいうところの群となる。(本稿では、ある置換が偶置換かどうかは一意に決まることや、偶置換全部の集合が群になることの証明は行わない。興味がある方は、群論の本をご覧いただきたい。)
この偶置換全部からなる群は「15次交代群」と言われる。そして、ここが重要なポイントなのだが、15次交代群の要素の個数、つまり偶置換の個数は、15次対称群の要素の個数のちょうど半分となることが示される。数で表すと、6538億3718万4000個となる。
偶数個ではなく奇数個の互換で表される置換(これは「奇置換」と言われる)の全部の個数は、15次対称群の要素の個数と、15次交代群の要素の個数の差で、やはり6538億3718万4000個となる。
このような群論の考え方を使って、15個のブロックをランダムに置いて作られた「スタート」の状態が、「ゴール」の状態の偶置換となっている確率は、1/2となる。これが、確率の問題の答えとなる。
(2025年01月14日「研究員の眼」)

保険研究部 主席研究員 兼 気候変動リサーチセンター チーフ気候変動アナリスト 兼 ヘルスケアリサーチセンター 主席研究員
篠原 拓也 (しのはら たくや)
研究・専門分野
保険商品・計理、共済計理人・コンサルティング業務
03-3512-1823
- 【職歴】
1992年 日本生命保険相互会社入社
2014年 ニッセイ基礎研究所へ
【加入団体等】
・日本アクチュアリー会 正会員
篠原 拓也のレポート
日付 | タイトル | 執筆者 | 媒体 |
---|---|---|---|
2025/02/10 | 欧州の自然災害リスクへの取り組み-気候変動による自然災害への対策は段階的アプローチで | 篠原 拓也 | 基礎研レター |
2025/02/06 | バレンタインジャンボ2025の検討-狙いは一攫千金? 超高額当せん? それともポートフォリオを作る? | 篠原 拓也 | 研究員の眼 |
2025/02/04 | 気候変動と食品ロス・廃棄物削減-消費者がすぐに貢献できる気候変動対策のポテンシャルは大きい | 篠原 拓也 | 基礎研レター |
2025/01/28 | 屋根裏部屋の電球の問題-デジタルの感性とアナログの感覚をうまく組み合わせる | 篠原 拓也 | 研究員の眼 |
公式SNSアカウント
新着レポートを随時お届け!日々の情報収集にぜひご活用ください。
新着記事
-
2025年02月17日
QE速報:10-12月期の実質GDPは前期比0.7%(年率2.8%)-3四半期連続のプラス成長も、内需は低迷 -
2025年02月17日
タイパ時代の「脱タイパ」消費とは-「消費に失敗したくない」Z世代 -
2025年02月14日
マレーシア経済:24年10-12月期の成長率は前年同期比+5.0%~内需が好調で堅調な成長ペースを維持 -
2025年02月14日
英国GDP(2024年10-12月期)-前期比0.1%と低空飛行が続く -
2025年02月14日
保険と年金基金における各種リスクと今後の状況(欧州 2025.1)-EIOPAが公表した報告書(2025年1月)の紹介
レポート紹介
-
研究領域
-
経済
-
金融・為替
-
資産運用・資産形成
-
年金
-
社会保障制度
-
保険
-
不動産
-
経営・ビジネス
-
暮らし
-
ジェロントロジー(高齢社会総合研究)
-
医療・介護・健康・ヘルスケア
-
政策提言
-
-
注目テーマ・キーワード
-
統計・指標・重要イベント
-
媒体
- アクセスランキング
お知らせ
-
2024年11月27日
News Release
-
2024年07月01日
News Release
-
2024年04月02日
News Release
【15パズルの確率-ランダムに設定したパズルが解ける確率は?】【シンクタンク】ニッセイ基礎研究所は、保険・年金・社会保障、経済・金融・不動産、暮らし・高齢社会、経営・ビジネスなどの各専門領域の研究員を抱え、様々な情報提供を行っています。
15パズルの確率-ランダムに設定したパズルが解ける確率は?のレポート Topへ