パズルの国のアリス

カードを順に積み上げろ(解答)

坂井 公(筑波大学)題字・イラスト:斉藤重之

解答例このパズルは,セル・オートマトン・ゲーム「ライフ」の発明者として名高いコンウェイ(J.H.Conway)の発案によるものとされ,実際に取り組んでみると,じっと考え込んだりカードを動かしたりで,椅子から動けなくなってしまうことから「コンウェイの釘付けパズル」と呼ばれている。この問題の難しさは,見えていないカードに依存せずに操作を決めねばならないので,うまくアルゴリズムを設計しないと,無限の繰り返しに陥ってしまい,目標の状態に行き着けなくなることにある。 

解はいくつもあるが,例えば次のように動かすとうまくいく。空き山が2つある場合,つまり全カードが1つの山になっているなら,トップカードをその左の空き山に動かす。この際,山は輪になっていると考え,カードの山が左端にのみあるなら,そのトップカードを右端に移す。以下でも同様だ。

具体的に示そう。カードの山が1つだけの場合,手順の前後の動きは以下の3通りになる。-は空き山を表す。

〔a,-,-〕 → 〔?,-,a〕
〔-,a,-〕 → 〔a,?,-〕
〔-,-,a〕 → 〔-,a,?〕

次に,空き山が1つだけなら,その左の山のトップカードを空き山に移す。具体的には

〔a,-,b〕 → 〔?,a,b〕
〔b,a,-〕 → 〔b,?,a〕
〔-,b,a〕 → 〔a,b,?〕

という動きになる。ただし,例外があり,〔2,-,1〕と〔2,1,-〕のときは,1を2の上に載せる。つまり,

〔2,-,1〕 → 〔1,-,?〕
〔2,1,-〕 → 〔1,?,-〕

空き山がない,すなわち全部のカードが見えている場合は次のようにする。まず,3のカードが左端にあれば2をその上に載せる。3が左端以外にあったら,その右にあるカードをさらに右に動かす。空き山がない場合の6パターンすべてを以下に示す。

〔3,2,1〕 → 〔2,-,1〕
〔3,1,2〕 → 〔2,1,-〕
〔2,3,1〕 → 〔1,3,-〕
〔1,3,2〕 → 〔2,3,-〕
〔2,1,3〕 → 〔-,2,3〕
〔1,2,3〕 → 〔-,1,3〕

 

なぜうまくいく?

なぜ,これでうまくいくのか,その理由を考えてみよう。

最初を除けば,3枚のカードが1つの山に集まることがあるのは例外の動きをした後であり,その場合,確かに目的に達する。その例外の動きをしたときも含 めて,目的状態に達していなければ,上の操作を繰り返すことですぐに空き山がなくなり,全部のカードが見えるようになる。

そのとき,3が左端にあればそこから2手で目的に達する。そうでなくても,操作を続けることで3はやがて左端に来て,右端の山が空くので,そこから3手で目的に達する。

 

カードが何枚あっても

カードが4枚以上あるとどうだろう。驚いたことに,カードが何枚あっても,3つの山のトップカードの移動だけで,左端にすべてのカードを集めて,順に並べることが可能である。もちろん,その操作は,3つの山の一番上のカードにのみ依存し,下のカードがどうなっているかにはよらない。

一般解を紹介しよう。以下,最大のカードというのは,もちろん見えているカードの中で最大という意味だ。

(a) 空き山がないなら,最大のカードの右のカードを1つ右にずらす。
(b) (a)の例外。左端に最大のカードがあり,右端にそれより1小さいカードがあれば,そのカードを左端に載せる。
(c) 空き山が1つだけなら,その左のカードで空きを埋める。
(d) (c)の例外。〔2,1,-〕のときは1を2の上に載せる。
(e) 山が1つだけなら,トップカードを左隣へ移して,空きの1つを埋める。

驚くべきことに,これだけの指示書で,どんな状態から始めても,カードが何枚あっても,やがて左端にカードが順に積み上がる。この指示書のミソは,最大のカードは(b),(d)の例外規則以外では上に他のカードが載ることがなく,右が空いたときに限り(c)によって右に移動するということだ。これでうまくいくことを厳密に証明するのは面倒だが,実際に少し操作をしてみると次のように状態が移っていくことに納得がいくだろう。nをカードの全枚数とする。

(1) どんな状態から始めても,途中で目的に達しない限り,n番のカードがどこかの山のトップに出て来る。
(2) やがて左端にn番だけの山ができる。
(3) (a),(b)により,左端のn番の上に降順に何枚かカードが積まれ,中央の山が空く。
(4) (a),(c)により,左端は再びn番だけになり,中央は空き,右端の上のほうは昇順に何枚かカードが積まれる。
(5) n番は,(c)によりいったん中央に移動するが,(a),(c)を繰り返して,再び左端に戻る。このとき,(4)のときの右端の山が,中央に来ている。
(6) (a),(b)により,再び(3)のような状態になるが,このとき左端の山は(3)のときより高くなる。
(7) (6)で左端にすべてのカード積まれていれば,目的達成である。そうでない場合(4),(5)が繰り返されて,(6)での左端の山が次第に高くなりやがては目的状態に達する。

 

違う動きの解が存在する!

以上,コンウェイによる見事な一般解を紹介したが,さらに驚いたことに,この一般解にすら別解が存在する。筆者の友人である富士通研究所の屋並仁史氏は,全く別のアイデアに基づいて新しい指示書を設計した。それは次のようなものだ。

(a) 中央と右端がともに空き山なら,左端のトップカードを右端に置く。
(b) 右端が空き山で中央が空きでなければ,中央のトップカードを左端に載せる。
(c) 右端が空きでなくて左端が空いていれば,右端のトップカードを中央に載せる。
(d) 右端も左端も空いていない場合,左端のトップカードを中央に載せる。(e) (d)の例外。右端も左端も空いていない場合,右端のトップカードより1小さいカードが見えていれば,そのカードを右端に載せる。

この指示書による操作ではカードが次第に揃っていく様子がコンウェイのものとはずいぶん異なる。実際にカードを動かしてみるとすぐにわかるが,

(1) (d)と(e)という2種の動きにより,左端のカードがどんどん中央と右端の山に振り分けられ,左端が空く。
(2) (c)によりカードは中央に集まる。
(3) (b)によりカードは左端に集まる。
(4) ここで(a)の操作によって右端の空きが埋まった後,再び(d)と(e)による振り分けが始まり,(1)-(3)の動きが繰り返される。

例えば3-4-5のような連続する数値列を「連」と呼ぶことにすると,注目すべきは(3)の終了時点での左端の山の中の連の様子だ。操作を繰り返しても, トップカードがそれまでの連から外れて別の連の最後のカードになることを除けば,連は壊れることがない。こうして,連は互いにくっつきあい次第に長くなっ ていく。そして最後には1からn番までの全体で1つの連ができあがり,目的が達成されるというわけだ。

さらに別の一般解があるかもしれない。見つけた読者は,ぜひ,下記のリンクからフォームを使って編集部にお知らせいただたい。

フォームはこちらから

 

参考にした本:Peter Winklerによる次の2冊(ともに出版元はA K Peters, Ltd.)Mathematical Puzzles: A Connoisseur’s Collection(2004)Mathematical Mind-Benders(2007)ルイス・キャロルによる『不思議の国のアリス』『鏡の国のアリス』(さまざまな出版社から,さまざまな訳者による翻訳本や注釈本が出ている)

 

 

問題に戻る

 

 

 

問題はこちらです