Fig: A simple case, when the number of Titans is two. The extra stone is between the two titans.
The Titans are in danger. They are trapped in a volcanic lake over a few stones. The number of stones is just one greater than the number of Titans. Only one Titan can stand over a stone at a time. They are mighty but helpless. They can see the shore but cannot reach it. The extra stone is of somewhat different nature. Once it is used, it sinks. But if the Titans can arrange themselves in a completely new orientation after that use, the stone rises again. The Titans could not figure out what to do? One of the merciful Gods became visible from the eastern sky and said,
¡°Use the stone to raise the stone¡.
When it finishes, you are free¡.¡±
So you are going to help them.
Note: The Titans can jump from one stone to another safely and easily if the target stone is vacant. No two Titans will have the same initial character in the name. Whenever the stone rises, the leftmost Titan loves to start. When all possible orientation is generated without repeating any state the Titans get free. A new state can be generated by exactly three jumps.
The input file contains several lines of input. Each line describes an initial orientation of Titans (as a sequence of the initial character of their names). The maximum number of Titans is 9. Input is terminated by end of file.
For each line of orientation you have to determine all possible orientations so that the titans become free. Print blank line after the output for each line of input.
/***************Many lines of outputs here which are not shown****************/
(Problem-setter: Tanbir Ahmed, CSE Dept, Southeast University)
(I would like to thank Hossain Muhammad Farook (University of Dhaka) for drawing the picture of the Titans)
A machine can do the work of fifty ordinary man, but no machine can do
the work of an extra-ordinary man.