パズルプログラミングを支える技術
はじめに
こんにちは、わんどです。
ペンシルパズルをやっていて、
最近競技プログラミングも始めたが、実際にどうすればツールが作れるのかわからない
パズル×プログラミングに興味があるが何を学べば良いかわからない
などといった声を耳にします。
実際、ペンシルパズル特有のプログラミング技術などもあり、0から調べるにはコツがいるかもしれません。
この記事では、2019年現在のペンシルパズルを取り巻くプログラミング環境についての紹介を行っていきます。
今回取り上げるトピックの一覧
アルゴリズム
競技プログラミング頻出アルゴリズム
最適化系アルゴリズム
バックトラッキング
ビット演算
ライブラリ
SAT
Graphllion
AlgorithmX
フロントエンド
ES2015
WebAssemblyとEmscripten
ブラウザ描画
DOM
Canvas
ぱずぷれ
モバイル
iOS / Android
Unity
Apatche Cordova
バックエンド
アルゴリズム
https://gyazo.com/c2afd00f62fffcb8f43b2a791012017a
ソルバーやジェネレータを作る際にはアルゴリズムが欠かせません。
業務プログラミングであまり使わないのと対照的です。
パズルソルバ全般としては、
ルール適用＆手筋+バックトラッキングが基本
手筋検出部分でアルゴリズムを利用
純粋な探索ではSATソルバを利用するのが速い
といったイメージになります。
言語に依存しない話が多いですが、
一部ライブラリが言語に依存していたりする点に注意です。
競技プログラミング頻出アルゴリズム
https://gyazo.com/69d40b3b4e5cf995486c61cee6be5683
アルゴリズムの詳細は競技プログラミング系の入門に任せるとし、
パズルへの利用の話題を見ていきます。
グラフ系アルゴリズム
手筋検出部分で、盤面グラフに対する処理にアルゴリズムを利用することで
計算量を減らすことができます。
ソルバーはけっこういろいろなアルゴリズム使う 手筋の適用のところで DP とか Union Find とか lowlink とか Warshall-Floyd とかも出てくる
パズルソルバーにアルゴリズムを応用した例としては、準急さんの以下の記事などがあります。
DPの利用
また、最近では、今年のアドベントカレンダー16日目の記事で、にしなんとかさんが動的計画法を用いて探索を行なっていました。
最適化系アルゴリズム
https://gyazo.com/1bb2dc277b138af390ba5852f6bac5bc
厳密解を求めるのが難しい時、最適解に近いものを求めるための手法で、ペンシルパズルでは主に作問に用いられます。
競技プログラミングでもマラソン形式では、ビームサーチや焼きなまし法がよく使われます。
準急さんによる今年のアドベントカレンダー12日目の記事では、
また、ヒント数の少ない数独などの生成に遺伝的アルゴリズムなどの進化的プログラミングが用いられるケースがあるようです。
遺伝的アルゴリズムによって、四角に切れを作成する本です。
バックトラッキング
https://gyazo.com/bc8640671fa7647e330ee268f3fe6fda
バックトラッキングとは
埋まっていないところに適当に何かの数字を入れる(仮置き)
解き進める
ぶつかったらさらに別のマスに適当に数字を入れ、解き進める(多重仮置き)
矛盾が発生したら仮置きを一つ戻し、別の数字を入れる
を繰り返し、解に到達させる方法では
人間では全検と呼ばれるが、ソルバはルール＋仮置き探索のみで大抵のパズルを高速に解ききってしまいます。
競技プログラミング的な言い方をすると、盤面を戻すことに着目した、深さ優先探索と行った感じです。
例
以下の日本語で動作する数独ソルバは、バックトラックのみで解を出力します。
code: js
const 解答作成 = マスId => {
// 盤面が完成している
if (マスId === マスの数) { return true; }
// 最初から記入済の場合, 次のマスをチェック
if (記入済の(マスId)) { return 解答作成(次の(マスId)); }
// どれかの数字を入れて重複せず, それ以降も数字を記入することができれば
if (入る数字.どれか(数字 => !重複(マスId, 数字) && (盤面マスId = 数字, 解答作成(次の(マスId))))) { // 正しい盤面
return true;
}
else {
// そうでなければ盤面を消して一つ戻し, 他の数字をチェック
return false;
}
}
Bit演算
https://gyazo.com/75df427e14882b1bd0c48e403f3ba393
変数と聞くと、一つの数字を取り扱うイメージがありますが、
32bitや64bitの整数を32個ないしは64個の0と1の集まりと見て、
1bit単位での計算を行うことで、メモリの圧縮や高速化をはかることができます。
ペンシルパズル以外の分野では、将棋やチェス、オセロなどの探索に利用されています。
オセロの例
例えばオセロでは盤面サイズが8x8=64、
1マスの状態としては
何も置かれていない
白が置かれている
黒が置かれている
の3状態あり、
code: cpp
long long int black;
long long int white;
64bit変数が2つあればオセロの全状態を表すことができます。
パズルでの利用
将棋やオセロ、チェスと違い、ペンシルパズルでは盤面サイズが固定でないものも多いですが、
例えばハニーアイランドは通常一辺5、盤面サイズが61かつ、
盤面は塗るか塗らないかの2通りなので、盤面の状態を64bit変数 1つで表すことができ、Bitboardと相性が良いです。
ああそういえば、snukeさんに書いてもらったハニーアイランドのソルバを置いておきます。みんなも作ろう()
Snukeさんのハニーアイランドソルバ
残りサイズによる枝刈りのみで、20分ぐらいで全解(1304983)を出力してくれます。
数独での利用
数独も盤面サイズが9x9のものが出題されます。
高速数独ソルバとして知られるfsss2では
64bit変数を2つ組み合わせた128bit変数を用いて
81マスのうちの確定マス/未確定マスを表したり、
9変数からなる配列で、各マスの数独の候補数字をリストアップしたりしているようです。
Bitごとの論理演算で、行、列、ブロックの候補数字をまとめて消せるのが便利そうです。
数独に限らずソルバを極限まで高速化したい、という時には利用することになりそうですが、
一方で、単純にループとして使う場合には配列とあまり速度が変わらなかったりするため、要注意です。
その他
いくつかのパズルについては、バックトラックより高速なアルゴリズムが知られています。
とはいえ、
どれもざっくりと言うと探索の効率化と高速化を測るものになります。
以下のようなトピックがありますが、ここでは紹介のみに留めます。
ZDD / Graphllion
SAT / CSP / Sugar
SMT / SAT
Knuth's Algorithm X / Dancing Links
最近調べていたSATやZDD関連の論文へのリンクです
フロントエンド
https://gyazo.com/f4922f43d37014299da3454d19a4eee9https://gyazo.com/2a6c660c6bf4ea1d0b47692a2a7fbc58
この記事のメインです。
ブラウザ上でのパズルツールの開発について見ていきます。
ブラウザ開発はほとんど、WebAssemblyかJavascriptによって開発が行われます。
ES2015
ECMA Script 2015 (ES2015)とは、2015年に制定されたJavaScriptの標準規格で、
現在はES2019まで規格の策定が進んでいます。
ES2015以前と以後では、別言語の様相になるほど文法が変わっています。
例えば、以前のJavascriptで使われたfunctionやvarなどはES2015以降ではほとんど使う必要がありません。
これからJavascriptを勉強する人は、古い文法は無視して、ES6もしくはES2015以降対応のガイドを参照することを強く勧めます。
また、Javascriptのサンプルスクリプトも、ES2015以前のものと、以後のものが入り混じっているため学習には注意です。
参考リンク
どういった機能が追加されたかの一覧です。
最新のJavascript文法の紹介です
WebAssemblyとEmscripten
WebAssemblyはWebブラウザ上で動かすことのできるアセンブリ風言語で、高いパフォーマンス
また、Emscriptenを利用することで、コンパイル言語をWebAssemblyに変換し実行することができます。
Emscripten
C++やRustなどで書かれたコード(厳密にはLLVMというコンパイラ基盤で動くコード)をWebAssembly (wasm)やJavascriptに変換するコンパイラです。
ゲームなど、高速な処理が求められる処理などで使われる技術ですが、
パズルプログラミングでもソルバやジェネレータなどで計算能力を必要としたり、
上記のアルゴリズムの実装がC++などのコンパイラ型言語で書かれることが多いので有用で、
実際、近年、割とパズル関連ツールでの使用実績も多いです。
使用例
ブラウザで解けるポリオミノソルバ
Knuth's Algorithm X & Dancing Linksが最速ですが、Z3ソルバはwasmを利用しています。
ブラウザで解けるナンバーリンク ソルバ
内部で動いているSATソルバである、minisat.jsはminisatをemscriptenでjsにコンパイルしたものです
準急さん(@semiexp)のナンバーリンクジェネレータ
emscriptenを利用し、ブラウザ上で動いています。
参考記事
ブラウザ描画周り
昔使われていた、FlashやJavaアプレットは現在動かない環境が多く、
Unity+WebGLなどはパズルプログラミングにはオーバースペックでしょう。
また、近年、Webサイト作成によく使われるSPAフレームワーク(React.jsやVue.js)も、Webサービス向けであり、パズルなどのWebアプリ向けではなため、今回は説明を割愛し、
DOM、HTML+Canvasについて説明していきます。
DOM
https://gyazo.com/ca8ce7357e6ca484d94bebbff6ba61b0
HTMLタグで括られたHTML要素のことです。
多くのWebサイトで使われているはずですが、
パズルとはあまり親和性が高くないのか、メイン部分での使用頻度は高くないです。
数独練習ツール（ラストワン数独）
上のボックスから抜けている数字を見つけてタップします。
正しい数字をタップするとボックスが赤く光ります。
Canvas
など、使用例多数の描画APIです。
画像を表示できるため、様々なゲームに使われるほか、
Twitterでの動画でおなじみのじゃがりきん(@jagarikin)さんの開発ツールも
Javascript+Canvas
となっていたり、メディアアートなど、様々な目的に利用されています。
ゲーム開発では画像を動かすことが多いですが、
パズルでは文字表示や線を引く機能など、素の機能もよく使います。
ぱずぷれ、ペンパくんでの採用など、Webでのペンシルパズルツール開発には欠かせない技術となっています。
参考リンク
ぱずぷれ
https://gyazo.com/e0b08e80614c8105382ff323aac605ee
ぱずぷれライブラリ自体を組み込んだツールはあまり見かけませんが、
ぱずぷれは外部からの利用や拡張性が高く作られており、
ぱずぷれのURLを読み込んでソルバに解かせる
ぱずぷれを拡張して自作のパズルや未対応のパズル、バリエーションに対応させる
ソルバや自動生成の出力盤面をぱずぷれで表示 (リンク or 埋め込み表示)
など、
うまく利用すればパズルツール作成の手間を大きく削減することができます。
というわけで、独立項目として紹介します。
ソースコード
ドキュメントが英語で書かれています。
使用例
URLの取得および盤面の描画に利用しています。
ぱずぷれのURLを呼んでいます（ライブラリとして使っているわけではないようです）
導入方法
19/12/21追記 導入方法の記事を作成しました
モバイルアプリ開発(iOS/Android)
https://gyazo.com/8ef3b8e0ad813f1e29f9f98782cf8ea1
あまりTwitterでは話題になりませんが、
アプリで自分の作ったパズルを遊びたいといった需要もありそうです。
ツール系はiOSであれば Swift、AndroidであればKotlinで開発されることがが多いですが、
以下のような手段もあります。
Apatche Cordova
https://gyazo.com/7473b371828513e324d69be961e0b338
HTML+Javascriptで開発のできるモバイルフレームワークです。
Webサイトの形で作ったアプリケーションをほぼそのままのコードで、
iPhone / Androidのアプリにすることができます。
類似ライブラリは色々ありますが、
昨年、本業にて、「Webサイトとして既にリリースしている状態で手っ取り早くアプリを作るには」という技術選定のもと、
チョイスしたので、おすすめできるのではないかと思います。
参考リンク
公式ページです
Unity
https://gyazo.com/42520d07b5f451227207a74b4c58483e
ゲームエンジンです。3Dですが、2Dゲームの開発もできます。
2Dで線を引いたりなどの原始的な機能も一応用意されているため、
モバイル開発であればギリギリ選択肢になるかもしれません。
参考リンク
公式ページです。
バックエンド
https://gyazo.com/ec93cf945adba372b525ec40f91b0a6b
パズルスクエアやコンテストサービスなどのWebサービスの作成などに必要となる技術です。
こちらも、パズルに限らない一般的なWebサービスの開発を参考にするのが良さそうです。
例えば、パズルスクエアや謎解き王トーナメント2014-2016はPHP+MySQLですし、
謎解き王トーナメント2019の構成にはFirebaseが使われています。
また、アルゴリズムのパートで開発したプログラムをサーバー側で動作させるのにも使われます。
サーバー側で処理するため、処理負荷の問題などは発生しますが、
自由な言語・構成で開発ができるなどの利点があります。
例えばみゃーみゃさん(@3892myamya)さんのペンシルパズル ソルバーはHeroku+Javaの構成で動いているようです。
ペンシルパズル ソルバー
ソースコード
構成例や言語は様々なので、詳しい説明は今回割愛します。
最後に
網羅的に書いたつもりですが、Webサイトホスティングについての記載がなかったり、
具体的な使い方は公式ドキュメントのリンクや検索任せにしているなど、
この記事自体は雰囲気やとっかかりとしての役割でしかないと思っています。
気になった点や個別の技術相談等は@wand_125までお願いします。
実際にツールを作ってみようと思い立った時に、読み返したりできる記事になれば良いなと考えています。
ここまで読んでいただきありがとうございました。