フリーセルは、全部のカードが見えているので、コンピューターで解き方を探すのに向いたゲームです。ここでは、コンピューターがフリーセルをどう解くのかを、やさしく紹介します。このページのために、アプリ「フリーセル」と同じ決まりで動くプログラムを作って試しました。

探索 ― 手を指しては先を調べる

コンピューターは、人と同じように「この手を指したら、どうなるか」を調べます。違うのは、その数です。

  1. 今の盤面で指せる手を、全部書き出す(フリーセルへ置く、場札へ重ねる、ホームセルへ積む、など)。
  2. ひとつの手を指して、新しい盤面を作る。
  3. その盤面で、また指せる手を全部書き出す。
  4. ホームセルに52枚積めた盤面が見つかったら、そこまでの手順が答え。

この「盤面から盤面へ、枝分かれしながらたどっていく」ことを探索といいます。

工夫1: 同じ盤面を二度調べない

フリーセルでは、ちがう順番で動かしても、同じ盤面にたどり着くことがよくあります。カードを右へ動かして、また左へ戻せば、元の盤面です。一度調べた盤面を覚えておき、同じ盤面が出てきたら調べない、とすると、むだがぐっと減ります。

さらに、列の順番だけがちがう盤面や、フリーセルの中の並びだけがちがう盤面も、解き方は同じです。これらを同じ盤面として扱うと、調べる数をもっと減らせます。

工夫2: 見込みのよい盤面から調べる

全部の盤面を順に調べていては、時間がかかりすぎます。そこで、「ホームセルに積んだ枚数が多い」「次にホームセルへ積みたいカードの上に乗っている枚数が少ない」「フリーセルが空いている」といった点数を付けて、見込みのよい盤面から先に調べます。

このページのプログラムで、Windowsのフリーセルの1番の配札を解かせると、843の盤面を調べたところで、110手の解き方が見つかりました。人が考えると大変でも、コンピューターには一瞬です。見つかる手順は、いちばん短い手順とは限りません(移動した回数とクリアの手数)。

解けないことを確かめる

解き方が見つかれば、その配札は解けます。では、「解けない」ことは、どう確かめるのでしょう。

答えは、たどれる盤面を全部調べることです。どの手を指しても、もう新しい盤面が出てこなくなり、それでも52枚積めた盤面がなければ、その配札は解けないと分かります。

Windowsのフリーセルの11982番は、解けない配札として知られています。このページのプログラムでも、11982番は、ホームセルから戻す手も含めて、たどれる盤面(約9万5千)を全部調べても、解き方がありませんでした(フリーセルはほとんど解ける)。

まとめて動かす決まりは、解けるかどうかに関係ない

アプリ「フリーセル」で1回に動かせるのは「空いているフリーセルの数+1」枚までで、空いた列では増えません(まとめて動かせる枚数)。でも、まとめて動かす手は、フリーセルや空いた列を使った1枚ずつの手に分けられます。たどれる盤面は同じなので、解ける配札は同じです。変わるのは、移動した回数の数え方だけです。

アプリ「フリーセル」の配札の検算

アプリ「フリーセル」の配札は、毎回ランダムに混ぜて配ります。作者は、ランダムな10万通りの配札をコンピューターで解き、見つけた解き方を、アプリと同じゲームのしくみで実際に最後まで指して確かめました。結果は、10万通りすべてに解き方がありました。

ただし、これは「全部の配札が解ける」という証明ではありません。調べていない配札の中に、解けないものがまれにある可能性は残ります。

解き方の考え方は、人が遊ぶときにも役に立ちます。フリーセルの攻略と必勝法もどうぞ。