The Towers of Hanoi puzzle, introduced in 1883, is a classic and widely used example for the study of recursion, analysis of algorithms, and induction. Over 350 papers have been published about it, and some of its variants. Undeterred, I will consider yet another variation -- the towers played as a two player game. In the game of "Touring Hanoi", the discs are moved alternately by the two players, subject to the usual restrictions (no disc can be placed on top of a smaller disc), and, in order to prevent stalemate, a rule that forbids repeated positions, or dead end moves which don't allow the goal to be reached. The question then is: which player has a winning strategy? Not unexpectedly, the classic themes of recursion and induction are the key to finding the answer.
Reference: http://www.cs.wm.edu/~pkstoc/toh.html
Last modified: Monday, 05-Jul-2010 12:09:29 NZST
This page is maintained by the seminar list administrator.