There was one word of warning...not all possible combinations can be solved in the 1 - 15 order. Of all permutations of the tile positions, half are solvable in the 1-15 order with the space in the bottom right corner, and the other half are solvable in the reverse (15-1) order with the space in the bottom right corner. There is a way of calculating which solvable format a given permutation is a member of. Many of the sit's show this, but only mention that the puzzle will end up with the 14 and 15 in the wrong order...none mention the reverse-order. Personally, I find it interesting that the solutions are in forward and reverse order for the two sets of permutations.

We were to use whatever computer system we had available. I wrote a Pascal program to solve it running on a CDC Cyber system. One classmate was able to complete the assignment in assembler on a 6502 processor system with 4KB of memory. Heuristic searches, tree searches and brute force methods were used...given the limited resources of the time, a combination of heuristic and tree searches were the most successful.

I am currently working on a Visual Basic version of the program and plan to use a breadth-first tree search to find the shortest path.