格子ガス

格子上を粒子が拡散する。各粒子は第一、第二近接サイトに他の粒子がこれないような反発力があるとする。粒子数の一乗に計算時間が比例する方法を考案せよ。
ゲームとかで、グリッド上を2x2とか3x3マスの大きいキャラが重ならずに動く場合の効率的な判定、と言い替えてもいい。