Search for a Solution: A Case Study

Abstract

This paper describes a series of attempts at the solution of a conceptually tough problem, the Firing Squad Synchronization Problem. These attempts demonstrate an increasing reliance on man-machine symbiosis and decreasing reliance on powerful heuristics and preplanning. These attempts consist of a clerical checking program, and four attempts . utilizing a basic backtracking program for searching the solution space. The first two attempts, Serial Definition of Productions and Symbolic Definition of Productions were non-interactive entirely computer directed attempts at solution. The second two, Functional Planning and Constraint Satisfaction were man-machine symbiotic attempts designed to allow the human to control and direct the computer search of the solution space. The benefits of these symbiotic attempts and the problems encountered with them are discussed