ポリオミノを自動で解く「ポリオミノソルバー」を作ってみた
2022年06月23日
アルゴリズム
beespiel.net
github.com
ポリオミノソルバーの紹介と実装周りの話。
ポリオミノソルバーとは
ポリオミノを自動で解くことができる Web サービス。
ポリオミノソルバー
ポリオミノソルバーはポリオミノを自動で解くことが出来るWebサイトです。回転・反転にも対応していて、答えの総数を出すことが出来ます。
なぜ作ろうと思ったか
時々謎を作るんですが、ポリオミノ関連の謎を作ったときに別解を調べるの大変だ！となったのがきっかけ。
色々調べても Web で解の個数まで表示してくれるものが無かったので、じゃあ作るかとなった。
実装周りの話
repo はこれ。
GitHub - kontotto/polyomino
Contribute to kontotto/polyomino development by creating an account on GitHub.
README は書いていないのでもし使いたい方いたら連絡してください！ テストだけは無駄に書いています。
言語は TypeScript で npm で install 出来るようになってます。
肝心のアルゴリズムとしては、下記技術を使っています。
- Knuth’s Algorithm X → exact cover problem を効率的に解くアルゴリズム
- Dancing Links → 双方向リストのデータ構造
ここら辺に関してはもっと詳しい人が書いてくれているのでそちらをご覧ください。
UI 周りは Vue を使って頑張って作ってます。正方形を描画するのが地味に難しかった。
今後やりたいこと
今回は問題を解く側のプログラムを作りましたが、逆に問題を作る側に興味があります。
ポリオミノの難しさを定義することが出来れば自動で問題を作ることが出来る気がするのでその内作るかもしれません。
おしまい。