判別方法是:
以數組為壹維的舉例子.
將八數碼的壹個結點表示成壹個數組a[9],空格用0表示,設臨時函數p(x)定義為:x數所在位置前面的數比x小的數的個數,
其中0空格不算在之內,那設目標狀態為b[9],那r=sigma(p(x)) sigma()表示取所有的x:1-8並求和,
那對於初始狀態a[9],t=sigma(p(x)),如果r和t同為奇數或者同為偶數,那麽該狀態有解,否則無解。
考慮到四種移動方法對sigma(p(x))的影響,左移和右移是不會影響它的值的,
更不會影響奇偶性,如果是上移或者下移就會影響:
上移:壹次上移會使壹個元素向前跳兩個數字的位置,設這兩個數字為a1,a2,
不妨設a1<a2,移的這個數字設為a0,那無非只有以下三次情況:
1,a0<a1<a2,考慮它們三者的p(x)值,p(a0)不變,p(a1)++,p(a2)++,總體增加了2
2,a1<a0<a2,p(a0)--,p(a1)不變,p(a2)++,總體不變
3,a1<a2<a0,p(a0)-=2,p(a1),p(a2)不變,總體減小了2
綜合起來的結論就是不會影響sigma(p(x))的奇偶性。