10 Nov
2003
10 Nov
'03
4:30 p.m.
At 06:12 PM 11/10/2003, Jud McCranie wrote:
In the reference for the 4x4 case,
Correction, that was 5x5.
I did a Google search for "15 puzzle" and "optimal solution", and I found this: http://citeseer.nj.nec.com/context/44966/0 which says that finding the optimal solution of nxn is NP-hard. This 1994 result http://www.informatik.uni-osnabrueck.de/papers_html/ai_94/node10.html mentions taking an average of 8 seconds per solution on a parallel computer with 1024 CPUs, but it states that the parallel computer wasn't fully utilized. It goes on to say that a Sun SparcStation 10/40 could do 660,000 nodes per second. Of course, that was 10 years ago, but there are a large number of nodes per position and a large number of positions.