お話しする内容：

概略

置換パズルの定義

Minkwitz factorization の解説

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

課題・目標・夢

概略（何がしたいのか）

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

計算機群論によるアルゴリズムによって置換パズルごとに「鍵」（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 分解は鍵の鋳造にあたるので高コスト高負荷.

実演

課題と目標と夢

細かい調整（任意のシャッフル状態をアニメーションを経由せずに表示したりなど）

面白い置換パズルの考察（双曲群, モジュラー群とかで置換パズル的なものを考えられないか）

Schreier-Sims + Minkwitz の高速化 (Rubik's cube 群の計算は 4*4*4 が限界)

研究時間の確保