3 Puzzle: 3 2 -1 1 8 Puzzle: 3 2 1 6 5 4 8 7 -1 15 Puzzle: 4 3 2 1 8 7 6 5 12 11 10 9 -1 15 14 13 24 Puzzle: 5 4 3 2 1 10 9 8 7 6 15 14 13 12 11 20 19 18 17 16 -1 24 23 22 21
My program began in some state (call it A). A is assumed to not be the goal state. It then generated all legal moves from A and randomly selected one (call it B). If B was the goal, the program stopped and declared the problem solved. Otherwise the set B to A and repeated.
If the program maintained a history, then it removed from the set of legal moves all points in the history list. If, as a result, there were no possible moves it declared itself stuck and the problem unsolvable (in the current trial at least).
2x2 = 4!/2 = 12 possible moves 3x3 = 9!/2 = 181,440 possible moves 4x4 = 16!/2 = 10,461,394,944,000 possible moves 5x5 = 25!/2 = 7,755,605,021,665,492,992,000,000 possible movesRoughly, this says that moving randomly will work as a method for solving the 2x2 and 3x3 puzzles because moving by simply taking random moves you can see almost all (or all) of the possible states in a reasonable time. For example, my program looked at about 600 states per second, so for the 3x3 puzzle, it could visit every possible state in about 30 seconds. Since it takes visiting each state about 3 times (for the 3x3 puzzle) to get a sulution the program takes about 1 minute. To get similar time to solution on the 4.4 puzzle, my program would need to visit 400,000,000,000 states per second. This speedup seems unlikely to come soon.
Using the 8 puzzle, and a static random seed generator, the program was able to find a solution in an average of 438K moves. Next I added a check that would prevent the next move from being a return to the previous position. If the last move was up, then the next move could not be down, if the last move was right then the next could not be left, and so on. Again using the static random seed this change improved the solution to average solution 273K moves. According to a one tailed t-test, preventing the program from moving back to its last position improves search speed with greater than .99 probability.
Expanding the history length to 2 further improves the speed, however, the difference is not statistically significant. Further expanding the history still does not significantly improve spped (measured in number of states searched).
Another measure of speed is CPU time. The single history does improve CPU time, but only at the .98 level (according to a one-taile t-test). Longer histories acutally result in increasing the time required to find a solution.
These results might be explained as follows. The random searcher is inefficient because it frequently chooses to move back to where it has just been. Simply preventing it from doing this stupid thing tends to speed a solution because it results in a more efficient sampling of the state space.
Longer histores further improve the efficiency of state space sampling , but not by a huge since the history of 1 already stops the most eggregious problem.
The problem with retaining histores is that you have to chek them. This takes time, albeit not much. Still, if the gain from maintainin a longer history is minimal, then the cost (in CPU time) from doing so can easily overwhelm the gains from reduced search.
In the 8 puzzle, any history size over 3 can cause the program to get stuck in a corner. [[Consider a long explanation here]] Longer histories increase the likelihood of this occurrence. More, a history of length 6 is sufficient to get the program stuck along a side (that is not a corner). A history of length 9 is sufficient to get stuck in the middle.