最終的な駒の配置を決め打った際に，その配置が実際に可能であるか判定してみます．

これは， \(2\) 部グラフのマッチング問題と等価であることがわかります． つまり，左側に駒の初期位置に対応する頂点，右側に駒の最終位置に対応する頂点を作り，駒が移動可能なペアについて辺を貼ったグラフを考え，このグラフに完全マッチングが存在するかどうかを判定すればよいです．

完全グラフが存在することは明らかに必要条件です． また十分性は，次のように示せます． まず，任意の完全マッチングを一つ得ます． このマッチングに従って，駒を動かしていきます． 駒が衝突する場合が問題になります． そこで，移動先のマスにある駒を，先に動かしてしまうことにします．移動先の駒がもう動かないという場合は，今動かそうとした駒と目的地を入れ替えることで，何らかの動きをすることになります．先に動かそうとして衝突が発生した場合は，その移動先にある駒を更に先に移動させて・・・と再帰的に行うことができます． 結局，駒が衝突しない操作方法が得られることになり，十分性が示せました．

操作回数を最大化しましょう． これは，最終目的地のマスの行番号と列番号の和を最大化する問題です．よって，上記の最大マッチング問題を変形し，最小費用流の問題にすることで，解くことができます．

駒の個数を \(K\) とおきます． グラフの構築を愚直にやると，\(O(K+NM)\) 頂点 \(O(KNM)\) 辺のグラフができます． これでも解くことは可能ですが，元の盤面をグリッドグラフとみなしてその形を利用すると，\(O(NM)\) 頂点 \(O(NM)\) 辺のグラフの最小費用流の問題になります． よってこの問題は，\(O(KNM\log(NM))\) 時間で解くことができます．