国际象棋马的遍历 贪心算法

国际象棋的棋盘有8×8＝64个格子，给它们规定坐标（1，1）到（8，8）。马在这64个格子的某一个格子上，它的跳动规则是：如果它现在在（x，y）位置，它下一步可以跳到（x±1，y±2）或（x±2，y±1）（所有的“±”之间没有相关性），一般来说它下一步可以有八种跳法。但是它不能跳出这64个格子。 设计算法使它不管从哪出发都可以跳遍所有的格子（每个格子只能路过一次）最后回到起点。 基本要求：（80分） 合理设计界面，自行设计国际象棋棋盘，用鼠标选择马的起始位置，起始位置选定后，按“开始”按钮演示马的每一步行走路线。棋盘和马的显示尽量美观逼真。功能菜单或按钮自行设计，以合理为目的。 扩展要求：（15分） 对算法进行优化，根据j.c.Warnsdorff规则设计算法，该规则是在所有可跳的方格中,马只可能走这样一个方格:从该方格出发,马能跳的方格数为最少；如果可跳的方格数相等,则从当前位置看,方格序号小的优先。 VS2017开发

// Knight.cpp : 定义应用程序的类行为。
//


#include “stdafx.h“
#include “afxwinappex.h“
#include “afxdialogex.h“
#include “Knight.h“
#include “MainFrm.h“

#include “KnightDoc.h“
#include “KnightView.h“

#ifdef _DEBUG
#define new DEBUG_NEW
#endif


// CKnightApp

BEGIN_MESSAGE_MAP（CKnightApp CWinApp）
	ON_COMMAND（ID_APP_ABOUT &CKnightApp::OnAppAbout）
	// 基于文件的标准文档命令
	ON_COMMAND（ID_FILE_NEW &CWinApp::OnFileNew）
	ON_COMMAND（ID_FILE_OPEN &CWinApp::OnFileOpen）
	// 标准打印设置命令
	ON_COMMAND（ID_FILE_PRINT_SETUP &CWinApp::OnFilePrintSetup）
END_MESSAGE_MAP（）


// CKnightApp 构造

CKnightApp::CKnightApp（）
{
	// 支持重新启动管理器
	m_dwRestartManagerSupportFlags = AFX_RESTART_MANAGER_SUPPORT_ALL_ASPECTS;
#ifdef _MANAGED
	// 如果应用程序是利用公共语言运行时支持（/clr）构建的，则:
	//     1） 必须有此附加设置，“重新启动管理器”支持才能正常工作。
	//     2） 在您的项目中，您必须按照生成顺序向 System.Windows.Forms 添加引用。
	System::Windows::Forms::Application::SetUnhandledExceptionMode（System::Windows::Forms::UnhandledExceptionMode::ThrowException）;
#endif

	// TODO: 将以下应用程序 ID 字符串替换为唯一的 ID 字符串；建议的字符串格式
	//为 CompanyName.ProductName.SubProduct.VersionInformation
	SetAppID（_T（“Knight.AppID.NoVersion“））;

	// TODO: 在此处添加构造代码，
	// 将所有重要的初始化放置在 InitInstance 中
}

// 唯一的一个 CKnightApp 对象

CKnightApp theApp;


// CKnightApp 初始化

BOOL CKnightApp::InitInstance（）
{
	// 如果一个运行在 Windows XP 上的应用程序清单指定要
	// 使用 ComCtl32.dll 版本 6 或更高版本来启用可视化方式，
	//则需要 InitCommonControlsEx（）。否则，将无法创建窗口。
	INITCOMMONCONTROLSEX InitCtrls;
	InitCtrls.dwSize = sizeof（InitCtrls）;
	// 将它设置为包括所有要在应用程序中使用的
	// 公共控件类。
	InitCtrls.dwICC = ICC_WIN95_CLASSES;
	InitCommonControlsEx（&InitCtrls）;

	CWinApp::InitInstance（）;


	// 初始化 OLE 库
	if （!AfxOleInit（））
	{
		AfxMessageBox（IDP_OLE_INIT_FAILED）;
		return FALSE;
	}

	AfxEnableControlContainer（）;

	EnableTaskbarInteraction（FALSE）;

	// 使用 RichEdit 控件需要  AfxInitRichEdit2（）	
	// AfxInitRichEdit2（）;

	// 标准初始化
	// 如果未使用这些功能并希望减小
	// 最终可执行文件的大小，则应移除下列
	// 不需要的特定初始化例程
	// 更改用于存储设置的注册表项
	// TODO: 应适当修改该字符串，
	// 例如修改为公司或组织名
	SetRegistryKey（_T（“应用程序向导生成的本地应用程序“））;
	LoadStdProfileSettings（4）;  // 加载标准 INI 文件选项（包括 MRU）


	// 注册应用程序的文档模板。文档模板
	// 将用作文档、框架窗口和视图之间的连接
	CSingleDocTemplate* pDocTemplate;
	pDocTemplate = new CSingleDocTemplate（
		IDR_MAINframe
		RUNTIME_CLASS（CKnightDoc）
		RUNTIME_CLASS（CMainframe）       // 主 SDI 框架窗口
		RUNTIME_CLASS（CKnightView））;
	if （!pDocTemplate）
		return FALSE;
	AddDocTemplate（pDocTemplate）;


	// 分析标准 shell 命令、DDE、打开文件操作的命令行
	CCommandLineInfo cmdInfo;
	ParseCommandLine（cmdInfo）;



	// 调度在命令行中指定的命令。如果
	// 用 /RegServer、/Register、/Unregserver 或 /Unregister 启动应用程序，则返回 FALSE。
	if （!ProcessShellCommand（cmdInfo））
		return FALSE;

	// 唯一的一个窗口已初始化，因此显示它并对其进行更新
	m_pMainWnd->ShowWindow（SW_SHOW）;
	m_pMainWnd->UpdateWindow（）;
	// 仅当具有后缀时才调用 DragAcceptFiles
	//  在 SDI 应用程序中，这应在 ProcessShellCommand 之后发生
	return TRUE;
}

int CKnightApp::ExitInstance（）
{
	//TODO: 处理可能已添加的附加资源
	AfxOleTerm（FALSE）;

	return CWinA

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        679  2017-07-15 10:03  国际象棋终\国际象棋骑士遍历\Knight\Debug\Knight.log

     文件      48615  2017-07-15 10:03  国际象棋终\国际象棋骑士遍历\Knight\Debug\Knight.obj

     文件   54525952  2017-07-15 10:03  国际象棋终\国际象棋骑士遍历\Knight\Debug\Knight.pch

     文件    9021920  2017-07-15 10:03  国际象棋终\国际象棋骑士遍历\Knight\Debug\Knight.res

     文件       4602  2017-07-15 10:03  国际象棋终\国际象棋骑士遍历\Knight\Debug\Knight.tlog\CL.command.1.tlog

     文件     111328  2017-07-15 10:03  国际象棋终\国际象棋骑士遍历\Knight\Debug\Knight.tlog\CL.read.1.tlog

     文件       3302  2017-07-15 10:03  国际象棋终\国际象棋骑士遍历\Knight\Debug\Knight.tlog\CL.write.1.tlog

     文件        230  2017-07-15 10:03  国际象棋终\国际象棋骑士遍历\Knight\Debug\Knight.tlog\Knight.lastbuildstate

     文件       2148  2017-07-15 10:03  国际象棋终\国际象棋骑士遍历\Knight\Debug\Knight.tlog\link.command.1.tlog

     文件       7684  2017-07-15 10:03  国际象棋终\国际象棋骑士遍历\Knight\Debug\Knight.tlog\link.read.1.tlog

     文件       1224  2017-07-15 10:03  国际象棋终\国际象棋骑士遍历\Knight\Debug\Knight.tlog\link.write.1.tlog

     文件        374  2017-07-15 10:03  国际象棋终\国际象棋骑士遍历\Knight\Debug\Knight.tlog\rc.command.1.tlog

     文件       4642  2017-07-15 10:03  国际象棋终\国际象棋骑士遍历\Knight\Debug\Knight.tlog\rc.read.1.tlog

     文件        242  2017-07-15 10:03  国际象棋终\国际象棋骑士遍历\Knight\Debug\Knight.tlog\rc.write.1.tlog

     文件      94432  2017-07-15 10:03  国际象棋终\国际象棋骑士遍历\Knight\Debug\KnightDoc.obj

     文件     122646  2017-07-15 10:03  国际象棋终\国际象棋骑士遍历\Knight\Debug\KnightView.obj

     文件      75051  2017-07-15 10:03  国际象棋终\国际象棋骑士遍历\Knight\Debug\MainFrm.obj

     文件      63033  2017-07-15 10:03  国际象棋终\国际象棋骑士遍历\Knight\Debug\Qipan.obj

     文件     930443  2017-07-15 10:03  国际象棋终\国际象棋骑士遍历\Knight\Debug\stdafx.obj

     文件    2583552  2017-07-15 10:03  国际象棋终\国际象棋骑士遍历\Knight\Debug\vc141.idb

     文件    6787072  2017-07-15 10:03  国际象棋终\国际象棋骑士遍历\Knight\Debug\vc141.pdb

     文件    9070452  2017-07-12 13:37  国际象棋终\国际象棋骑士遍历\Knight\Knight.aps

     文件       4238  2017-07-12 14:09  国际象棋终\国际象棋骑士遍历\Knight\Knight.cpp

     文件        502  2017-07-12 14:09  国际象棋终\国际象棋骑士遍历\Knight\Knight.h

     文件      22798  2017-07-12 13:37  国际象棋终\国际象棋骑士遍历\Knight\Knight.rc

     文件       6644  2017-07-12 13:24  国际象棋终\国际象棋骑士遍历\Knight\Knight.vcxproj

     文件       3325  2017-07-12 13:24  国际象棋终\国际象棋骑士遍历\Knight\Knight.vcxproj.filters

     文件        228  2017-07-12 11:11  国际象棋终\国际象棋骑士遍历\Knight\Knight.vcxproj.user

     文件       2510  2017-07-12 14:09  国际象棋终\国际象棋骑士遍历\Knight\KnightDoc.cpp

     文件        845  2017-07-12 14:09  国际象棋终\国际象棋骑士遍历\Knight\KnightDoc.h

............此处省略33个文件信息