Baudelaire is Programmer

Consider nine clocks arranged in a 3x3 array thusly:

|-------|    |-------|    |-------|    
|       |    |       |    |   |   |    
|---O   |    |---O   |    |   O   |          
|       |    |       |    |       |           
|-------|    |-------|    |-------|    
    A            B            C

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O   |    |   O   |
|   |   |    |   |   |    |   |   |
|-------|    |-------|    |-------|
    D            E            F

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O---|    |   O   |
|   |   |    |       |    |   |   |
|-------|    |-------|    |-------|
    G            H            I

The goal is to find a minimal sequence of moves to return all the dials to 12 o'clock. Nine different ways to turn the dials on the clocks are supplied via a table below; each way is called a move. Select for each move a number 1 through 9 which will cause the dials of the affected clocks (see next table) to be turned 90 degrees clockwise.

Example

Each number represents a time accoring to following table:

9 9 12       9 12 12       9 12 12        12 12 12      12 12 12 
6 6 6  5 ->  9  9  9  8->  9  9  9  4 ->  12  9  9  9-> 12 12 12 
6 3 6        6  6  6       9  9  9        12  9  9      12 12 12 

[But this might or might not be the `correct' answer; see below.]

PROGRAM NAME: clocks

INPUT FORMAT

SAMPLE INPUT (file clocks.in)

9 9 12
6 6 6
6 3 6

OUTPUT FORMAT

A single line that contains a space separated list of the shortest sequence of moves (designated by numbers) which returns all the clocks to 12:00. If there is more than one solution, print the one which gives the lowest number when the moves are concatenated (e.g., 5 2 4 6 < 9 3 1 1).

SAMPLE OUTPUT (file clocks.out)

4 5 8 9

这个问题要求用最少的步骤把所有的表盘都调整到12点，所能使用的操作集合是给定的。首先我们也许会担心这九种操作是否总能给出一个解决方案，答案是肯定的，因为对于任意表盘，都有一个操作序列能使表针不多不少顺时针转动90度同时其他表盘最终回到原状态（通过应用我们的算法可以预计算出这些操作序列，实际上这些序列的计算只是原问题的特例）。如此以来，通过累积这些序列的操作，我们肯定能得到一个问题的解（这正是USACO题解中给出的一种方法）。

然后我们注意到所有操作最多可以做3次（如果一种操作做4次，等价于没有做任何操作），而且操作顺序对结果没有影响（因为操作的效果是累加的）。这样以来所有可能的操作序列有4^9=262144个，这个数量级完全可以暴力破解（USACO对程序的限制是：运行时间<1s，内存<14M，栈<1M）。

如此一来通过DFS枚举所有情况是完全可行的。但是由于这个问题实质上属于求“最短路径”（这里路径就是操作序列），我选择了BFS以保证得到的第一个解就是最优解（DFS因为是深度优先，不遵循路径长度的顺序进行搜索，第一个解一般不是最优解，所以需要遍历所有情况，这消耗了不必要的时间），当然这需要对搜索的顺序做一定的安排：按非递减顺序遍历，每种操作最多三次。

BFS看似是个不错的选择，但是最多262144个搜索节点数让人头疼，为此我MLE（Memory Limit Exceeded）了一次。之后我想到了使用循环队列^【1】。

【1】循环队列开多大？找到搜索树中节点数之和最多的相邻两层，如果这个节点数之和是n，那么循环队列开到n+1应该就可以了。假设队列长度为n+1但是搜索过程中队尾循环回来覆盖了队头，这说明队头节点和队尾节点之间有n个节点，这与相邻两层节点数之和最多为n相矛盾（注意到BFS时队头节点永远在队尾节点的上一层）。

但是对于这道题，我的搜索树形状很奇特，这给估算n值带来了很大麻烦，在尝试之后我取了n=50000并且AC。这显然是BFS在解决这个问题时最大的坏处。

作为一个对空间的优化，实际上可以使用位运算，这样可以用一个整数的比特位表示所有表盘的状态，这让它既省空间又省时间。但我没有尝试。

我的程序代码：

USACO题解的第一种方法是DFS：

第二种方法很独特，正如文章开头提到的“对于任意表盘，都有一个操作序列能使表针不多不少顺时针转动90度同时其他表盘最终回到原状态”。这是USACO的原文：

You can precalculate a matrix a as following:

a[i][0],a[i][1],....,a[i][8] is the number of moves '1','2','3',...'9' necessarly to move ONLY clock i (where 0 < i <= 8 - there are 9 clocks: 0=A, 1=B, ... 8=I) 90 degrees clockwise. So, you have the matrix:

int a[9][9]= { {3,3,3,3,3,2,3,2,0},
               {2,3,2,3,2,3,1,0,1},
               {3,3,3,2,3,3,0,2,3},
               {2,3,1,3,2,0,2,3,1},
               {2,3,2,3,1,3,2,3,2},
               {1,3,2,0,2,3,1,3,2},
               {3,2,0,3,3,2,3,3,3},
               {1,0,1,3,2,3,2,3,2},
               {0,2,3,2,3,3,3,3,3} };

That means: to move ONLY the clock 0 (clock A) 90 degrees clockwise you have to do {3,3,3,3,3,2,3,2,0}, 3 moves of type 1, three moves of type 2, ..., 2 moves of type 8, 0 moves of type 9, etc.

To move ONLY the clock 8 (clock I), you have to do the moves {0,2,3,2,3,3,3,3,3}: 0 moves of type 1, 2 moves of type 2... 3 moves of type 9....

That's it! You count in a vector v[9] how many moves of each type you have to do, and the results will be modulo 4 (%4 - 5 moves of any type have the same effect 1 move has).

代码：

方法就是预先计算出所有这些序列，然后针对具体问题简单地叠加这些操作序列，如果一种操作超过了4次，将操作次数模4取余。这种方法可以在O(1)时间内解决问题。问题是这种方法能够总是得到最优解吗？

我认为这种方法成立的一个重要前提是 9种基本操作中任意一种不能由其余操作的组合来等效！

这样一来，操作2（ABC）等于a[0]+a[1]+a[2]（a[i]表示一个向量），也就是说(a[0]+a[1]+a[2])mod 4 == {0,1,0,0,0,0,0,0,0} （参照原文中的int a[9][9]），也就是说a矩阵中各种操作的叠加不仅和操作2等效，而且实际上就是操作2。相反，如果这个重要前提不成立，例如操作2可以由操作1和操作3叠加得到，那么a[0]+a[1]+a[2]有可能等于{1,0,1,0,0,0,0,0,0} 这样由此算法得到的解不一定是最优解（一个操作变成了两个操作，操作步骤增加了）。

如果这个前提成立，那么这个算法肯定是安全的，当然这只是一个充分条件，至于其必要性我没能证明。不过从另一角度考虑，一个“九维”的表盘组，表盘之间没有相关性，如果操作2可以由操作1和3叠加的话，实际上我们只有8种操作方式，这显然是不够的，对于一些情况它甚至不能成功的将所有表盘调到12点！

那么这个安全性如何被保证呢？当这个前提成立时，我们的搜索算法和这个常数时间算法是等价的。因为9种操作的每一种都和a矩阵中的某操作序列唯一等价。当你被告知a矩阵向量的某种组合可以组合出最优解，而且把重复4次的向量消去后你只有唯一一种组合方式，那么这个组合不是最优解又能是什么呢？

PS. 本文所有推理都是意淫，事实上本人没有什么数学造诣以至于不能给出形式化的证明。