U455764 The Rotation Game

# 一道好的$DFS$题

旋转游戏使用一个#形状的棋盘，可以容纳24个方块（见图1）。这些方块标有符号1、2和3，每种符号恰好有8个方块。  最初，方块是随机放置在棋盘上的。你的任务是移动方块，使得中心方块中的八个方块具有相同的标记。只有一种有效移动方式，即旋转四条线中的一条，每条线由七个方块组成。也就是说，线中的六个方块向头部移动一个方块，头部方块移动到线的末尾。八种可能的移动用大写字母A到H标记。图1说明了某个初始配置下的两个连续移动，移动A和移动C。

输入不超过30个测试用例。每个测试用例只有一行，包含24个数字，即初始配置中方块的符号。方块的行从上到下列出。对于每一行，方块从左到右列出。数字之间用空格分隔。例如，样例输入中的第一个测试用例对应图1中的初始配置。测试用例之间没有空行。在最后一个测试用例之后，有一行包含单个`0'的行，表示输入结束。

对于每个测试用例，你必须输出两行。第一行包含到达最终配置所需的所有移动。每个移动是一个字母，范围从`A'到`H'，并且行中的字母之间不应有任何空格。如果不需要移动，输出`No moves needed'。在第二行中，你必须输出这些移动后中心方块中的符号。如果存在多个可能的解决方案，你必须输出使用最少移动次数的解决方案。如果仍然存在多个可能的解决方案，你必须按照移动字母的字典顺序输出最小的解决方案。在测试用例之间不需要输出空行。