#include<stdio.h>
?
?
//定義棋盤的行數(shù)和列數(shù)
#define CHESS_BOARD_LINE_NUM 10
#define CHESS_BOARD_COLUM_NUM 10
?
//定義棋盤上位置的結(jié)構(gòu)體
typedef struct?
{
?? ?int nPosX;
?? ?int nPosY;
}SPOS;
?
//使用一個二維數(shù)組來表示棋盤
int g_ArrChessBoard[CHESS_BOARD_LINE_NUM][CHESS_BOARD_COLUM_NUM];
?
//用來表示Horse跳到下一位置為第幾跳，起跳位置為第0跳
int g_HorseSteps = 0;
?
//定義Horse的起跳位置，可以輸入；若輸入非法則使用默認起跳位置(0,0)
SPOS g_StartPos={0,0};
?
//檢查位置有效性, 若位置在棋盤內(nèi)則返回1，不在棋盤則返回0
int checkPos(SPOS tPos)
{
?? ?//X/Y坐標不在棋盤內(nèi)則位置不在棋盤內(nèi)
? ? return !(0 > tPos.nPosX || tPos.nPosX +1 > CHESS_BOARD_LINE_NUM || 0 > tPos.nPosY || tPos.nPosY + 1 > CHESS_BOARD_COLUM_NUM);
}
?
//檢查位置是否已經(jīng)跳過，若跳過則位置上記錄經(jīng)過該位置時為第幾跳，若未被跳過則值為棋盤初始值-1
int checkUsed(SPOS tPos)
{
?? ?return g_ArrChessBoard[tPos.nPosX][tPos.nPosY] != -1;
}
?
//根據(jù)偏移量獲取位置有效性
void getNextStepListByOffSet(SPOS curPos, SPOS NextStepList[8], int* NumOfValidStep, int offSetX, int offSetY)
{
?? ?//定義Horse的可跳方向
?? ?//分別為右上（1,1）、右下（1，-1）、左上（-1，1）、左下（-1，-1）
?? ?//原始坐標+方向位移得到新的跳點
?? ?static SPOS DirectionList[4] = {{1,1},{1,-1},{-1,1},{-1,-1}};
? ? SPOS tPos; //存儲可能的跳點，該跳點不一定有效
?? ?int i = 0;
?
?? ?for (; i < 4; i++)
?? ?{
?? ??? ?tPos.nPosX = curPos.nPosX + offSetX*DirectionList[i].nPosX;
?? ??? ?tPos.nPosY = curPos.nPosY + offSetY*DirectionList[i].nPosY;
?
?? ??? ?//若跳點在棋盤內(nèi)，且跳點未被跳過則可以作為下一跳點
?? ??? ?if (checkPos(tPos) && !checkUsed(tPos))
?? ??? ?{
?? ??? ??? ?NextStepList[(*NumOfValidStep)++] = tPos;
?? ??? ?}
?? ?}
}
?
//獲取下一跳位置列表, 下一跳位置列表最多存在8個，所以固定傳入數(shù)組8
//只返回有效的位置列表， NumOfValidStep中存儲有效位置列表個數(shù)
void getNextStepList(SPOS curPos, SPOS NextStepList[8], int* NumOfValidStep)
{
?? ?//X坐標移動2格，Y坐標移動1格檢查
? ? getNextStepListByOffSet(curPos, NextStepList, NumOfValidStep, 2, 1);?? ?
?? ?
?? ?//X坐標移動1格，Y坐標移動2格檢查
?? ?getNextStepListByOffSet(curPos, NextStepList, NumOfValidStep, 1, 2);?? ?
}
?
//冒泡排序
void sortByNextStepNum(SPOS NextStepList[8], int* NumOfValidStep, int nSubValidStep[8])
{
?? ?int tmpN;
?? ?SPOS tmpPos;
?? ?int i = 0;
?? ?int j = 0;
?? ?int MaxStepNum = *NumOfValidStep;
?? ?for (; i < MaxStepNum; i++)
?? ?{
?? ??? ?for (j = 1; j < MaxStepNum - i; j++)
?? ??? ?{
?? ??? ??? ?if (nSubValidStep[j] < nSubValidStep[j-1])
?? ??? ??? ?{
?? ??? ??? ??? ?//進行位置互換，進行冒泡
?? ??? ??? ??? ?tmpN = nSubValidStep[j];
?? ??? ??? ??? ?nSubValidStep[j] = nSubValidStep[j-1];
?? ??? ??? ??? ?nSubValidStep[j-1] = tmpN;
?? ??? ??? ??? ?
?? ??? ??? ??? ?//進行對應(yīng)的Pos互換
?? ??? ??? ??? ?tmpPos = NextStepList[j];
?? ??? ??? ??? ?NextStepList[j] = NextStepList[j-1];
?? ??? ??? ??? ?NextStepList[j-1] = tmpPos;
?? ??? ??? ?}
?? ??? ?}
?? ?}
}
?
//使用貪心算法獲取下一位置列表，即對返回的有效列表根據(jù)出口進行升序排列
void getNextGreedList(SPOS curPos, SPOS NextStepList[8], int* NumOfValidStep)
{
? ? SPOS subNextStepList[8]; //用于緩存下一跳點列表的中每個跳點的下一跳點列表
?? ?int ?nSubValidStep[8] = {0,0,0,0,0,0,0,0}; ?//用于存儲下一跳點列表中每個跳點的下一跳點個數(shù)?? ?
?? ?int ?i = 0;?
?
?? ?//先獲取所有的可跳節(jié)點
?? ?getNextStepList(curPos, NextStepList, NumOfValidStep);
?? ?
?? ?//獲取子跳點的下一跳點個數(shù)
?? ?for(; i< *NumOfValidStep; i++)
?? ?{
?? ??? ?getNextStepList(NextStepList[i], subNextStepList, &nSubValidStep[i]);
?? ?}
?? ?
?? ?//使用冒泡排序
?? ?sortByNextStepNum(NextStepList, NumOfValidStep, nSubValidStep);
}
?
?
//以輸入Pos為起點進行馬踏棋盤
//返回0 ?表示找到正確跳躍路徑
//返回-1 表示已經(jīng)完成所有跳點的嘗試，不存在可行方案
//返回1 ?表示選中的下一跳并非可行路徑，需要重新選擇一個跳點進行嘗試
int HorseRoaming(SPOS curPos)
{
? ? SPOS NextStepList[8]; ? //記錄curPos的下一跳點列表，最多存在8個可能跳點，使用數(shù)組表示
?? ?int ?NumOfValidStep = 0;//記錄下一跳列表中的跳點個數(shù)
?? ?int ?i = 0;
?? ?int ?nRet = 1;
?? ?
?? ?//添加跳點的Trace記錄，并刷新跳點的計數(shù)
?? ?g_ArrChessBoard[curPos.nPosX][curPos.nPosY] = g_HorseSteps++;
?? ?
?? ?//若已經(jīng)經(jīng)過棋盤上所有節(jié)點則表示找到馬踏棋盤路徑，退出
?? ?if (g_HorseSteps == CHESS_BOARD_LINE_NUM*CHESS_BOARD_COLUM_NUM)
?? ?{
?? ??? ?return 0;
?? ?}
?? ?
?? ?
?? ?//使用普通DFS進行路徑查找
?? ?//getNextStepList(curPos, NextStepList, &NumOfValidStep);
? ??
?? ?//使用貪心算法獲取有效列表
?? ?getNextGreedList(curPos, NextStepList, &NumOfValidStep);
?? ?
?? ?for (; i < NumOfValidStep; i++)
?? ?{
?? ??? ?//進行遞歸求解
?? ??? ?nRet = HorseRoaming(NextStepList[i]);
? ? ? ? if (1 != nRet)
? ? ? ? {
?? ??? ??? ?//求解結(jié)束
?? ??? ??? ?return nRet;
? ? ? ? }?? ??? ?
?? ?}
?? ?
? ? //若回到起點位置，且起點的所有可能跳點均已嘗試過，則說明未找到遍歷棋盤方案
?? ?if (curPos.nPosX == g_StartPos.nPosY && curPos.nPosY == g_StartPos.nPosY)
?? ?{
?? ??? ?return -1;
?? ?}
?? ?
? ? //回溯：回退棋盤上的Trace記錄，并返回上層
?? ?g_ArrChessBoard[curPos.nPosX][curPos.nPosY] = -1;
?? ?g_HorseSteps--;
?? ?return 1;
}
?
//初始化棋盤上所有位置的值為-1
void initBoard()
{
?? ?int i,j; //設(shè)置循環(huán)控制變量
?? ?for (i = 0; i< CHESS_BOARD_LINE_NUM; i++)
?? ?{?? ?
?? ??? ?for (j = 0; j< CHESS_BOARD_COLUM_NUM; j++)
?? ??? ?{
?? ??? ??? ?g_ArrChessBoard[i][j] = -1;
?? ??? ?}
?? ?}
}
?
//將棋盤上記錄的跳躍Trace打印到文件中
void ?printSteps()
{
?? ?int i,j;?? ?
?? ?FILE* pfile = fopen("OutPut.txt","wb+");
?? ?
?? ?for (i = 0; i< CHESS_BOARD_LINE_NUM; i++)
?? ?{
?? ??? ?for (j = 0; j< CHESS_BOARD_COLUM_NUM; j++)
?? ??? ?{
?? ??? ??? ?fprintf(pfile,"%2d ", g_ArrChessBoard[i][j]);
?? ??? ?}
?? ??? ?fprintf(pfile,"\r\n");
?? ?}
?? ?
?? ?fclose(pfile);
}
?
int main()
{
?? ?//進行棋盤上跳躍Trace初始化
?? ?initBoard();
?? ?if (HorseRoaming(g_StartPos) == 0)
?? ?{
?? ??? ?//打印結(jié)果
?? ??? ?printSteps();
?? ?}
?? ?else
?? ?{
?? ??? ?//未找到解
?? ??? ?printf("Not found Result \n");
?? ?}
?? ?return 0;
}