**The Best of Creative Computing Volume 1 (published 1976)**

Another new game from Creative Computing.... REVERSE 987654321 123456789 by Peter Sessions, People's Computer Company, Menlo Park, CA Description In the computer game REVERSE the player must arrange a list of numbers in numerical order from left to right. To move, you tell the computer how many numbers in the list (counting from the left) to reverse. For example, if the current list is: 2 3 4 5 1 6 7 8 9 and you reverse four numbers, the result will be: first 4 numbers reversed from above list [image] 5 4 3 2 remainder of list stays the same [image] 1 6 7 8 9 Now if you reverse five numbers, you win! first 5 numbers reversed from above list [image] 1 2 3 4 5 6 7 8 9 *** Playing Strategies There are many ways to play the game; generally an approach can either be classified as algorithmic or heuristic. The game thus affords the player an opportunity to explore these concepts in a practical rather than a theoretical context. An algorithmic approach is one that is described by means of a finite algorithm and guarantees a solution in a predictable number of moves. For example, an algorithmic approach to playing REVERSE would be to order the list from right to left starting with the highest value number and moving down. Using this strategy with a list of nine numbers, your first move would always be to get the 9 into position 1 (leftmost) and the second move would be to reverse nine so the 9 was put into position 9 (rightmost). You would continue moving the 8 to position 1 and then to position 8, the 7, 6, 5 and so on until the list was ordered. This method guarantees a solution in 2N-3 moves (N numbers in the list). One could easily program a computer to play this strategy. A heuristic approach to solving a problem can be thought of as a rule of thumb. Some rules of thumb are very good and lead to good solutions, others are not as good. Consequently, using a heuristic approach doesn't guarantee the best possible solution but for very complex problems (and even some simple ones) it may be a more efficient approach than a rigorous linear programming or mathematical method which guarantees a perfect solution. The science of heuristic problem solving using the computer has become very advanced and is widely used for things like locating warehouses, railroad car routing and other problems involving hundreds of variables and many alternative solutions. Consider: a linear programming solution to routing a mixed load boxcar from Boston to receiving points in Hartford, Columbus, Atlanta, and Baton Rouge would take about 0.72 hours to run on a computer. The heuristic solution takes 0.002 seconds to run, yet it generally yields a solution within 5% of the linear programming (perfect) solution. Obviously, with millions of cars to be routed every day, the linear approach is not economically feasible. The game of REVERSE lends itself very well to a heuristic approach. There are many possible solutions to each game. One is best, but the mathematics to determine this solution are quite complex and would be extremely time-consuming to calculate. (The simpler algorithmic approach above guarantees a solution, but it is far from optimal). A good heuristic approach which takes advantage of "partial orderings" in the list generally yields a solution within 1 or 2 moves of the perfect solution, i.e., within 10% to 20% of perfection. Using a heuristic approach, your next move is dependent upon the way the list currently appears. No solution is guaranteed in a predictable number of moves, but if you are clever (and lucky?) you should come out ahead of the simple algorithmic approaches. For a list with nine numbers can you describe a heuristic strategy that wins the game in an average of 10 or fewer moves? You may well use more than one rule of thumb (heuristic). 258