Thinking Recursively with Java

Chapter 8. Recursive Backtracking

A mighty maze! but not without a plan.

—Alexander Pope, An Essay on Man, 1733

Of those areas that make up computer science, the one that tends to capture the most popular attention is artificial intelligence. The idea that a machine could be endowed with the capacity for thought is enticing to some and profoundly disturbing to others. Prior to the advent of modern computers, the debate over artificial intelligence and its potential was primarily philosophical. With the development of extremely fast machines, computers can now perform complex tasks that seem to require intelligence.

Systems that seek to simulate intelligent behavior often make extensive use of recursion, which provides a powerful framework for searching through a set of possibilities for an optimal choice. The general strategy is called recursive backtracking. It consists of having the computer make tentative choices in a way that allows it to backtrack to previous decision points so that it can explore other possible options. This chapter presents two applications of recursive backtracking: (1) finding a path through a maze, and (2) choosing a move in a strategy game.