srm 498 div2 hard NinePuzzleの解説

本番では、解き方が分からんかったんだけど、やっと分かったのでメモ。
このパズルでは、以下のように具体的な手順で、任意の状態から任意の状態に遷移出来ることを証明する。http://www.topcoder.com/stat?c=problem_statement&pm=11225&rd=14427にある図で、0 1 3 6 7 4 8 9 5 2 という閉路に沿って空白を動かすことを繰り返すと、0に任意のタイルを運ぶことが出来る。次に、1 3 6 7 4 8 9 5 2 という閉路に沿って空白を動かす事を繰り返すと、6に任意のタイルを運ぶことが出来る。以下、同様に、常に残りのタイルだけで閉路が出来るよう留意して順番を選びながら各場所に指定された色が来るようにすれば良い。