/*

	ハノイの塔 

          27:    --2--567|    01------|    ---34---|

	このスタイルで、一ステップにつき一行で表示する。この例は、27 ステップ目、
	棒 0 には円盤 2, 5, 6, 7 が、棒 1 には円盤 0, 1 が、棒 2 には円盤 3, 4 が
	ささっている、と読む。（円盤は番号が小さいほど小さい。）
*/
#include <stdio.h>

#define N 16		/* 円盤の数 */

int a[N];			/* 各円盤が 0, 1, 2 のどの棒にささっているか */
int count = 0;		/* 何ステップ目かのカウンタ */

void hanoi(int n, int from, int to);
void show(void);

main() {
	int i;

	for (i = 0; i < N; i++) {	/* 初期化 */
		a[i] = 0;				/* すべてが棒 0 にささっているとする */
	}
	show();						/* 表示 */
	hanoi(N-1, 0, 1);
}


/* 円盤 0 から円盤 n までを、棒 from から棒 to へ移す */
void hanoi(int n, int from, int to) {
	if (n == 0) {
		a[n] = to; count++; show();
	} else {
		hanoi(n-1, from, 3-from-to);	/* 再帰呼び出し */
		a[n] = to; count++; show();
		hanoi(n-1, 3-from-to, to);		/* 再帰呼び出し */
	}
}


/* 円盤の配置を表示 */
void show(void) {
	int i, j;

	printf("%12d:", count);
	for (j = 0; j <= 2; j++) {		/* j は棒の番号 */
		printf("    ");
		for (i = 0; i < N; i++) {	/* i は円盤の番号 */
				if (a[i] == j) {
				printf("%x", i%16);	/* 十六進で下一けたのみを表示 */
			} else {
				printf("-");		/* 空きの印 */
			}
		}
		printf("|");				/* 床の印 */
	}
	printf("\n");
}