Solving combinatorial problems: the 15-puzzle

We present a series of experiments in which human subjects were tested with a well-known combinatorial problem called the 15-puzzle and in different-sized variants of this puzzle. Subjects can solve these puzzles reliably by systematically building a solution path, without performing much search and without using distances among the states of the problem. The computational complexity of the underlying mental mechanisms is very low. We formulated a computational model of the underlying cognitive processes on the basis of our results. This model applied a pyramid algorithm to individual stages of each problem. The model's performance proved to be quite similar to the subjects' performance.