おつかれさまでした。99.5%のケースで最適解が出ています。

盤面を分割して順に、焼きなまして消す…次を焼きなまして消す…を繰り返しました。最後2ブロックを多スタート。 pic.twitter.com/yERLy1TekY
— hakomo (@hakomof) 2018年4月26日

方針

私は焼きなまし厨なのでとりあえず焼きなましを考えます。

この問題の要求する解は消すペアとその順番です。その解そのものを（順番を含めて）直接焼きなますというのは難しそうです。なぜならあるペアを消すと新たにペアが消せるようになる、といった順序関係が強そうなので、順番を安易に変えると状態が壊れそうだからです。

そこで消すペアと順番を分けて考えてみます。消すペアの集合（消せる消せないにかかわらずすべてのマスをペアにしたもの）を固定したときの順番はどうなるでしょうか。これは以下のような簡単な貪欲で最適な順番、最適なスコアが求まります。

なので、

とすれば焼きなましに帰着できました！

近傍

同じ色のペアを2つ選んでつなぎかえます。マスAとBを消すペアとマスCとDを消すペアを、ACを消すペアとBDを消すペアに変えるといった感じです。

状態に制限がなく、近傍も小さいのでうまく焼きなませそうです。

ですが、先の貪欲はめちゃくちゃ遅いのでまともにまわりません。なので収束速度の底上げ・高速化をしていきます。

盤面を分割して順に焼きなまします。探索空間が小さくなり収束が速くなることが期待されます。消すペアは近いことが多いので局所的な焼きなましはあまりデメリットになりませんでした。

盤面は1-27分割しますが最後の2ブロックだけ多スタートします。

近傍は、消せないペアか他のペアをたくさん囲っているペアの中から選びます。他のペアをたくさん囲っているペアというのは、囲われているペアが先に消えることを縛っていて、それがたくさんということは大局的に良い状態ではない可能性があります。なので変更の候補です。

近傍のつなぎかえ先は（広義）近いマスほど高確率で選ばれるようにします。

先の貪欲は次のような言い換えができます。消すペアを頂点として、ぺアXを消してからでないとペアYを消せないときXからYに有向辺を張った依存グラフを、閉路の手前までトポロジカルソートすると先の貪欲と同じ結果が得られます。消せるペアを探す手間が省ける分こっちのほうがたぶん速いです。

評価値は、消せるペア数 - 依存グラフの最小閉路の数 / 2.5です。閉路以下のペアはすべて死ぬので閉路の数をペナルティとすると探索空間がなだらかになってよさげです。

依存グラフは差分更新します。更新が必要な辺は、変更する2つのペアに入出する辺だけなので、グラフ全体を毎回つくりなおさなくていいです。

依存グラフを差分更新するにあたり、新しいペアを囲うペアを列挙する必要がありますが、愚直にすべてのペアを走査すると遅いので、バイナリ空間分割という衝突している物体の列挙を高速にするアルゴリズムを使います。囲われていることと衝突していることは同じことなので転用できます。