水玉つぶし

水玉つぶしが実は NP-Complete にみえる。
http://d.hatena.ne.jp/nuc/20060217/p1

水玉つぶしというのを以下のように定義する。
ある正方格子の上に、有限の1〜4の数字(水玉)が散らばっている。数字の書いていない格子があってもよい。
数字に水滴をあてると吸収され、それは1増える。5になった瞬間に爆発し数字がない格子になりに四方に水滴を飛ばす。また、飛ばされた水滴は一定速度で別の数字に当たるまで一定速度で進む。
「いくつかの水玉に水滴を与え、十分な時間待つ」という手順を繰り返し、すべての数字を消滅させる。

具体的な問題設定は、指定された n箇所をどの順で水滴を与えれば、すべての水玉がつぶれるか。
ちゃんとやっていないけれども、どうも And Or Not が構成できるから、SAT が表現できまして。