第38回
2013年 11月号
|
全てのライトを消せ!(その1) 〜無限ライツアウトの曼陀羅〜
n×nライツアウトの特性行列/逆特性行列/検査行列一覧 他
|
ダウンロード→n×nライツアウト(n=2〜100)の特性行列A/逆特性行列B/掃き出し検査行列Cの一覧(テキストファイル/約764KB)ライツアウトにおいて、掃き出し操作(2〜n行のボタンのみを押して、1〜n-1行のライトを全て消灯する操作)は容易に行えるので、掃き出し後のn行目の点灯パターンを元に盤面を全て消灯することを考え、その作業に必要な行列を用意します。ここでの行列の演算は、成分が全て二元体の要素であるものとして行います。 具体的な解法としては、まず掃き出し操作を行い、その結果のn行目をCでチェックして解が存在することが確認されたら、Bを用いて求めた押下パターンに従い1行目を操作した後、あらためて掃き出し操作を行うことで、盤面全てを消灯できます。 nが20までのケースについては、こちらのFlashで実際に操作して確かめてみて下さい 特性行列A全消灯状態から、1行目のボタンだけをいくつか押下した上で掃き出し操作を行う場合において、1行目の押下パターンと掃き出し後のn行目の点灯パターンの対応を表したn×n行列。「rank=*」と表示されている数字は、この行列Aの階数。 逆特性行列B1〜n-1行目は全て消灯している状態に対し、n行目も含め全て消灯するための押下パターン(解)が存在するとき、元のn行目の点灯パターンと、代表解の1行目の押下パターンの対応を表したn×n行列。rank A=n の場合は、BはAの逆行列。 掃き出し検査行列C1〜n-1行目が全て消灯している状態に対し、解が存在するかどうかをチェックするための行列。n行目の点灯パターンをzとするとき、Cz=oであることと解が存在することが同値。r=rank Aとすると、Cは(n-r)×n行列。r=n の場合は、必ず解が存在するため、Cは定義されない。 ダウンロード→n×nライツアウト(n=2〜1000)の特性行列の階数一覧(テキストファイル/約19KB)n=1000までの全てのケースについて、特性行列Aの階数のみを示します。行末に#の記号があるものは、rank A<nとなっているもの、すなわち、一部の点灯パターンに対してのみ解が存在し、掃き出し検査行列が存在するケースです。 ダウンロード→十字関数の作る図形(PDFファイル/約438KB)本編記事の図10に示した図の拡大版。十字関数は、n×nライツアウトを統合的に扱う際に重要な意味を持つ関数であり、その詳細は本編記事参照。 |