🧩

ルービックキューブのソルバーを書いた, wasm で動かした

2022/09/12に公開

パズル

ルービックキューブ

スピードキューブ

idea

はじめに

はい.
暇な時間があるようになったのでルービックキューブを手に入れて遊ぶようになった. 一秒でも早く回しやすくアワヨクバ覚えやすい手順をネット資料で漁るうちに, 自分でも発見したくなったのでソルバーを書いた.

成果物

https://github.com/cympfh/cube

これはただの cargo プロジェクトなので, レポジトリをクローンしてきたら cargo run したら動くし, cargo install --path . すれば cube というコマンドとしてインストールされる.

cube は初期状態（混ぜた状態）とゴール状態（解いた状態）を与えたら, 初期状態をゴール状態に持ってくまでの手順を出力する. 初期状態の代わりにスクランブル（混ぜ方の手順, つまりゴール状態から初期状態までの手順）を与えることもできる. 当たり前だがスクランブルは初期状態を作るのにだけ使い, ソルバーはこれを参照しない.

これ（左が初期状態, 右がゴール）を入力すると, U'DD を出力する

回転記号

ここで U とか D は回転記号と呼ばれるもので,

これが詳しい.
要するにキューブ状態へ作用する操作を表している.
明らかにこれらは有限群を成す. 何も操作しないことが単位元で, 逆再生することが逆操作になっている. D に対する逆元のことはプライム記号を用いて D' と書く. 二回続けて適用することは D2 などと書く（これは DD と同じだし特に文字数の節約にもなってないので cube は気にせず DD と出力する）. 基本的に U とか D みたいに大英文字一つだったら「記号が示すある面を前に持ったときに, 90度時計回りに回す」を意味する. プライムがついたら反時計回りに90度, 2 がついたら180度だ.
記号を並べて合成（積演算）することができる. 左から順に適用する. UU' は U してから U' する（これは何もしないことと等しい）.

上のリンクにはとりあえず全操作があるわけだが, 実際には全て使うわけではない.

回す意味がない
- すでに揃ってるところを壊してしまう場合
回しにくいから使いたくない
- 右利きの人間にとっては右側の操作 R とか Rw (r) は回しやすい
- B とか E とかは利き手に限らず回しにくい

教訓. 操作を絞って解くべき

成果物2

デモンストレーションとして, cube の一部の機能だけを wasm としてビルドして, web ページから使えるようにした.

https://cympfh.cc/cube

これは実態としては github pages で公開されているに過ぎない. wasm なので当然ブラウザ上でソルバーを動かすことになる. せいぜい一秒程度で完了する探索だけを公開してる.

二通りの解法, URF (URF 及びそれらの逆元だけで解く) と Roux Method という方法での解法を示してる. URF の方はそもそも解けない場合もある. Roux Method は一般の解法なので何でも解ける. 大抵 50 手前後の解法が一秒程度で出力される.

探索

cube は大きく三種類の探索APIを提供している. ただの探索と Roux Method と CFOP Method. 後者2つは内部で探索を繰り返ししまくるだけなので, 先に探索パートを話す.

基本的にはただただ幅優先探索を行う. 回転記号のパートで延べたように, 適用する操作を絞っておくことが重要だ. 探索は予め適用可能な操作の集合を固定して与える. 操作が $M$ 種類, 探索の深さが $N$ だとすると探索空間の広さは $O(M^N)$ ある. 幅優先とはいえ最悪これだけ時間が掛かると見積もっておかないといけない.
うげっ, 指数時間じゃんと思うだろうがこの $N$ は実は大きくない.

どんな状態からでも20手以下で解けることが示されている. というわけで $N \leq 20$ と思うことにする.（これは嘘で, 20 というのはすべての操作を許した場合であって, 今回は違う.）

Roux Method の話をするか. Roux Method はあんまりメジャーではない, が興味深い解法だ.
この方法の後半では次の状態を目指す (CMLL という手順を終えた状態).

ここで灰色は何でもいいことを表している. 色がついてる部分がすでに正しく揃ってることを表す. 図では隠れてるが左右対称で, 左もいい感じに揃ってるとする. この後は, U と M という2つの操作だけで揃えてく. この操作では今揃ってるところは回さないので壊れない.

操作が二種類, ただし逆元も使うので全部で $M=4$ となる. $M,N=4,20$ のときに $M^N \fallingdotseq 10^{12}$ . 少しまだ大きいが, 決してスーパーコンピュータを持ってこないと行けないレベルではない数字だ.

ただの幅優先探索を双方向にする. スタートからもゴールからの幅優先探索を行い, 2つの探索が初めてぶつかった地点をつなぐ方法だ. これを行うだけで探索深さが半減する. $O(M^N)$ だったのが, $O(M^{N/2})$ になるわけだ. $M,N=4,20$ のときに $M^{N/2} \fallingdotseq 10^6$ . これは家庭レベルのコンピュータにとってなんてことなく小さい.

小さい工夫

同じ回転を三回以上適用することは無意味. U3 は U' と同じ. 同じ回転は二回までしか繰り返さないという制約をつけられる. しかも U' を二回適用するのは U2 と同じ. プライムの操作は二回繰り返してはいけない. キャンセル可能な操作は適用しない. U したあとに U' するとキャンセル（打ち消す）するだけなので探索する必要がない.

Roux Method, CFOP Method

本来のルービックキューブは六色（Yellow, White, Red, Orange, Green, Blue）と決まっている. しかし探索においてはこれを拡張すると便利だ. 七色目（なんでもいいが仮に灰色としよう）を付け加える.

例えば Roux Method の第一ステップでは次の状態を目指す.

色がついてるところを揃えるのであって他の部分（図の灰色の箇所）は「今はまだなんでもいい」を表す. 何でもいいのだが, 本当に灰色にしてやっていい. 初期状態からも適切に色を灰色に変えてやる手間が生じるが, それでもキューブの状態が一気に減る（色が減るんだからそりゃそう）という最大のメリットがある.

Roux Method, CFOP Method はどちらも大体このようにサブゴールがいくつか設けられていて, その手順に従うと少しずつ探索空間が小さくなってく. その点で同じだが, Roux のほうが一気に小さくなるので良いね.
CFOP は F2L も OLL も PLL も全部それなりにでかい. Roux は CMLL と LSE とでコーナーとエッジを完全に独立に解いてるので探索空間をちょうど2つに分けた形になっているのが強い.

wasm

コマンドラインで動く cargo プロジェクトが出来たので, これを wasm ビルドして web ページで公開する.

フロントエンド側のことは詳しくないが Rust 側は定番の組み合わせで wasm-bindgen と wasm-pack を使う. wasm-bindgen は crate ライブラリなので Cargo.toml に書き足して, lib.rs で

use wasm_bindgen::prelude::*;

/// これがエクスポートされる
#[wasm_bindgen]
pub fn solve() {
  // なんかやる
}

wasm-pack はコマンドラインツールなので rustwasm.github.io/wasm-pack/installer/ にしたがってインストールする. cargo プロジェクトのルートディレクトリで wasm-pack build --target web と叩くと wasm ビルドされる. デフォルトだと pkg/ ディレクトリが出来てその中に生成物が出力される.

フロントエンドは svelte で書いた. App.svelte から

import init, { solve } from '../pkg/'

init();

とする. pkg は wasm-pack で生成されたディレクトリ. solve は Rust で #[wasm_bindgen] 付きでビルドした関数名. init はなんか wasm を初期化するための関数らしい. 適当なタイミングで init() を実行してからインポートした solve() が使えるようになる. たぶん init は非同期で実行されるので直後に solve() すると実行エラーが出る.