What Makes Some Problems Hard: Explorations in the Problem Space of Difficulty
Abstract
This paper identifies two sources, one larger, one smaller, of the great difficulty encountered by subjects solving the Chinese Ring Puzzle. Almost none of our subjects were able to solve the puzzle within two hours unless they were given a demonstration of how to move, and even with that help only half of the subjects obtained solutions. Discovering how to make moves, rather than other features of the problem search space, was the source of its inordinate difficulty. Evidence for this comes from isomorphs that were designed to 'digitize' the moves, which in the original version have analog qualities. These digital isomorphs were solvable by almost all subjects, with average solution times of 10 to 25 minutes, depending on isomorph type. The digitized problems still required considerable effort for their solution. The difficulty of these problems in digital form is particularly surprising, given that the problem search space is linear: there is no branching. Hence, size of search space (exponential explosion) was not the source of difficulty here. The linearity of the search space did not prevent the subjects from making a large number of moves in reaching a solution. The average number of moves ranged from 150 to 450 for different isomorphs. In addition, the subjects' move behavior was often dichotomous, consisting of a very large number of non-progressive, often error- prone moves, followed by a very rapid, often error-free movement to the goal.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 14, 1989
- Accession Number
- ADA219002
Entities
People
- Herbert Simon
- Kenneth Kotovsky
Organizations
- Carnegie Mellon University