horsetravel.h

一个解决国际象棋的马周游问题的算法.本程序使用改善后的回溯算法来加速问题的解决.

// HorseTravel.h: interface for the HorseTravel class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_HORSETRAVEL_H__D7460B80_CC19_4C31_BD5D_14FABF6EA5F7__INCLUDED_)
#define AFX_HORSETRAVEL_H__D7460B80_CC19_4C31_BD5D_14FABF6EA5F7__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

struct Node
{
	int row;
	int col;
	int dirt[8];
	int index;
};

class HorseTravel  
{
public:
	HorseTravel(int StartRow, int StartCol, int ChessSize);
	virtual ~HorseTravel();

private:
	//全局数据,8个方向的增量
	static int s_drow[8];
	static int s_dcol[8];

	static bool s_bStop;
	
	//辅助数据
	int m_ways[8];//临时保存某点在8个方向的出口数
	bool** m_Access;//保存(N*N)各点是否访问

	//核心数据
	Node* m_Path;//保存路径
	bool m_bFlag;//是否有解
	int m_n;//棋盘大小

	//马周游起始点
	int m_iStartRow;
	int m_iStartCol;

public:
	Node* GetSolvePath() {return m_Path;}
	bool IsHasSolve() {return m_bFlag;}
	int GetChessBoardSize() {return m_n;}
	
	static void SetStart() {s_bStop = false;}
	static void SetStop() {s_bStop = true;}

private:
	bool Check(int row, int col);//检查部分解的合法性
	void CountDirtWays(int row, int col);//计算各个方向的出口数
	void DirtWaySort(int k);//各个方向按出口数非降序排序
public:
	void HouseTravelIter();//解决问题(迭代法)
	
};

#endif // !defined(AFX_HORSETRAVEL_H__D7460B80_CC19_4C31_BD5D_14FABF6EA5F7__INCLUDED_)