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在解决这个问题时最大的坏处。

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

我的程序代码：

/*
ID: *******
LANG: C
TASK: clocks
*/
#include<stdio.h>
FILE *fin,*fout;
typedef struct{
	int clo[9];//表盘状态
	int beg;//第一个要尝试的操作的编号
	int count[9];//每种操作的次数
	int memo[27];//操作序列
	int pMemo;
}CL;//搜索树节点的定义
CL queue[50001];
int tailQue=-1;
int headQue=-1;
int move[9][9]={
	{3,3,0,3,3,0,0,0,0},
	{3,3,3,0,0,0,0,0,0},
	{0,3,3,0,3,3,0,0,0},
	{3,0,0,3,0,0,3,0,0},
	{0,3,0,3,3,3,0,3,0},
	{0,0,3,0,0,3,0,0,3},
	{0,0,0,3,3,0,3,3,0},
	{0,0,0,0,0,0,3,3,3},
	{0,0,0,0,3,3,0,3,3}
};

int testOutput(int po){
	int isAnswer=1;
	int i;
	for(i=0;i<9;i++){
		if(queue[po].clo[i]!=12){
			isAnswer=0;
			break;
		}
	}
	if(isAnswer==1&&queue[po].pMemo>=0){
		fout=fopen("clocks.out","w");
		fprintf(fout,"%d",queue[po].memo[0]+1);
		for(i=1;i<=queue[po].pMemo;i++){
			fprintf(fout," %d",queue[po].memo[i]+1);
		}
		fprintf(fout,"\n");
	}
	return isAnswer;
}

int main(){
	fin=fopen("clocks.in","r");
	int i;
	headQue=0;
	tailQue=1;
	for(i=0;i<9;i++){
		fscanf(fin,"%d",&queue[headQue].clo[i]);
		queue[headQue].count[i]=0;
	}
	queue[headQue].pMemo=-1;
	queue[headQue].beg=0;
	while(headQue!=tailQue){//开始BFS
		if(testOutput(headQue)==1)break;
		for(i=queue[headQue].beg;i<9;i++){
			if(queue[headQue].count[i]>=3)continue;
			int j;
			for(j=0;j<9;j++){
				queue[tailQue].clo[j]=queue[headQue].clo[j]+move[i][j];
				if(queue[tailQue].clo[j]>12)
					queue[tailQue].clo[j]-=12;
				queue[tailQue].count[j]=queue[headQue].count[j];
			}
			for(j=0;j<=queue[headQue].pMemo;j++)
				queue[tailQue].memo[j]=queue[headQue].memo[j];
			queue[tailQue].count[i]++;
			queue[tailQue].pMemo=queue[headQue].pMemo+1;
			queue[tailQue].memo[queue[tailQue].pMemo]=i;
			queue[tailQue].beg=i;
			//printf("tail:%d\n",tailQue);
			tailQue++;
			if(tailQue>50000)tailQue=0;
		}
		headQue++;
		if(headQue>50000)headQue=0;
	}
	return 0;
}

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>

#define INF 60000	/* bigger than longest possible path */

char *movestr[] = { "abde", "abc", "bcef", "adg", "bdefh", "cfi", "degh",
                    "ghi", "efhi" };

int movedist[9][9];
int clock[9];

int bestmove[9];
int nbestmove;

/* translate move strings into array "movedist" of which clocks change on each move */
void
mkmove(void)
{
    int i;
    char *p;

    for(i=0; i<9; i++)
	for(p=movestr[i]; *p; p++)
	    movedist[i][*p-'a'] = 3;
}

/* apply some number of each move from k to 9 */
/* move contains the number of times each move is applied */
void
solve(int *move, int k)
{
    int i, j, n, rep;

    if(k == 9) {
	for(j=0; j<9; j++)
	    if(clock[j]%12 != 0)
		return;

	/* we have a successful sequence of moves */
	n = 0;
	for(j=0; j<9; j++)
	    n += move[j];

	if(nbestmove == 0 || n < nbestmove) {
	    nbestmove = n;
	    for(j=0; j<9; j++)
		bestmove[j] = move[j];
	}
	return;
    }

    /*
     * the for loop counts down so we
     * generate smaller numbers first by
     * trying more of small numbered
     * moves before we try less of them.
     */
    for(rep=3; rep>=0; rep--) {
	/* apply move k rep times */
	for(i=0; i<rep; i++)
	    for(j=0; j<9; j++)
		clock[j] += movedist[k][j];
	move[k] = rep;

	solve(move, k+1);

	/* undo move */
	for(i=0; i<rep; i++)
	    for(j=0; j<9; j++)
		clock[j] -= movedist[k][j];
    }
}

void
main(void)
{
    FILE *fin, *fout;
    int i, j, move[9];
    char *sep;

    fin = fopen("clocks.in", "r");
    fout = fopen("clocks.out", "w");
    assert(fin != NULL && fout != NULL);

    mkmove();

    for(i=0; i<9; i++)
	fscanf(fin, "%d", &clock[i]);

    solve(move, 0);

    sep = "";
    for(i=0; i<9; i++) {
	for(j=0; j<bestmove[i]; j++) {
	    fprintf(fout, "%s%d", sep, i+1);
	    sep = " ";
	}
    }
    fprintf(fout, "\n");

    exit(0);
}

第二种方法很独特，正如文章开头提到的“对于任意表盘，都有一个操作序列能使表针不多不少顺时针转动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).

代码：

#include <stdio.h>

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} };
int v[9];

int main() {
    int i,j,k;
    freopen("clocks.in","r",stdin);
    for (i=0; i<9; i++) {
        scanf("%d",&k);
        for(j=0; j<9; j++)
             v[j]=(v[j]+(4-k/3)*a[i][j])%4;
    }
    fclose(stdin);

    k=0;
    freopen("clocks.out","w",stdout);
    for (i=0; i<9; i++)
        for (j=0; j<v[i]; j++)
            if (!k) { printf("%d",i+1); k=1; }
            else    printf(" %d",i+1);
    printf("\n");
    fclose(stdout);
    return 0;
}

方法就是预先计算出所有这些序列，然后针对具体问题简单地叠加这些操作序列，如果一种操作超过了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. 本文所有推理都是意淫，事实上本人没有什么数学造诣以至于不能给出形式化的证明。