適当に１ターン動かすと

状態Ａから適当に１ターン動かして状態Ｂになったとします。Ａでの結果をmin_trans(A)としてＢのときをmin_trans(B)と書くことにすると

min_trans(A) ≦ min_trans(B) + 1

であることを証明できれば、min_transより短い手順で解くことは出来ません。どんなにがんばって１ターンすすめても、この関数を１より多く減らすことは出来ないのです。たったこれだけを証明するだけでこれより短い手順がないことを証明できるのです(ゴールに到達したときに値がゼロになるもいるけど)。

逆に、この不等号を等号にするような一手が必ず存在することを証明できれば、この手数を実現するような手順が存在することを証明できます。