国际象棋中马的遍历问题国际象棋启蒙:棋子的走法 与战术 象棋棋谱(图1)

本课程是从少年编程网转载的课程,目标是向中学生详细介绍计算机比赛涉及的编程语言,数据结构和算法。编程学习最好使用计算机,请登陆 www.3dian14.org (免费注册,免费学习)。

国际象棋棋子的走法 :

国际象棋中马的遍历问题国际象棋启蒙:棋子的走法 与战术 象棋棋谱(图2)

1王 KING

回溯是一类算法模式,它通过尝试不同的解决方案,直到找到“有效”的解决方案。 

通常能够使用回溯技术解决的问题具有以下共同特性:这些问题只能通过尝试每个可能的方案来解决,并且每个方案只尝试一次。

(1) 除易位时外,王可走到未被对方棋子攻击的任何相邻格子。

针对这类问题,一个”傻瓜式“的办法是尝试所有方案并输出符合给定问题条件的方案。 一般来说,这种办法的效率不高,有些情形下,可能无法在时间和资源限制下找到解答。

而回溯技术以增量方式工作,是对上面”傻瓜式解决方案“的优化。

(2) 易位是由王已方任何一个车一起进行仍被视作王的一着的走法,其进行方式如下:王从原始位置向任何一围的方向横移两格,然后那人横越过王而置于王刚经过的格子。

下面我们用一个经典问题来说明:

国际象棋中的马的遍历(Knight's Tour)问题

(3) 如果一方先触摸车一起然后再触摸王,那么他不能用那个车进行易位,这种情况须按第7.2和7.3条处理 

(4) 如果一方在准备易位时触摸了王,或者同时触摸了王和车,然后发现易位不合规则,他可以选择走王或者向另一翼易位,前提是向那一翼易位是合乎规则的,如果王没有合乎规则的走法,该方有权造反走任何规则的着法。

马被放置在国际象棋棋盘的某个格子内,并按照国际象棋的规则移动,必须完全访问棋盘中的每个方块格子正好一次。

(5) 不符合规则的易位: (一) 王已经移动过,或者 (二) 用来易位的车已经移动过。 

(6) 下列情况暂不能易位: (一)王的原始格子或者将要越过的格子或者将要占据的格子正受到对方棋子的攻击,或者 (二)王和用来易位的车之间尚有别的棋子 

根据国际象棋中马的移动规则,它从当前位置最多可以移动到八个位置,见下图。

国际象棋中马的遍历问题国际象棋启蒙:棋子的走法 与战术 象棋棋谱(图3)

因此,现在我们要找到一种方案,使得马可以依照移动规则,遍历上述棋盘中的每个格子,而且不能有重复,也不能有遗漏。

国际象棋中马的遍历问题国际象棋启蒙:棋子的走法 与战术 象棋棋谱(图4)

以下是有8 x 8个格子的棋盘。从任意一个格子开始,马依照连线移动,这样马的足迹正好覆盖棋盘上的所有格子一次。

国际象棋中马的遍历问题国际象棋启蒙:棋子的走法 与战术 象棋棋谱(图5)

我们先来看看采用傻瓜式方案——称为朴素(Naive)算法来解决这个问题的思路,然后再看看如何运用回溯算法来改进它。

国际象棋中马的遍历问题国际象棋启蒙:棋子的走法 与战术 象棋棋谱(图6)

算法思路

朴素算法的思路

国际象棋中马的遍历问题国际象棋启蒙:棋子的走法 与战术 象棋棋谱(图7)

2 后  QUEEN

朴素算法是依次尝试所有的走法象棋棋谱,然后从中找到可以满足约束条件的方案。算法描述如下:

后可走到它所在的直线,横线或斜线上的任何格子。

1)如果还有没有尝试过的遍历方案,就执行下面第2)步     

否则,输出此问题没有解答

2)找到下一个遍历方案

3)如果这个方案可以覆盖所有棋盘上的方格,那么输出该方案的遍历路径,结束;

国际象棋中马的遍历问题国际象棋启蒙:棋子的走法 与战术 象棋棋谱(图8)

     否则,回到1)

国际象棋中马的遍历问题国际象棋启蒙:棋子的走法 与战术 象棋棋谱(图9)

回溯方法的思路

3 车 ROOK 

车可走到它所在的直线和横线上任何格子。 

回溯方法以增量方式工作以解决问题,它的基本思路如下:

通常情况下,我们从一个空的解决方案向量中开始逐个添加条目(条目的含义因问题而异。比如对于马的棋盘遍历问题,一个条目就是在棋盘上马的一次移动)。

当我们添加一个条目时,我们检查添加的当前项目是否违反了问题约束条件,如果违反了某个约束条件,那么我们删除该条目并尝试其他替代方案。

国际象棋中马的遍历问题国际象棋启蒙:棋子的走法 与战术 象棋棋谱(图10)

如果没有其他替代方案可以解决问题,那么我们将返回上一阶段并删除上一阶段添加的条目。

如果我们回到初始阶段,那么我们说没有解决方案存在。 

4 象 BISHOP

如果添加条目并不违反约束条件,那么我们将通过递归逐个添加条目。 如果最后能成功得到完全的解决方案向量,那么我们将输出对应的解决方案。

象可走到它所在斜线上的任何格子。

国际象棋中马的遍历问题国际象棋启蒙:棋子的走法 与战术 象棋棋谱(图11)

马的棋盘遍历问题的回溯算法

国际象棋中马的遍历问题国际象棋启蒙:棋子的走法 与战术 象棋棋谱(图12)

我们用一个8X8的二维数组表示解,它将记录马在棋盘上依次移动的次序。

5 马  KNIGHT

二位数组的每个元素对应棋盘上的一个方格。每个元素是一个数字,它表示了马的移动次序。

马的走法由两个不同 步骤组成,先沿横线或直线走一格,然后沿斜线离原格方向一格,在走第一格时即使该格已有棋子占据也仍可行走

下面的图记录了一个解,也就是马依照 0->1->2->...->63的次序可以正好访问所有格子,并且每个格子只访问一次。

国际象棋中马的遍历问题国际象棋启蒙:棋子的走法 与战术 象棋棋谱(图13)

国际象棋中马的遍历问题国际象棋启蒙:棋子的走法 与战术 象棋棋谱(图14)

6 兵 PAWN

以下是马的遍历问题的回溯算法:

(1)兵只能朝前走

 (2)除吃子以外,兵可从原始位置起沿所在直线和向前走一格或两格(所占据格子必须是空格)。以后每次只能沿直线向前走一格。吃子时,只能吃它斜前方一格的棋子。

(3)当兵处于攻击对方兵从原始格子一次走两格所经过的格子时,可以把后者走两格当作走一格而吃掉它,这种吃法只能在对方以该方式走兵后立即进行,称为"吃过路兵"。 

(4)兵一旦到达底线,必须立即变换为与它相同颜色的后、车、马、或象,这种变换仍被视作同一着,变换何种棋子由棋手选择,不必考虑棋盘上是否还有同类的其他棋子,这种由兵变换为别的棋子的走法称为"升变",升变的棋子立即生效。

国际象棋中马的遍历问题国际象棋启蒙:棋子的走法 与战术 象棋棋谱(图15)

如果访问了所有方块都已被访问到,打印输出对应的解决方案,否则

国际象棋常用战术: 

a)将找到下一个可以移动目的地并将它添加到求解数组并递归检查本次移动是否会找到合适的解决方案。(依照国际象棋的规则,马可以最多可以移动到八个位置,我们需要从8个目的地中选择一个)

b)如果在上述步骤中选择的移动没有导致找到合适的解决方案,那么从解决方案数组中删除此次移动并尝试其他的移动目的地。

c)如果没有找到其他合适的目的地,则返回false(返回false将在递归中删除以前添加的条目。如果为false返回给最初的初始调用,那么就表示该问题“没有解决方案存在”)

国际象棋中马的遍历问题国际象棋启蒙:棋子的走法 与战术 象棋棋谱(图16)

代码实现

闪击战术

以下是马的遍历问题的c/C++代码实现。 它以二维矩阵形式打印出一种可能的解决方案。 基本上,输出是一个 8 * 8矩阵,数字从0到63,这些数字显示了马在棋盘上的遍历步数。

#include<stdio.h> 

击双战术

牵制战术

#define N 8 

  

int solveKTUtil(int x, int y, int movei, int sol[N][N], 

                int xMove[],  int yMove[]); 

  

//看看棋盘位置[i,j]是否可用

消除保护战术

bool isSafe(int x, int y, int sol[N][N]) 

    return ( x >= 0 && x < N && y >= 0 && 

             y < N && sol[x][y] == -1); 

堵截战术

//打印出结果

void printSolution(int sol[N][N]) 

    for (int x = 0; x < N; x++) 

    { 

封锁战术

        for (int y = 0; y < N; y++) 

            printf(" - ", sol[x][y]); 

        printf("\n"); 

引入战术

引离战术

腾挪战术

    } 

  

等着战术

//该函数使用回溯方法解决马的遍历问题。

//如果返回false,表示无解

逼和战术

//否则返回true并打印出结果

bool solveKT() 

兵的升变战术

抽将战术

闪将战术

    int sol[N][N]; 

双将战术

  

顿挫战术

暴露战术

   //初始化解的向量

    for (int x = 0; x < N; x++) 

        for (int y = 0; y < N; y++) 

            sol[x][y] = -1; 

  

//按照国际象棋规则,定义马的8个合法的移动位置

方形区战术

对王战术

// xMove[] 和yMove[]分别定义x和y的移动方向

    int xMove[8] = {  2, 1, -1, -2, -2, -1,  1,  2 }; 

控制格战术

突破战术

紧逼战术

    int yMove[8] = {  1, 2,  2,  1, -1, -2, -2, -1 }; 

逼走劣着战术

    //从棋盘的[0][0]位置开始

对应格战术

    sol[0][0]  = 0; 

迂回战术

  

 //从0,0开始运行函数solveKTUtil()找答案

    if (solveKTUtil(0, 0, 1, sol, xMove, yMove) == false) 

    { 

        printf("Solution does not exist"); 

        return false; 

    } 

    else

        printSolution(sol); 

  

    return true; 

  

//函数solveKTUtil用来寻找目标方案

int solveKTUtil(int x, int y, int movei, int sol[N][N], 

                int xMove[N], int yMove[N]) 

   int k, next_x, next_y; 

   if (movei == N*N) 

       return true; 

  

   //从当前位置x,y开始尝试所有的8个移动位置

   for (k = 0; k < 8; k++) 

   { 

       next_x = x + xMove[k]; 

       next_y = y + yMove[k]; 

       if (isSafe(next_x, next_y, sol)) 

       { 

         sol[next_x][next_y] = movei; 

         if (solveKTUtil(next_x, next_y, movei+1, sol, 

                         xMove, yMove) == true) 

             return true; 

         else

             sol[next_x][next_y] = -1;// backtracking 

       } 

   } 

  

   return false; 

  

//主程序

int main() 

    solveKT(); 

    return 0; 

点击阅读原文观看动画课件。