// KNIGHT.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream.h>
#include <iomanip.h>

enum BOOLEAN 
{
	FALSE =0,
	TRUE =10
};

const int MAX_WIDTH = 30;
const int MAX_DIR = 8;

class KNIGHT 
{
  public:

	KNIGHT(int width);		// 設置初始狀態
	
	void print();			// 打印問題的解
	
	// 根據馬的起始位置(start_x, start_y)使用回溯算法求騎士游歷問題的一個解
	// (start_x, start_y)必需在所設置的棋盤寬度范圍內
	BOOLEAN tourist(int start_x, int start_y);

protected:
	void init_direction();		// 初始化記錄所選方向的數組，將每個值置為MAX_DIR
	
	void init_chessboard();		// 初始化記錄馬在第幾步到位每個位置的數組，將每個值置為0
	
	void set_start(int x, int y);	// 設置初始狀態，包括初始化方向數組和棋盤數組，并設置馬的初始位置
	
	// 在當前位置選擇一個方向以推進到下一位置
	// 如果可選擇一個方向推進則返回TRUE，否則返回FALSE
	// 將該函數定義為虛函數，以便下面快速游歷的類來重定義該函數而產生動態綁定
	virtual BOOLEAN select_direction();
	
	// 從當前位置回溯到上一位置
	// 將該函數定義為虛函數，以便下面快速游歷的類來重定義該函數而產生動態綁定
	virtual void backward();
	
	// 從當前位置推進到下一位置
	// 將該函數定義為虛函數，以便下面快速游歷的類來重定義該函數而產生動態綁定
	virtual void forward();
	
	// 判斷馬是否能夠走向位置(x, y)。
	// 如果馬已經到過該位置，或該位置超出棋盤范圍返回FALSE，否則返回TRUE
	BOOLEAN is_legal(int x, int y);
	
	// 判斷是否回溯到初始狀態
	// 如果步數回到第1步則表示回到初始狀態而返回TRUE，否則返回FALSE
	BOOLEAN back_to_start();
	
	// 判斷是否游歷完所有位置
	// 如果步數等于棋盤格子數則表示游歷完所有位置而返回TRUE，否則返回FALSE
	BOOLEAN is_end();
	
	// 下面兩個數組用來記住選擇某個方向后，推進到下一位置時x方向和y方向的值的變化
	int var_x[MAX_DIR];
	int var_y[MAX_DIR];
	
	int chessboard[MAX_WIDTH][MAX_WIDTH];	// 記錄馬第幾步到達某個位置的棋盤數組
	
	int direction[MAX_WIDTH][MAX_WIDTH];	// 記錄馬在某個位置是在上一位置選擇第幾個方向到達的
	int width; 				//棋盤寬度
	int curr_x, curr_y; 			//馬的當前位置
	int step; 				//已經游歷的步數
	int last_direction; 			//上一位置到當前位置所選的方向
	int total_step;
};

KNIGHT::KNIGHT(int width)
{
	this->width = width;
	init_direction();
	total_step = 0;
}

void KNIGHT::print()
{
	int x, y;
	cout << " +";
	
	for (x = 0; x < width; x = x + 1) 
		cout << "----+";
        cout<<endl;
	
	for (x = 0; x < width; x = x + 1) 
	{
		cout << " |";

		for (y = 0; y < width; y = y + 1) 
			cout << setw(3) << chessboard[x][y] << " |";

		cout << endl;
		cout << " +";

		for (y = 0; y < width; y = y + 1) 
			cout << "----+";
		
		cout << endl;
	}
}

BOOLEAN KNIGHT::is_legal(int x, int y)
{
	if (x < 0 || x >= width) return FALSE;
	if (y < 0 || y >= width) return FALSE;
	if (chessboard[x][y] > 0) return FALSE;
	return TRUE;
}

BOOLEAN KNIGHT::back_to_start()
{
	if (step == 1) return TRUE;
	else return FALSE;
}

BOOLEAN KNIGHT::is_end()
{
	if (step > width * width) return TRUE;
	else return FALSE;
}

void KNIGHT::set_start(int x, int y)
{
	curr_x = x; curr_y = y; step = 1;
	chessboard[x][y] = step; step = step + 1;
	direction[x][y] = MAX_DIR;
	last_direction = MAX_DIR;
}

BOOLEAN KNIGHT::select_direction()
{
	int try_x, try_y;
	
	// last_direction為MAX_DIR表示當前位置是一個新的位置，在新推進到某個位置(curr_x, curr_y)時，
	// direction[curr_x][curr_y]會記錄上一位置到(curr_x, curr_y)時所選擇的方向，這時
	// last_direction置為MAX_DIR用來標記該位置是新推進的位置。
	if (last_direction == MAX_DIR) 
		last_direction = 0;
	else 
		last_direction = last_direction + 1;
	
	while (last_direction < MAX_DIR) 
	{
		// 看下一步推進到哪個位置是合法的，如果合法則選擇該方向。
		try_x = curr_x + var_x[last_direction];
		try_y = curr_y + var_y[last_direction];
		
		if (is_legal(try_x, try_y)) break;
		
		last_direction = last_direction + 1;
	}
	
	if (last_direction == MAX_DIR) 
		return FALSE;
	else 
		return TRUE;
}

void KNIGHT::backward()
{
	step = step - 1;
	chessboard[curr_x][curr_y] = 0;
	
	// 將last_direction置為上一位置到(curr_x, curr_y)所選擇的方向
	last_direction = direction[curr_x][curr_y];
	
	// 根據這個方向回溯到上一位置，同時回溯到上一位置之后，在上一位置再試探時應該從
	// last_direction+1的方向開始。參看成員函數select_direction()。
	curr_x = curr_x - var_x[last_direction];
	curr_y = curr_y - var_y[last_direction];
}

void KNIGHT::forward()
{
	// 在推進時last_direction是當前位置所選擇的方向
	curr_x = curr_x + var_x[last_direction];
	curr_y = curr_y + var_y[last_direction];
	chessboard[curr_x][curr_y] = step;
	step = step + 1;

	// 這個方向被記錄下一位置(這時已經為(curr_x, curr_y))的direction數組中。
	direction[curr_x][curr_y] = last_direction;

	// last_direction的值已經被記錄，這時置為MAX_DIR表示當前位置為新推進的位置
	last_direction = MAX_DIR;
}

BOOLEAN KNIGHT::tourist(int start_x, int start_y)
{
	init_chessboard();
	set_start(start_x, start_y);
	do 
	{
		if (select_direction()) forward();
		else backward();
	} while (!back_to_start() && !is_end());
	
	if (back_to_start()) 
		return FALSE;
	else 
		return TRUE;
}

void KNIGHT::init_direction()
{
	var_x[0] = 2; var_y[0] = 1;
	var_x[1] = 1; var_y[1] = 2;
	var_x[2] = -1; var_y[2] = 2;
	var_x[3] = -2; var_y[3] = 1;
	var_x[4] = -2; var_y[4] = -1;
	var_x[5] = -1; var_y[5] = -2;
	var_x[6] = 1; var_y[6] = -2;
	var_x[7] = 2; var_y[7] = -1;
}

void KNIGHT::init_chessboard()
{
	int x, y;
	for (x = 0; x < width; x = x + 1) 
	{
		for (y = 0; y < width; y = y + 1) 
		{
			chessboard[x][y] = 0;
		}
	}
}
// 使用回溯算法快速求解騎士游歷問題
class FAST_KNIGHT: public KNIGHT 
{
  public:
	FAST_KNIGHT(int width);
  
  protected:
	void init_cannot();		// 初始化cannot數組
	
	// 在當前位置根據啟發式規則選擇一個方向以推進到下一位置
	// 如果可選擇一個方向推進則返回TRUE，否則返回FALSE
	// 重定義KNIGHT類的select_direction()
	virtual BOOLEAN select_direction();
	
	// 從當前位置回溯到上一位置，注意維持cannot數組
	// 重定義KNIGHT類的backward()
	virtual void backward();
	
	// 從當前位置根據所選擇的方向推進到下一位置
	// 重定義KNIGHT類的forward()
	virtual void forward();
	
	BOOLEAN cannot[MAX_WIDTH][MAX_WIDTH][MAX_DIR];	// 用來記住某個位置某個方向是否已經試探過
};

void FAST_KNIGHT::init_cannot()
{
	int x, y, dir;
	for (x = 0; x < width; x = x + 1)
		for (y = 0; y < width; y = y + 1)
			for (dir = 0; dir < width; dir = dir + 1) 
cannot[x][y][dir] = FALSE;
}

FAST_KNIGHT::FAST_KNIGHT(int width): KNIGHT(width)
{
	init_cannot();
}

BOOLEAN FAST_KNIGHT::select_direction()
{
	int try_x, try_y, next_x, next_y;
	int dir_index, next_index;
	int min_dir, count;
	min_dir = MAX_DIR; last_direction = MAX_DIR;
	for (dir_index = 0; dir_index < MAX_DIR; dir_index = dir_index + 1) 
	{
		// 選擇一個方向，使得根據該方向推進到下一位置時，在該位置可選的方向最少
		try_x = curr_x + var_x[dir_index];
		try_y = curr_y + var_y[dir_index];
		if (is_legal(try_x, try_y) && !cannot[curr_x][curr_y][dir_index]) 
		{
			// 這個位置作為下一位置是合法，那么計算該位置可選的方向
			count = 0;
			for (next_index = 0; next_index < MAX_DIR; next_index++) 
			{
				next_x = try_x + var_x[next_index];
				next_y = try_y + var_y[next_index];
				if (is_legal(next_x, next_y)) count = count + 1;
			}
			
			if (count < min_dir) 
			{
				// 記錄具有最少可選方向的下一位置
				last_direction = dir_index;
				min_dir = count;
			}
		}
	}
	
	if (last_direction == MAX_DIR) 
		return FALSE;
	else 
		return TRUE;
}
void FAST_KNIGHT::backward()
{
	int dir;
	step = step - 1;
	chessboard[curr_x][curr_y] = 0;
	
// 從位置(curr_x, curr_y)回溯，那么下一次再到達該位置時所有方向都需要重新試探
	for (dir = 0; dir < MAX_DIR; dir = dir + 1) 
cannot[curr_x][curr_y][dir] = FALSE;
	last_direction = direction[curr_x][curr_y];
	curr_x = curr_x - var_x[last_direction];
	curr_y = curr_y - var_y[last_direction];
}
void FAST_KNIGHT::forward()
{
	// 該位置的這個方向已經試探過了
	cannot[curr_x][curr_y][last_direction] = TRUE;
	curr_x = curr_x + var_x[last_direction];
	curr_y = curr_y + var_y[last_direction];
	chessboard[curr_x][curr_y] = step;
	step = step + 1;
	direction[curr_x][curr_y] = last_direction;
	last_direction = MAX_DIR;
}

int main()
{
	int width = 8;
	FAST_KNIGHT knight(width);
	int start_x, start_y;
	cout << "\nProgram begin..."<<endl;
	start_x = 4; start_y = 4;
	
	if (knight.tourist(start_x, start_y)) 
	{
		knight.print();
	}
	else 
	{
		cout << "\nHave not found the solution for: ";
		cout << "Start: <" << start_x << ", " << start_y << ">, ";
		cout << "Width: " << width << endl;
	}
	
	return 1;
}