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.
Department of Psychological Sciences, Purdue University, West Lafayette, Indiana 47907-2081, USA. pizlo@psych.purdue.edu
Zygmunt
Z
Pizlo
Zheng
Z
Li
D006801:Humans; D007600:Judgment; D011340:Problem Solving