コラム

15パズルの確率－ランダムに設定したパズルが解ける確率は?

2025年01月14日

（篠原 拓也） 保険計理

関連カテゴリ

世の中にはさまざまな種類のパズルがある。クロスワードパズルやナンバープレース(ナンプレ)といった有名なものは、「やったことがある」という人が多いはずだ。

他にも、迷路、ロジックパズル、ジグソーパズルから詰将棋や詰碁に至るまで、インターネットや雑誌などではパズルにことかかない。こうしたパズルのよい点として、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パズルは、1874年に、ニューヨークの郵便局長を務めていたノイズ・チャップマン氏が考案したのが原型とされている。

1878年には、パズル作家のサム・ロイド氏が、15パズルについて有名な問題を出題した。次の左図の「スタート」の状態から始めて、右図の「ゴール」の状態にせよ、という問題だ。
一番下の段の「14」と「15」のブロックを入れ替えるだけで、一見簡単にできそうだ。だが、これができない。出題された当時、多くの人が試みたといわれるが、誰一人完成する人はいなかった。

それもそのはず。実は、このサム・ロイド氏の出題した問題は、後に、完成できないことが示されている。「スタート」の状態によっては、「ゴール」の状態にできない、つまり完成できない場合もあるということになる。

◇ 完成できる確率は?

そこで、15パズルに関して、次のような確率の問題が浮上してくる。
 

(15パズルの確率の問題)
15パズルで、一番右下を空白として、それ以外の場所に「1」から「15」の15個のブロックをランダムに置いて、「スタート」の状態を作ります。このとき、ブロックを動かしていって「ゴール」の状態にできる、つまり完成できる確率は、どれぐらいでしょうか？

この問題を解くには、どんなふうに考えたらよいだろうか。まず、考えられるすべての「スタート」のパターンをしらみつぶしに調べていく、という地道な方法が考えられるだろう。「スタート」のパターンの数はしょせん有限個に過ぎないのだから、1つ1つ調べていけば、(大変だろうが)いつかは答えが得られるだろう、という考え方だ。

だが、すべての「スタート」のパターンの数は、15の階乗(15!)通りある。数字で表すと、1兆3076億7436万8000通りとなる。スーパーコンピューターでも使えば、あっという間に計算できるかもしれないが、1人で1つ1つ調べることは、時間と体力と精神力の面からほぼ不可能とみてよいだろう。

さらに、そもそも完成できるかどうかをどうやって調べるのか、という問題もある。完成できることを示すには、実際にブロックを動かしていって、「ゴール」の状態にできればよい。問題は、完成できない場合だ。この場合は、実際にブロックを動かして「ゴール」の状態にならないからといって、完成できないとは言い切れない。他に「ゴール」に至るうまい動かし方があるかもしれないからだ。つまり、なにか別の形で、完成できないことを示す必要がある。

◇ 15パズルを解くということは、互換を何度も繰り返すこと

こう考えていくと、どうやら15パズルはかなり奥深いということがわかってくる。実は、完成できるかどうかを判断するためには、数学の群論と言われる分野で出てくる「置換」(複数のものをある順列から他の順列に並べ替えること)とか、「互換」(2つのものを互いに取り換えること)といった考え方が必要となる。

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となる。これが、確率の問題の答えとなる。

【次ページ】“予想”が正しいことの確認は、稿末の(参考)に

1 2

保険研究部   主席研究員 兼 気候変動リサーチセンター チーフ気候変動アナリスト 兼 ヘルスケアリサーチセンター 主席研究員

篠原 拓也（しのはら たくや）

研究領域：保険

研究・専門分野
保険商品・計理、共済計理人・コンサルティング業務

レポートについてお問い合わせ
(取材・講演依頼)

経歴 ＋ －

【職歴】
　1992年　日本生命保険相互会社入社
　2014年　ニッセイ基礎研究所へ

【加入団体等】
　・日本アクチュアリー会　正会員

関連レポート

レポートについてお問い合わせ
(取材・講演依頼)

関連カテゴリ・レポート

研究員の眼

保険計理