/*
 *** hanoi1.c: 「ハノイの塔」の探索版プログラム ***
 *	(2004.06.24 YH)
 * * 状態空間探索により「ハノイの塔」の解を求める。
 * * 探索には search.c の探索エンジンを用いる。
 *
 *** コンパイルの仕方
 *	% cc -o hanoi1 hanoi1.c
 *	　search.c を直接取り込んでいるので、分割コンパイルは不要。
 */

#define	MAXDISK		10	// 円盤の最大枚数
#define	MAXLINK		20000	// 1000 以上のリンクが必要なので上限値を定義

#include "search.c"		// 分割コンパイルでなく、直接 search.c を取り込む

/*
 *** 状態は、各円盤がどの軸にあるかを３進数で表す。
 */
#define	MAXSTATE	59049	// = 3^10
#define	A		0
#define	B		1
#define	C		2
#define	FULL		0x07

int states[MAXSTATE];			// 状態ノード。内容は最短経路長
int ndisk = 3;				// 円盤の枚数（デフォールト 3）
int nstate, initial_state, final_state;

void
init()
{
	int i;
	for (i=0, nstate=1; i<ndisk; i++) nstate *= 3;	// 3^ndisk
	final_state = nstate-1;				// all C
	initial_state = 0;				// all A
	for (i=0; i<nstate; i++) states[i] = nstate;
}

int
movable(used, pos, d, n)
	int used, pos, d, n;
{
	int i = (pos-d)*n;
	if (used & (1 << pos)) return(0);
	return(i);
}

int
node_status(node, len, next_nodes)
	int *node, **next_nodes; int len;
{
	int state = node - states;
	int i, j, st, used, n=0;

	if (*node < len) return(FAILURE);
	*node = len;
	if (state == final_state) return(SUCCESS);

	for (i=1, st=state, used=0; i < nstate; i *= 3, st /= 3) {
		int d = st % 3;
		if (used & (1 << d)) continue;
		used |= 1 << d;
		if (used == FULL) break;
		if (j = movable(used, A, d, i)) next_nodes[n++] = node + j;
		if (j = movable(used, B, d, i)) next_nodes[n++] = node + j;
		if (j = movable(used, C, d, i)) next_nodes[n++] = node + j;
	}
	return(n);
}

void
main(argc, argv)
	int argc; char **argv;
{
	int n, len, **ans, i, j;
	int answer_flag = 0;
	int method = BREADTH_FIRST;

	for (i=1; i<argc; i++) if (argv[i][0] == '-') {
		for (j=1; argv[i][j]; j++) switch(argv[i][j]) {
			case 'a': case 'A': answer_flag = 1; break;
			case 'd': case 'D': method = DEPTH_FIRST; break;
		}
	} else {
		ndisk = atoi(argv[i]);
	}
	if ((ndisk < 1) || (ndisk > MAXDISK)) {
		fprintf(stderr, "%s: %d%s\n", "枚数", ndisk, "（1...10 枚の間であること）");
		exit(1);
	}
	init();
	n = search(states+initial_state, method);
	len = answer_length();
	ans = (int **)answer_path(1);

	printf("%s: %d  %s: %d (%s: %d, %s: %d, %s: %d)\n",
		"解の個数", n, "長さ", len,
		"状態数", nstate, "割当リンク総数", l_assigned, "極大リンク数", l_max);

	if (answer_flag == 0) exit(0);
	for (i=1; i<=len; i++) {
		int this = ans[i]-states, prev = ans[i-1]-states;
		for (j=1;; j++) {
			if (this % 3 != prev % 3) {
				printf("%4d: %s %2d %s %c %s %c %s\n",
					i, "円盤", j, "を", 
					"ABC"[prev%3], "から", "ABC"[this%3], "へ");
				break;
			}
			this /= 3; prev /= 3;
		}
	}
}