15パズルの場合、最終形(数字がきれいに並んだ状態)から、数字と数字を入れ替えるシャッフルをした場合に、
シャッフル偶数回なら解ける状態。
シャッフル奇数回なら解けない状態になる。

逆に言えば、ランダムな状態から偶数回のシャッフルで最終形に持ってけるなら、そのランダムな状態は解決可能。

多分トポロジー当りで説明できると思うが俺は無理ｗ