テトリスの地形を与えると、その地形がどんな置き方によって作れるかを逆算してくれるツールです。 つまり、テトリス用に特化したポリオミノ敷き詰め問題解答ツールです。
https://shohei909.github.io/tetromino_tiling_solver/
から利用できます。
テトリスのテンプレなどを考える上で逆算という手法がある。
例えば、3巡目の開始時時点での良い地形を考えてから、その地形を組める1巡目と2巡目を考える。
solution-finder のような地形与えるとその組み方とセットアップ率を出してくれるツールはあるが、速度的には1巡程度の逆算が限界で、2巡分を逆算しようとすると相当な時間がかかる。ライン消去やセットアップ確率を出さない代わりに、2巡・3巡分の置き方をリストアップしてくれるツールを作りたかった。
このツールを作る上で考えたアイデアのメモです。アイデアのメモなので、すべてが実装に反映されているわけではありません。
二つの領域が分割されているかを判定する。
完全に分割されているなら適当な灰色マス1を選んで、深さ優先探索(DFS)してつながっている範囲を見つければひとつながりのグループが取得できる。これがグループ分けがしてないマスが無くなるまで繰り返す。
関節点を見つけて領域を分割する。この場合の関節点とは、そのマスを削除したら領域が分割されるようなマスを指す。これは lowlink 法で見つけられる。
- 間接点を削除した時に生まれる2つの領域のうち片方の領域がちょうど 4 の倍数のマス数だった場合、その境界で領域を分割して良い。
- 間接点を削除した時に生まれる2つの領域のうち片方の領域が、4 の倍数 - 1マス だった場合、の最大で3通りの分割ができるので、3通りの分割を行って問題を場合分けできる。
- 元の領域マス数が4の倍数なら、上記のどちらかに当てはまる
ある領域のサイズが4の倍数でなかった場合、その領域を埋めることはできない。
領域のマス数を 4N としたとき、ceil(N / 7) 巡目のミノまでを使用して埋める。このとき、最後の1巡のミノは使っても使わなくても良いミノ、それ以前のミノは必ず使用するものとしてあつかう。
各ミノの使用回数の上限下限リストと、領域分のミノ数が決まったので、使用するミノとしてのありうる組み合わせを全列挙する。これは深さ優先探索で出来る。
領域が対称なら1つだけミノの向きを制限する。この時利用する対称性は180°ごとの点対称性と90°ごとの点対称性。ミノにも対称性があるので、この時向きの制限をするのは、なるべく対称性の低いものとする（T・L・J → I・S・Z → O の順）
SMTソルバーのZ3を使用して解く案。
前提として、ミノ内の4つのブロックを分けて考える
基本的な変数は
- ミノ内の各ブロックの位置を表すX座標・Y座標の変数。(2 × 4 × ミノ数の変数)
必須の制約は
- 有効な領域の座標は、ミノのブロックの XY 座標のうち 1 つだけと一致する
- 同じミノ内のブロックの XY 座標の関係性が、ミノの回転によって生まれる 4 種類の形状のいずれかに一致する
対称性を除去する制約は
- 同種のミノはIDの若いミノの方がXY座標の値が小さい
実装した結果、遅かったのでボツ。4×6 の敷き詰めに対して、8秒程度かかっていた。
SATソルバー、例えば splr を使って解く
ミノ内の4つのブロックを分けない
- 変数はあるマスに特定の種類のミノが存在しているかの Bool (ミノの数×マス数)
必須の制約は
- あるマスに存在しているミノは一つ
- ミノごとに有効な配置方法を全列挙して、そのいずれかが満たされること
- 無効な配置方法が枝刈りできるのが強そう
対称性を除去する制約は簡単には張れなそう
案3が十分に高速だったので、未実装
Algorithm X + Dancing Links（DLX）を使って解く。
- 種類が同じ複数ミノは行はまとめる。行は残りミノ数を使いきったら削除する。
- 同じミノが複数回使用可能な場合、領域の対称性の利用がしづらい
- 各種類ごとに種類を表すダミー列を用意する
- 埋めるべきマスをすべてリンクした行を用意し、その行が空になったら完了（=ヘッダー行）
- ここにリンクしないことで、覆わなくても良いマスを表現できる
- バックトラックは列の要素すべて試しても、その列が削除できなかった場合
前述の案2や案3では、1ミノの置き方を全通りリストアップする過程がある。この1ミノによって領域が不正に分割されていないかのチェックを行って、不正に分割されてたら、その置き方を除外する
- ① あらたに置いたミノの周囲にある空きマスをチェックし、それらマスの周囲に空きマスが一つもなかったら枝刈り
- ② バックトラックが発生したときに、領域どのように分断されてるかをとってくる。すべての領域のサイズが4の倍数になるところまで、一気にバックトラックする
- 毎ステップ領域が分断されたかを判定するのは大変。動的木でO(logN)で判定できそうだけど実装が難しい
- 逆に領域がくっついたかどうかは、バックトラックで戻したミノの周囲をみて、別の番号が降られていたら、それらの番号の領域がくっついたと判定できる
- 分断後の領域について、どの領域がすでにくっついたかは UnionFind 木で管理
- 分断された領域ごとのパリティを計算する。市松パリティでTミノの必要数、縦パリティでLJTミノの必要数がわかる
① の実装は簡単だが、②を実装してしまえば ① の必要性はわりと薄そう
分割した領域や使用するミノの組み合わせごとで、問題を分割してあるので並列化が可能
分割した問題を解決していく過程で、そこまでで使用したミノとフィールドの形状が一致する場合がある。この際、その後の問題を重複して解かないように、ミノ・フィールドからキーを作って、途中までの解答を辞書に格納していく
ある領域へのミノの敷き詰めを考える場合に、特定のミノの組み合わせでは絶対に領域の敷き詰めができないことを、パリティを用いた2種類の制約で判定できる
（ここではライン消去は考えない場合の話をする）
ある地形を敷き詰める場合、Tミノ数は市松模様の塗り分けに対して、2種類の制約を両方満たす必要がある
塗り方： https://fumen.zui.jp/?D115@AhAtg0Atg0Feg0Atg0AtFeAtg0Atg0Feg0Atg0AtMe?AgH
ここでは、ある地形を青と赤の市松模様で塗り分けたときの 「(青マス数-赤マス数)の絶対値 / 2」 を 「市松パリティの偏り」 と呼ぶことにする
- 制約① 市松パリティの偏りの偶奇と、Tミノの個数の偶奇は一致する。
- 制約② 市松パリティの偏り <= Tミノの個数
ある地形を敷き詰める場合、LJ・T縦・I縦の数は縦縞の塗分けに対して、2種類の制約を両方満たす必要がある
塗り方： https://fumen.zui.jp/?D115@AhAtg0Atg0FeAtg0Atg0FeAtg0Atg0FeAtg0Atg0Me?AgH
ここでは、ある地形を青と赤の縦縞で塗り分けたときの 「(青マス数-赤マス数)の絶対値 / 2」 を 「縦パリティの偏り」 と呼ぶことにする
- 制約① 縦パリティの偏りの偶奇と、Lミノ+Jミノ+T縦の偶奇が一致する。
- 制約② 縦パリティの偏り <= Lミノ+Jミノ+T縦+2×I縦
ある地形を敷き詰める場合、LJ・T横・I横の数は横パリティに対して、2種類の制約を両方満たす必要がある
ここでは、ある地形を青と赤の横縞で塗り分けたときの 「(青マス数-赤マス数)の絶対値 / 2」 を 「横パリティの偏り」 と呼ぶことにする
- 制約① 横パリティの偏りの偶奇と、Lミノ+Jミノ+T横の偶奇が一致する。
- 制約② 横パリティの偏り <= Lミノ+Jミノ+T横+2×I横
ここでは、①を偶奇制約、② を閾値制約と呼ぶことにする。 閾値制約については縦横市松以外の塗分けでも使用できる
塗り方： https://fumen.zui.jp/?D115@+gh0Bth0BtBeBth0Bth0Beh0Bth0BtBeBth0Bth0Ke?AgH
- このパリティの偏り <= T+L+J+S横+Z横
- I・O・S縦・Z縦は0変動
- S横+Z横は必ず1変動する
- T、L、Jは置く位置によって、1変動か0変動かが変わるので、偶奇制約について考えるのは面倒
同様に縦長市松パリティもある
塗り方: https://fumen.zui.jp/?D115@rgBth0BtDeAth0Btg0Deh0Bth0Deg0Bth0AtDeBth0?BtDeAth0Btg0LeAgH
- ①偶奇制約: TJLが無い場合、このパリティ偏りの偶奇はO数の偶奇は一致する
- ②閾値制約: パリティの偏り <= O+T+L+J+2×S+2×Z
- Iは0変動
- Oは1変動
- TJLは0か1変動
- ZSは0か2変動
塗り方: https://fumen.zui.jp/?D115@/gxhRpxhDexhRpxhDeRpxhRpDeRpxhRpLeAgH
このパリティの偏り <= T+L+J+S+Z+2×O
- Iは0変動
使える例: https://fumen.zui.jp/?D115@tgh0Heh0Feh0Bth0Deh0Bth0Feh0Heh0NeAgH
この地形は偏り6で5ミノなので、Oが1つ以上必要
4色・16色パリティで閾値制約ってあるの？
地形が二つに分断されてる場合、地形①の偏り+地形②の偏りの2つで合算してから、閾値制約を判定すれば良い。横長市松パリティのように偏りの取り方が複数ある場合は、それぞれでもっとも偏りの大きくなる取り方を合算して良い