月刊「現代数学」数学パズルにトドメをさす?! 今月のFlash    おまけは→こちら
第39回
2013年 12月号
全てのライトを消せ!(その2) 〜その操作は冗長〜
n×nライツアウトの不動操作のパターンを観察する
Adobe Flash Player を取得

目的

n×nサイズのライツアウトにおける不動操作(その一連の操作を行う前後において、盤面のライトの点灯パターンが変化しないような操作)となる押下パターンを表示します。

また、どの不動操作においても押さないボタン(=ライト)は孤立ライト(そのライトのみ点灯している状態に対して解が存在するようなライト)となることを利用して、不動操作を重ね合わせて孤立ライト配置パターンを浮かび上がらせる様子をアニメーションで表示します。

奇妙な不動操作パターンや、特徴的な孤立ライト配置を観察してみましょう。また、n≦20のものについては、それらが実際に不動操作/孤立ライトになっていることを、前回Flashを用いて確かめてみましょう。

操作方法

ライツアウト面のサイズの選択

・右上の一覧から、数字を選んでクリックすると、その数字をnとして、n×nライツアウト面が選択されます。最初に選択された際には全検査行列Tを計算する処理が実行されます。サイズによってはその処理に1分以上かかりますが、2度目以降選択された場合は、前回作成した行列を記憶しているので、処理は短縮されます。

・一覧で白くハイライトされているのが現在選択されてるサイズ、青く色がついているものは1度選択されて必要なデータが作成済みのサイズを意味します。

・選択できるサイズは、100以下のnのうち、特性値dnが0でないものです。各nに対する特性値は、ここに公開してある一覧を参照して下さい。

・初期状態では、n=11が選択されています。

不動操作パターンの表示

・n×nライツアウトの特性値をdnとすると、全ての不動操作はdn個の代表不動操作の排他的論理和による重ね合わせによって得られます。画面下の「Select Combination」欄で代表不動操作の組合せを選ぶことで、2^dn個全ての不動操作パターンを表示させることができます。

・「Select Combination」欄では、黒マスが選択、白マスが非選択を意味します。また、パターンを表示するメイン画面では、黒マスが不動操作で押下するボタンを表します。

・No-change Operationメニューで「Single」を選択した場合、「Select Combination」欄をクリックすると対応する1個の代表不動操作パターンのみが選択され、表示されます。

・No-change Operationメニューで「Multiple」を選択した場合、「Select Combination」欄をクリックする毎に対応する代表不動操作パターンの選択/非選択が反転し、自由な組合せで重ね合わせた不動操作パターンを表示させることができます。

・なお、「Select Combination」欄の各マスにマウスを乗せると、対応する代表不動操作パターンがメイン画面で赤くハイライトされるので、「Multiple」で全て非選択状態にしてメイン画面をクリアした状態で「Select Combination」欄の各マスの上でマウスを動かすと、代表不動操作パターンのみを次々に表示させることができます.

孤立ライト配置パターンの表示

・「Solitary Blocks」をクリックすると、代表不動操作パターンを順次重ね合わせて(ここでは、論理和により重ねます)得られたものを最後に反転させて、それが孤立ライトの配置パターンになるという過程を、アニメーションで表示します。

・孤立ライトパターン表示後、不動操作パターン表示に戻るには、Single/Multipleのいずれかをクリックします。

代表不動操作について

各不動操作パターンは、そのパターンの一番下の行の右からdnマス(メイン画面で赤枠で表示)のパターンと1対1に対応しており、代表不動操作パターンはその枠内で1マスのみ黒マスとなっているものとなっています。したがって、複数の代表不動操作を重ねた不動操作パターンにおいては、「Select Combination」欄の黒マスの配置と、メイン画面の赤枠内の黒マスの配置が一致します。

なお、代表不動操作は、全検査行列Tの各行とも一致します(詳細は本編記事参照)。15以下のnについてのTは、ここに公開してあります。また、100以下のnについてのTの各行(n^2次の行ベクトル)をn×nに折り返したもの、すなわち、ここでの代表不動操作パターンに相当するものも、テキストファイルで同じページに公開してあります。

特性値=0の場合

特性値dn=0の場合は、全ての点灯パターンが唯一解を持つため、不動操作は存在せず、全てのライトが孤立ライトとなります。