Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456 A Real-Time Algorithm for the (<i>n</i><sup>2</sup>-1)-Puzzle
A real-time algorithm for the (n2-1)-puzzle is designed
using greedy and divide-and-conquer techniques.
It is proved that (ignoring lower order terms)
the new algorithm uses at most 5n3 moves,
and that any such algorithm must make
at least n3 moves in the worst case,
at least 2n3/3 moves on average, and
with probability one,
at least 0.264 n3 moves on random configurations.
Created by Ian Parberry,
October 15, 1997. Last updated
Wed Oct 15 19:19:11 CDT 1997.