お話しする内容：

自己紹介

概略

置換パズルの定義

Minkwitz factorization の解説

html canvas で作成したパズルの紹介

課題・目標・夢

自己紹介

松川信彦 (Matsukawa Nobuhiko)

大阪教育大学附属池田中学校数学科　常勤講師　→　なので所属が頻繁に変わる

生徒は全員 iPad 持参. web (google など) を介した教育活動が当たり前の学校

高等学校数学, 高等学校情報, 中学校数学教員免許所持

趣味：JavaScript などで計算代数や計算群論の実装し計算する. 数学の html canvas などによる可視化.

html canvas でパズルアプリや juggling simulator などを作る

好きな本：

　 　 　 　

概略（何がしたいのか）

html canvas による置換パズル UI の実装

計算機群論によるアルゴリズムによって置換パズルごとに「鍵」（Minkwitz data）を作る

置換パズルの任意のシャッフル状態から「鍵」によってそれを解くための手順を作成

これらをすべて JavaScript のみによって実行する

置換パズル(Permutation Puzzles)とは

有限の点集合 $\Omega$ 上の対称群を $\mathfrak{S}_{\Omega}$ と表す

有限の点集合 $\Omega$ とその点たちを着色する「色」を集めた集合 $C$ について

$a\in \mathrm{Map}(\Omega,C)$ に $\sigma\in \mathfrak{S}_{\Omega}$ が次のように右から作用

$a^{\sigma}(\omega^{\sigma}):=a(\omega)$ $(\forall \omega\in \Omega)$

これは $a$ によってに着色された小石 $\omega$ を小石 $\omega^{\sigma}$ の場所へ移動させることと解釈される

初期状態 $\iota\in \mathrm{Map}(\Omega,C)$ を一つとり

操作の集まり $\sigma_1,\cdots,\sigma_m\in \mathfrak{S}_{\Omega}$ を固定して

これらによって生成された群 $G:=\langle \sigma_1,\cdots,\sigma_m\rangle$ について

$\iota$ の $G$-軌道 $\iota^G$ がシャッフルされたパズルの状態全体であると考えられる

$\sigma\neq \tau$ であっても $\iota^{\sigma}=\iota^{\tau}$ となることがある!

従って, 以下では簡単のために

$C=\Omega$, $\iota=id_{\Omega}$ ($\Omega$ 上の恒等写像)

の場合についてのみ置換パズルおよびそのソルバーの構成について考察していく

即ち

$G=\langle \sigma_1,\cdots,\sigma_m\rangle \leq \mathfrak{S}_{\Omega}$ に対し $id_{\Omega}^G$ のみを扱っていく

$\Omega$ が $\Omega$ 自身によって着色されていると考える

注意点!

任意の状態 $a\in id_{\Omega}^G$ に対し $a=id_{\Omega}^{\sigma}$ となる $\sigma\in G$ が存在するが,

$a(\omega)=id_{\Omega}^{\sigma}(\omega)=id_{\Omega}^{\sigma}(({\omega}^{\sigma^{-1}})^{\sigma})=id_{\Omega}(\omega^{\sigma^{-1}})={\omega}^{\sigma^{-1}}$

となるので, 状態 $a$ は置換の逆元と見なせる.

初期状態 $id_{\Omega}$ を状態 $a$ に移す作用 $\sigma$ を定義するためには

逆元をとる操作が必要である

作用

任意の状態 $a\in id_{\Omega}^G$ に対し $a=id_{\Omega}^{\sigma}$ となるとき

$\sigma=\sigma_{i_1}^{\varepsilon_1}\cdots \sigma_{i_k}^{\varepsilon_k}$ $(i_1,\cdots,i_k\in\{1,\cdots,m\}.\ \varepsilon_1,\cdots,\varepsilon_k\in\{-1,1\})$

と分解されたとき

$id_{\Omega} =\left(id_{\Omega}^{\sigma}\right)^{\sigma^{-1}} =a^{\sigma^{-1}} =\left(\cdots \left(a^{\sigma_{i_k}^{-\varepsilon_k}}\right)^{\sigma_{i_{k-1}}^{-\varepsilon_{k-1}}}\cdots \right)^{\sigma_{i_1}^{-\varepsilon_1}} $

は状態 $a$ を初期状態 $id_{\Omega}$ に戻す操作となる

従って置換パズルを解くために $\sigma$ を元の生成系の積に分解することが必要であり

これを計算機群論的に実装することについて考察していく

Schreier's lemma

• 部分群の生成系を与える, 簡単ではあるが基本中の基本で重要な補題
• $G=\langle X\rangle$, $H\leq G$, $T$:$G$ における $H$ の右剰余類分解の完全代表系
• $G\rightarrow T\quad (\sigma \mapsto \overline{\sigma})$ を $H\sigma = H\overline{\sigma}$ なる写像とするとき
• $H=\langle tx\overline{tx}^{-1}\ |\ t\in T,\ x\in X\rangle$

Schreier-Sims Algorithm とは

• BSGS を求める方法
• BSGS = Base + Strong Generating Set
• 有限集合 $\Omega$ 上の対称群を $\mathfrak{S}_{\Omega}$ と表す
• 特に $\Omega=\{1,\cdots,n\}$ のときは $\mathfrak{S}_n$ と表す
• 以下では $G=\langle X \rangle \leq \mathfrak{S}_n$ とする
• Base とは $B = (b_1, \cdots, b_s)$ $(b_1,\cdots,b_s\in\{1,\cdots,n\})$ であって
• $G^{(i)}:=G_{b_1,\cdots,b_i}$ ($G^{(0)}:=G$) とおくとき
• $G^{(s-1)}\neq 1$ であるが, $G^{(s)}=1$ となるもの.
• $G=\prod_{i=0}^{s-1}G^{(i+1)}\backslash G^{(i)}$ と集合で表す方法
• $G^{(i+1)}\backslash G^{(i)}\simeq b_{i+1}^{G^{(i)}}$ はサイズが小さいから, 大きくなりがちな置換群において, 基底のような役割を演ずる.

Schreier-Sims Algorithm の困難

• $i$ が増えるに連れ Schreier's lemma によって構成される $G^{(i)}=G_{\{b_0,\cdots,b_i\}}$ の生成系は雪だるま式に肥大化する.
• $\rightarrow$ 何の工夫も施すことがなければブラウザは簡単にクラッシュ
• それを解消する手段として Jerrum's filter を用いる
• Jerrum's filter は $\mathfrak{S}_n$ の任意の部分群に対し, その生成系の大きさが $n-1$ 以下で抑えられることを証明するだけではなく, 具体的に実装することのできるアルゴリズム.
• $H=\langle X\rangle\leq \mathfrak{S}_n$ を任意の部分群とするとき, $\sigma\in X$ に対し, $i\neq i^{\sigma}$ となる最小の $i$ に対し $\{i,i^{\sigma}\}$ を辺とする無向グラフを作り,
• そのグラフから閉路を潰し, 木 (辺の数は $n-1$ 以下になる)にするグラフ理論的方法

Schreier-Sims Algorithm だけでは permutation puzzle は解けない

• Minkwitz の方法
• strong generating set をオリジナルの生成系の語として表示する方法
• Minkwitz の原論文を見て, (怪しいが) 一応実装できた
• JSによる実装の紹介
• JSによる実装の紹介(有限行列群への応用)
• Minkwitz の方法は実用的ではあるが, 原論文は7ページと短く, 群の表示, 項書換えに関して掘り下げた議論が見いだすことができなかった. (理論的な研究の余地あり？)

BSGS(+Minkwitz) の導出は時間が掛かる

• A24 (24 puzzle) の生成には標準的なノートPCで30秒ほどかかる
• 3x3x3 の rubik's cube では 3 ~ 4 分ほどかかる!
• 4x4x4 の rubik's cube では 16 時間ほどかかる!
• BSGS(+Minkwitz)は置換パズルの鍵なので solver の実装は鍵を使ってドアを開くだけの作業にすぎず, JavaScript であっても容易に実装でき, しかも負荷が少ない.
• BSGS の導出および Minkwitz 分解は鍵の鋳造にあたるので高コスト高負荷.

実演

課題と目標と夢

Minkwitz の理論を群の表示の手法 (coset enumeration など) から整理し理解を深める

面白い置換パズルの考察・実装（Klein quartic などのように）

rubik's torus, rubik's 立体射影 の完成

Schreier-Sims + Minkwitz の再構築・高速化 (Rubik's cube 群の計算は 4*4*4 が限界, やりっぱなしの実装を何とかする)

生活の安定・研究時間の確保