/*
名稱: knight.c
作者: 洪朝貴 http://www.cyut.edu.tw/~ckhung/
功能: 從命令列上讀入棋盤的列數與行數, 讓騎士從第 0 列, 第 0 行開始走起,
      看看是否可以一步一格, 把整個棋盤走完, 既不重複也不遺漏.
需求: 螢幕必須支援 ANSI escape sequence
*/

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

#define MAX_ROW 20				/* 列數上限 */
#define MAX_COL 18				/* 行數上限 */

typedef struct {				/* 棋盤型別 */
    int nrow, ncol;				/* 有多大? */
    char cell[MAX_ROW][MAX_COL];		/* 每一格各是第幾步走到的? */
} BOARD;

void clearscr(void);
void gotorc(int r, int c);
void pusage(char const * progname);
int march(int step, int row, int col);

BOARD _board;					/* 真正的棋盤變數 */

int main(int argc, char *argv[])
{
    int success;

    /*從命令列讀入棋盤大小 */
    if (3 != argc) pusage(argv[0]);
    _board.nrow = atoi(argv[1]);
    assert(_board.nrow > 0 && _board.nrow <= MAX_ROW);
    _board.ncol = atoi(argv[2]);
    assert(_board.ncol > 0 && _board.ncol <= MAX_COL);

    /* 清除棋盤, 將所有格子設定為 0, 表示尚未走過 */
    memset(_board.cell, 0, sizeof(_board.cell));
    clearscr();

    _board.cell[0][0] = 1;
    gotorc(4, 2);
    printf("%3d", 1);
    /* 從左上角開始, 踏出第一步, 看看是否可以成功 */
    success = march(2, 0, 0);

    gotorc(23, 1);
    if (success) {
	printf("走完全程了!\n");
	return 0;
    } else {
	printf("這是不可能的任務!\n");
	return 1;
    }
}

void clearscr(void)
/* 清楚螢幕 */
{
    printf("\x1b[2J");
}

void gotorc(int r, int c)
/* 將遊標移到螢幕上第 r 列, 第 c 行. */
{
    printf("\x1b[%d;%dH", r, c);
}

void pusage(char const * progname)
/* 告訴使用者如何使用本程式 */
{
    char const * p;

    p = strrchr(progname, '/');
    if (NULL == p) p = progname;
    fprintf(stderr, "Usage: %s nrows ncols\n", p);
    exit(1);
}

int march(int step, int row, int col)
/* 跨出第 step 步, 確定踩到第 row 列, 第 col 行那一格 (本來必須是空的).
   如果這一步終究會走出正確答案, 則傳回 1, 否則傳回 0 */
{
    int i;
    int r_next, c_next;				/* 下一步的新位置 */

    int const d_row[8] = { 2, 1, -1, -2, -2, -1,  1,  2 };
    int const d_col[8] = { 1, 2,  2,  1, -1, -2, -2, -1 };
    /* 每一步有 8 種走法 */

    /* 這一步踏下去是否就已經成功了? 進入遞迴程式中的第一件事就是
       檢查結束條件 */
    if (step > _board.nrow * _board.ncol) return 1;

    /* 還有一步以上要走. 那麼我們就試試看下一步應該往那個方向走
       (共 8 種可能) */
    for (i=0; 8>i; ++i) {

	/* 如果我們下一步走第 i 個方向, 那麼新的坐標會變成 ... */
	r_next = row + d_row[i];
	c_next = col + d_col[i];

	/* 真的可以走這個方向嗎? 會不會撞到牆壁, 或者先前已經走過了? */
	if (0 > r_next || r_next >= _board.nrow ||
	    0 > c_next || c_next >= _board.ncol ||
	    _board.cell[r_next][c_next])
	    continue;

	/* 好, 那麼我們就大膽地跨出下一步 */
	assert(_board.cell[r_next][c_next] == 0);		/* 確定本來是空的 */
	_board.cell[r_next][c_next] = step;		/* 現在不是了 */
	/* 在螢幕上顯示騎士已踩到 (r_next, c_next) 這一格 */
	gotorc(r_next+4, c_next*4+2);
	printf("%3d", step);

	if (march(step+1, r_next, c_next)) return 1;

	/* 當初走這一步是沒有問題, 但是從這裡再往下走, 不管走那一個方向,
	   都無法達成目標, 所以只好退回去了. 這一步不算, 記得把棋盤上這
	   一格清成 0 */
	_board.cell[r_next][c_next] = 0;
	gotorc(r_next+4, c_next*4+2);
	printf("   ");
    }

    return 0;
}