Many computing problems can be solved by identifying all possible moves or combinations of events and then picking the best solution. Problems in this domain provide fertile ground for exploring problem representation, storage requirements, and computational complexity. The problems and solution approaches are easy to understand, yet quickly push the memory and storage limits of a personal computer. This paper describes insights from a preliminary investigating of two exhaustive search problems, the 15-puzzle and Rubik’s cube. The insights gained by looking at exhaustive search problems can be integrated into classroom discussions and projects.
Lehman, Jeffrey L., "Exploring the Limits of Computing Through Exhaustive Search" (2009). ACMS Conference Proceedings 2009. 12.