これからお前たちに奴との出会いについて語るとしよう
悪魔との出会いを

ザックリー クラウドアトラス（映画）

昏き揺らぎの地 のリドルである叡智の瞳パズルをなんとかうまく解く方法を考えたい。

ルールの整理

状態

石碑にはめ込まれた叡智の瞳は（赤い）光を宿している状態（）と宿していない状態（）がある。

光を宿している状態	光を宿していない状態

操作

パズルを解くうえで許されている操作は、一度に任意の１カ所の叡智の瞳を操作するのみである。 操作をすると、操作を行った叡智の瞳と「左上」「右上」「右下」「左下」の石碑の状態が反転する。 反転対象の叡智の瞳が存在しない場合は操作されない（上下左右がつながっているという事はない）。 ゆえに１度に反転する石碑は最低３か所（角の石碑）、最大５か所（中央の石碑）である。

[石碑操作例] 中央の叡智の瞳を操作した

[石碑操作例] ４行目右の叡智の瞳を操作した

スタート

ランダムに２つの叡智の瞳に光を宿している状態。

[開始状態]

ちなみに問題数は ${}_9 C_2 = 36$ 通りとなる。 そのうち回転や反転を行って同じ組み合わせになるものを除くと全８種類となる。

開始状態全パターン

回転・反転で同じ状態になるものを除く。

ゴール

すべての叡智の瞳に光を宿す。 すべての叡智の瞳に光を宿すと叡智の瞳は青い瞳を宿す。

[パズル解答例] Pattern.D から始めてゴールまで（最短手数）

数学的性質

石碑の座標表記

石碑の座標表記を導入する。

石碑はひし形状に並んでいるが正方形に並べたものを 45 度傾けたものとみなすことができる。 二次元に柱が配置されているので行列とみなし $s_{m, n}$ で石碑の位置を指定する事も可能であるが、プログラム作成上の都合によりベクトルとみなし０を起点 (0-origin) とし番号を振ることにする（これからの計算にもほとんど支障はきたさない）。

パズルの性質

• 同じ叡智の瞳を続けて２回押すとすべての叡智の瞳の状態が元に戻る
• 叡智の瞳を操作する順序は関係ない

[パズルの性質] Pattern.B の状態で座標４ ($s_4$) の叡智の瞳を２回続けて操作する

これらの性質により以下のことがわかる。

叡智の瞳が光を宿しているかどうかの判定は…
叡智の瞳の状態が変化した回数が偶数回か奇数回かによって決定される

導出への準備

叡智の瞳の数式表現

特定の石碑を $s_i$ と表し、叡智の瞳全体をベクトルで以下のように表記する。

叡智の瞳の状態の数式表現

$n$ の位置の叡智の瞳が光を宿している状態を $s_i = 1$ とし、光を宿していない状態を $s_i = 0$ とする。たとえば、右のような石碑の状態をベクトルで表現すると以下のようになる。

これにより叡智の瞳は以下のような性質をもつ。

• $s \in 0, 1$
• $0 \leq s \leq 1$

叡智の瞳の演算

叡智の瞳の状態は変化した回数の偶奇によって決定する性質により２の剰余をとる演算で事足りる。

[演算例] $s_i$ に光が宿っている状態で $s_i$ に影響する叡智の瞳を２回 操作 された

演算結果が 1 なので $s_i$ は現在、光が宿っているということがわかる。

四則演算の結果を以下のように定義する。

• 和算と差算の演算結果は同様になり排他的論理和 (XOR) 演算と同様
• 積算と除算も演算結果は同様になり論理積 (AND) 演算と同様

計算式の作成

• 叡智の瞳の初期状態を $a_i$
• 叡智の瞳の操作後の状態を $b_i$
• $i$ の叡智の瞳が操作された回数を $h_i$
• いずれも $0 \leq i \leq 8$

$a_i, b_i, h_i$ は以下の関係になる。

\[ b_i = \left\{ \begin{array}{rcrcrcrcrl} a_i & + & h_{i-3} & & & + & h_{i+1} & + & h_{i+3} & \qquad \mathrm{if} \quad i \equiv 0 \\ a_i & + & h_{i-3} & + & h_{i-1} & + & h_{i+1} & + & h_{i+3} & \qquad \mathrm{if} \quad i \equiv 1 \\ a_i & + & h_{i-3} & + & h_{i-1} & & & + & h_{i+3} & \qquad \mathrm{if} \quad i \equiv 2 \\ \end{array} (\mod 3) \right. \\ \mbox{（ただし、$i<0$ または $8 < i$ のときは $h_i = 0$ とする）} \]

操作した叡智の瞳 $a\_i$ とその左上 $h\_{i-3}$ 、左下 $h\_{i-1}$、右上 $h\_{i+1}$、右下 $h\_{i+3}$ を足したもの。 但し書きは、存在しない座標の叡智の瞳を無視するためのものである。 基点から直列に座標を振ったので、場合分けが発生してしまったが式は複雑さは増していない。

[参考] 叡智の瞳を行列として扱った場合

叡智の瞳の並びを行列とみなし２つのパラメータで座標を割り当てる。 以下は前項のものをベクトルから行列に置き換えたもの。 計算式の作成の項と比較すると場合分けがなくなって１本の式になった。

• 叡智の瞳の初期状態を $a_{m,n}$
• 叡智の瞳の操作後の状態を $b_{m,n}$
• $(m,n)$ の叡智の瞳が操作された回数を $h_{m,n}$
• いずれも $0 \leq m, n \leq 2$

$a\_{m,n}, b\_{m,n}, h\_{m,n}$ は以下の関係になる。

\[ b_{m,n} = a_{m,n} + h_{m-1,n} + h_{m,n-1} + h_{m,n+1} + h_{m+1,n} \\ \mbox{（ただし、$m,n<0$ または $2 < m,n$ のときは $h_{m,n} = 0$ とする）} \]

叡智の瞳の連立方程式

計算式の作成の項で作成した計算式にすべての叡智の瞳を当てはめると以下のようになる。

方程式を解く上での問題

石碑のリドルはすべての叡智の瞳に光を宿す、つまり初期状態または途中まで解かれた状態 $a_i$ に対して $b_i = 1$ となるような $h_i$ の値をうまく見つければよい。 つまり、上記の九元一次方程式を解いて $h_i$ の値を求めればよい。 しかし、$b_i = 1$ となる値を見つけるのは式が複雑になるので叡智の瞳の状態に対偶をとって考える。 そこで、改めてルールを簡単をイメージすると以下の通り。

イメージ

• スタート：すべての叡智の瞳が光を宿った状態からランダムに２つの叡智の瞳が光を宿していない
• ゴール：すべての叡智の瞳に宿させない
• 状態：同じ
• 操作：同じ

行列へ変換

まず、とりあえず $b_i = 0$ を代入して $a_i$ を左辺に移行する。 $b_i = 0$ を代入したので叡智の瞳は光を宿していない状態を指していることに注意（前項参照）。 $a_i$ を左辺に移行すると以下な連立方程式になる。

右辺にでてくる係数を行列にまとめると以下のようになる。 またこれを叡智の瞳の方程式と名づける。

記号の導入

叡智の瞳の方程式をもう少し抽象化する。

として $\mathbf{a} = S \mathbf{h}$ と完結に記述できるようになった。

$a_i$ 移行関する補足

$b_i = 0$ を代入して $a_i = \ldots$ となる理由。

$a_i = 0$ の場合

$a_i = 1$ の場合（参照：叡智の瞳の演算）

$a_i$ が取りうるすべての値 $( 0, 1 )$ において同じ結果になるので行列へ変換の項にある連立方程式になる。

叡智の瞳の方程式

叡智の瞳の方程式 $\mathbf{a} = S \mathbf{h}$ をどう解くか考えたい。 パズルのゴールである $\mathbf{b}$ はすでに除去されておりパズルの初期状態である $\mathbf{a}$ は既知である。 そして $S$ は定数であるから、未知なのは $\mathbf{h}$ だけである。 そこで $\mathbf{h} = \ldots$ という形に式を持っていきたい。

方程式の右辺にある $S$ を除去したい。 そこで $S$ の逆行列であある $S^{-1}$ を（行列では積算の交換法則が成り立たないため）両辺の左から掛けて $S$ を除去することで $\mathbf{h} = \ldots$ という形の式になった。

$ S^{-1} $ を求める

$2 \times 2$ 行列、$3 \times 3$ 行列および $4 \times 4$ 行列であれば広く知られた逆行列の公式があるが $S$ は $9 \times 9$ 行列であるためそれらを利用できない。 そこで、逆行列を解くことが出来るアルゴリズムである ガウスの消去法 を利用する。

ガウスの消去法についての説明は割愛するが以下に計算過程を記述していく。

計算過程をスキップ

ガウスの消去法：開始状態

前進消去

step 1: line 0 - line 1, line 0 - line 3

step2: swap line 1, line 2

step3: line 1 - line 3, line 1 - line 4

step4: line 2 - line 3, line 2 - line 4, line 2 - line 5

step5: swap line 4, line 7

step6: swap line 5, line 6

step7: line 5 - line 8

step8, step 9, step 10

後退代入

step1: line 8 - line 6, line 8 - line 4

step2: line 7 - line 5, line 7 - line 4

step3: line 6 - line 4, line 6 - line 3

step4: line 5 - line 3, line 5 - line 1

step5: line 4 - line 2

step6: line 3 - line 2, line 3 - line 0

step7: line 2 - line 1

step9: line 1 - line 0

ガウスの消去法：終了状態

$S^{-1}$ の導出

$S$ にガウスの消去法を用いて以下の通り逆行列 $S^{-1}$ を求めることが出来た。

石碑パズルの解法

リドルと解法の対応

$S^{-1}$ が導出され $\mathbf{h} = S^{-1}\mathbf{a}$ を求める事ができるようになった。 方程式を解く上での問題でリドルのゴールを全ての叡智の瞳に光を宿さないに組み替えたことを思い出してほしい。 そこで、リドルの解を求めるにあたって問題入力もそれに対応させる必要がある。 やることは単純でありすべての叡智の瞳の状態を反転させるだけである。

[問題の対応] Pattern.D を $\mathbf{a}$ 表現と解法への対応

パズルの解答導出

叡智の瞳の初期状態または現在の状態から $\mathbf{a}^{adjust}$ を入力しそれを左から $S^{-1}$ を掛けると $\mathbf{h}$ が導かれる。 その $\mathbf{h}$ が操作するべき叡智の瞳に対応したものとなる（操作する叡智の瞳の順序は順不同）。

[解答導出] Pattern.D を初期状態とし解答を導出する

ここで求まった $\mathbf{h}$ が 操作 するべき叡智の瞳であり若い添え字順に操作したのが e.g.4 パズル解答例になる。

JavaScript による実装

前項までで導出した解法を JavaScript によるプログラムに落としていく。 リドル（パズル）の解を得るのに最低限のもののみを実装することとし、ユーザーインターフェイスなどは省く。 ユーザーインターフェイスも含めたコード全文は recol.StelaiPuzzle.js に掲載されてる。 また、ここで作成した JavaScript の RECOL.StelaPuzzle モジュールと前述で示した recol.StelaiPuzzle.js には一部メソッドが欠落しているが最低限の範囲をこえるためである。

コーディング上のマイルールとして JavaScript の変数（定数扱い、フィールド扱い、メソッド扱いすべて含む）の先頭にアンダーバー _ があるものは外部から変更不可能なプライベート変数を指している。 アンダーバーのついていないものはたとえ定数扱いであれど、残念ながら外部から変更が可能であることを暗に示している。

定数の定義

前項までで求めた $S^{-1}$ を２次元配列の形で定数に定義。 プログラムで動的に求める事も可能だが石碑のサイズは $3 \times 3$ で固定であるためわざわざ計算コストをかけて求めることをせず定数として登録している。

var _SOLUTION_MATRIX = [
    [ 1, 0, 1, 0, 0, 1, 1, 1, 0 ],
    [ 0, 0, 0, 0, 1, 0, 1, 1, 1 ],
    [ 1, 0, 1, 1, 0, 0, 0, 1, 1 ],
    [ 0, 0, 1, 0, 1, 1, 0, 0, 1 ],
    [ 0, 1, 0, 1, 1, 1, 0, 1, 0 ],
    [ 1, 0, 0, 1, 1, 0, 1, 0, 0 ],
    [ 1, 1, 0, 0, 0, 1, 1, 0, 1 ],
    [ 1, 1, 1, 0, 1, 0, 0, 0, 0 ],
    [ 0, 1, 1, 1, 0, 0, 1, 0, 1 ]
  ];

叡智の瞳の状態を定数表現したもの。 setStela( 3, STELA_STATE.ON ); といった具合に外部からの状態操作に用いる。

var STELA_STATE = {
    OFF: 0,
    ON:  1
  };

配列（叡智の瞳）のサイズを保持。 配列のサイズは固定であるため for 文の継続条件用に定数登録。

var VECTOR_SIZE = 9;

フィールドの定義

叡智の瞳の数式表現で定義した $\mathbf{s}$ を表現したもの。 プライベートフィールド扱いであり、_stelai フィールドの操作は後述の setStela() メソッドで行う。

var _stelai = [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ];

叡智の瞳操作メソッド

_stelai フィールドのセッター。 座標 (position) や状態 (state) の型や範囲のチェックは行っていない単純なもの。 また、ユーザーインターフェイスを経由してマウスで１つ１つ設定することを想定しているので１度に１つの叡智の瞳しか操作できない。

var setStela = function ( position, state ) {
  _stelai[ position ] = state;
};

パズルの解を求めるメソッド

現在の叡智の瞳の状態（プライベートフィールド _stelai ）からパズルの解を求める。 入力はプライベートフィールド _stelai を参照するので入力は存在しない。 出力は叡智の瞳の方程式における $\mathbf{h}$ を戻り値とする。

var getSolution = function () {
  // 1. 内部変数宣言
  var COMPLEMENT_STELAI = ( function () {
      var cs = [];

      for ( var i = 0; i < VECTOR_SIZE; i += 1 ) {
        cs[ i ] = _stelai[ i ] ^ 1;
      }

      return cs;
    } () ),
    product = [];

  // 2. 処理本体
  for ( var i = 0; i < VECTOR_SIZE; i += 1 ) {
    product[ i ] = 0;
    for ( var j = 0; j < VECTOR_SIZE; j += 1 ) {
      product[ i ] += COMPLEMENT_STELAI[ j ] * _SOLUTION_MATRIX[ i ][ j ];
    }
    product[ i ] %= 2;
  }

  // 3. 戻り値
  return product;
};

１．内部変数宣言

var COMPLEMENT_STELAI = ( function () {
  var cs = [];

  for ( var i = 0; i < VECTOR_SIZE; i += 1 ) {
    cs[ i ] = _stelai[ i ] ^ 1;
  }

  return cs;
} () ),
product = [];

関数内上部に定義された内部変数 product は行列の積算結果を格納するための配列。 もう１つの内部変数 COMPLEMENT_STELAI は定数扱いでリドルと解法の対応で行っている動作と同様で $\mathbf{a}^{adjust}$ を求めている。実装上行っている処理は _stelai の各値に排他的論理和をとり値を反転している。 以下のように if 文などで行ってもよいが排他的論理和を用いる方が処理を効率的に行えるため採用している。

// alternative procedure #1
for ( var i = 0; i < VECTOR_SIZE; i += 1 ) {
  if ( _stelai[ i ] === STELA_STATE.ON ) {
    cs[ i ] = STELA_STATE.OFF;
  } else {
    cs[ i ] = STELA_STATE.ON;
  }
}

// alternative procedure #2
// STELA_STATE.ON が truthy であることを利用した if 文
for ( var i = 0; i < VECTOR_SIZE; i += 1 ) {
  if ( _stelai[ i ] ) {
    cs[ i ] = STELA_STATE.OFF;
  } else {
    cs[ i ] = STELA_STATE.ON;
  }
}

// alternative procedure #3
// 分岐内の処理内容が値代入のみなので #2 を三項演算子による書きかえ
for ( var i = 0; i < VECTOR_SIZE; i += 1 ) {
  cs[ i ] = _stelai[ i ] ? STELA_STATE.OFF : STELA_STATE.ON;
}

２．処理本体

for ( var i = 0; i < VECTOR_SIZE; i += 1 ) {
  product[ i ] = 0;
  for ( var j = 0; j < VECTOR_SIZE; j += 1 ) {
    product[ i ] += COMPLEMENT_STELAI[ j ] * _SOLUTION_MATRIX[ i ][ j ];
  }
  product[ i ] %= 2;
}

内部変数の宣言の続く二重 for 文が処理本体となる。 最後の一文は叡智の瞳の演算で定義した通り最後に偶奇（２の剰余）をとっている。 前述と for 文内先頭にある product[ i ] の初期化を除けば行列の積を求めているだけである。 本来の行列（正方行列同士）の積ならば以下のような三重 for 文になるが乗算行列の列数が常に１列なので簡略化している。

var n = [ VECTOR_SIZE ][ VECTOR_SIZE ],
    m = [ VECTOR_SIZE ][ VECTOR_SIZE ];

for ( var i = 0; i < VECTOR_SIZE; i += 1 ) {
  for ( var j = 0; j < VECTOR_SIZE; j += 1 ) {
    for ( var k = 0; k < VECTOR_SIZE; k *= 1 ) {
      p[ i ][ j ] += n[ i ][ k ] * m[ k ][ j ];
    }
  }
}

３．戻り値

直前の二重 for 文で求めた行列の積（一次元配列）を返却している。 ここで返却された値がパズルの解となる。

return product;

コード全体（実行可能コード）

前述までで断片的に提示したコードを１つのモジュール (RECOL.StelaiPuzzle) にまとめたもの。

/*jshint bitwise: false */

var RECOL = RECOL || {};

RECOL.StelaiPuzzle = ( function () {
  "use strict";

  // consts
  var _SOLUTION_MATRIX = [
      [ 1, 0, 1, 0, 0, 1, 1, 1, 0 ],
      [ 0, 0, 0, 0, 1, 0, 1, 1, 1 ],
      [ 1, 0, 1, 1, 0, 0, 0, 1, 1 ],
      [ 0, 0, 1, 0, 1, 1, 0, 0, 1 ],
      [ 0, 1, 0, 1, 1, 1, 0, 1, 0 ],
      [ 1, 0, 0, 1, 1, 0, 1, 0, 0 ],
      [ 1, 1, 0, 0, 0, 1, 1, 0, 1 ],
      [ 1, 1, 1, 0, 1, 0, 0, 0, 0 ],
      [ 0, 1, 1, 1, 0, 0, 1, 0, 1 ]
    ],
    STELA_STATE = {
      OFF: 0,
      ON:  1
    },
    VECTOR_SIZE = 9,

    // fields
    _stelai = [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ],

    // methods
    getSolution = function () {
      var COMPLEMENT_STELAI = ( function () {
          var cs = [];

          for ( var i = 0; i < VECTOR_SIZE; i += 1 ) {
            cs[ i ] = _stelai[ i ] ^ 1;
          }

          return cs;
        } () ),
        product = [];

      for ( var i = 0; i < VECTOR_SIZE; i += 1 ) {
        product[ i ] = 0;
        for ( var j = 0; j < VECTOR_SIZE; j += 1 ) {
          product[ i ] += COMPLEMENT_STELAI[ j ] * _SOLUTION_MATRIX[ i ][ j ];
        }
        product[ i ] %= 2;
      }

      return product;
    },
    setStela = function ( position, state ) {
      _stelai[ position ] = state;
    };

  return {
    VECTOR_SIZE: VECTOR_SIZE,
    getSolution: getSolution,
    setStela:    setStela
  };
} () );

このアルゴリズムの計算量

COMPLEMENT_STELAI を求めるのに VECTOR_SIZE $ = 9 $ 回の処理を行っている ($ = O(1) $) 。 また $S^{-1}$ と $\mathbf{a}$ との積を求める処理においても VECTOR_SIZE $ \times $ VECTOR_SIZE $ = 9 \times 9 = 81 $ 回の処理を行っている ($ = O(1) $) 。 よって $O(1) + O(1) = O(1)$ となり解を探索するなどの方法に比べて非常に高速にパズルの解を求めることができる。

参考文献

火が尽きそうだ
わしの話もちょうど尽きたな

ザックリー クラウドアトラス（映画）