競プロ勉強メモ

Daily Akari を ZDD で解く話

はじめに

Daily Akari というパズルがあります。

ルールを見た瞬間、ZDD で解けるなぁと思ったので、解きました。

ZDD が何かについては、過去記事を参照してください。(全3部)

過去記事↓

ZDDと8-Queen problemの話【卒研お勉強枠①】 - 競プロ勉強メモ

ZDDによるN-Queen problemの解法を効率化する話（卒研お勉強枠②） - 競プロ勉強メモ

ZDDでマインスイーパーを解く話（卒研お勉強枠➂（最終回）） - 競プロ勉強メモ

Daily Akari のルール

グリッド上に「空きマス」、「ブロック」、「数字付きブロック（以下、書かれた数字が $x$ のとき、 $x$ -ブロックと呼ぶ）」が配置された盤面が与えられる。
任意の空きマスには「灯り」を配置できる。灯りは上下左右方向のブロックに遮られていない空きマスを全て照らす。
以下の条件を満たすように灯りを配置出来ればクリア。
1. 全ての空きマスを照らす。
2. 全ての $x$ -ブロックについて、隣接する上下左右の空きマスに灯りをちょうど $x$ 個配置する。
3. 灯りは自身以外に照らされてはならない。

Daily Akari プレイ画面

クリア例

ZDDで扱える形への帰着

$x$ -ブロックは卒研で扱ったマインスイーパーと全く同じなので処理できるとして、他の2ルールについても次のように「空きマスの部分集合に対する個数制限」の形で表現できます。（下記は、以下 条件A, B, C と呼びます。）

全ての空きマスについて、上下左右方向のブロックに遮られていない空きマスに灯りを少なくとも 1 つ配置する。
全てのブロック（グリッド左端の壁を含む）について、右方向にあるブロックに遮られていない空きマスに灯りを高々 1 つ配置する。
全てのブロック（グリッド上端の壁を含む）について、下方向にあるブロックに遮られていない空きマスに灯りを高々 1 つ配置する。

まあ実質マインスイーパーですね。（個人の感想）

空きマス全体を台集合として、べき集合を表す ZDD （0-枝と1-枝を順に繋げていくだけ）を構築しておきます。

あとは、ZDDでマインスイーパーを解く話（卒研お勉強枠➂（最終回）） - 競プロ勉強メモで紹介した $\text{hint}$ 演算や、それをヒント数字「以上」・「以下」に対応させた演算 $\text{hint_ge}$ 、 $\text{hint_le}$ を適用しまくれば解けます。やったね。

ソルバーの実装例

githubに置いときます。

ちなみに

ルール説明時に貼っていた問題は唯一解らしいです。

※ 頂点の数字を9で割ったときの商と余りがグリッドの座標に対応。青辺を通る時そのマスに灯りを配置する。

ルール説明時の問題に対してソルバーが構築したZDD

高速化について [追記：2025/04/12]

本解法は、盤面が大きくなるほど内部で構築される ZDD の節点数が指数的に増え、計算時間もメモリも爆増します。

しかし、ZDD の特徴として、演算の順序だったり組合せだったりを適切に決めることで同じ問題でもいい感じに節点数を抑えられることが知られています*1。そういったチューニングについては、思いつき次第追記していこうかなと思います。（データ集計とかは面倒なので、体感でよくなってそうなのを書きます。）

条件A について、「少なくとも 1 つ」ではなく「1 個以上 2 個以下」に制限し、 $\text{hint_range}$ 演算で処理する。[追記: 2025/04/12]

*1:卒研解説記事の第2部でも触れています。