问题描述

国际象棋的棋盘为8×8的方格棋盘。现将“马”放在任意指定的方格中,按照“马”走棋的规则将“马”进行移动。要求每个方格只能进入一次,最终使得“马”走遍棋盘的64个方格。

为什么学国际象棋的孩子通常数学都很好?

编写一个C程序,实现马踏棋盘操作,要求用1〜64这64个数字标注马移动的路径,也就是按照求出的行走路线,将数字1,2,……64依次填入棋盘的方格中,并输出。

welcome

问题分析

为什么学国际象棋的孩子通常数学都很好?

一个刚刚学国际象棋不久的孩子家长就有这样的感慨:“起初送孩子来学国际象棋,是抱着开发智力,锻炼孩子思维能力的想法来的,但经过一段时间的学习后,意外发现孩子的数学成绩有稳步提升。”与这个家长有着同样体会的并不在少数,“以前在上数学课时,总感觉孩子‘算不过账来’,但在学习国际象棋一段时间之后,孩子有种突然开窍了的感觉,以前还想着实在不行就给孩子报个数学辅导班,但现在看来学国象就等于间接报了个奥数班。”

国际象棋与数学到底有什么关系?

国际象棋中,“马”的移动规则如图1所示。

















图1

如图1所示,图中实心的圆圈代表“马”的位置,它下一步可移动到图中空心圆圈所标注的8个位置上,该规则叫做“马走日”。但是如果“马”位于棋盘的边界附近,那么它下一步可移动到的位置就不一定有8个了,因为要保证“马”每一步都走在棋盘中。

前苏联的学者所著《国际象棋与数学》一书的前言中写道:“国际象棋的棋盘、棋子和它的走法,常常用来图示各种不同的数学概念和解题。国际象棋对发展电子计算机程序设计的现代方法,具有很重要的地位。”

看“马”如何走完方格——带注释和解析

国际象棋和数学有很多融会贯通之处。卓越的数学家哈尔基在其论文《数学家的自白》中写道:“拆解国际象棋的棋题正像是解数学题一样,而下国际象棋就仿佛是在进行数学运算。”这是哈尔基把国际象棋和数学这两者进行比较后得出的结论。

国际象棋与数学相通的方面是:国际象棋棋盘、棋子及其走法常常是用来图示各种不同的数学概念和解题。在有关控制论、博弈论、计算数学、战役研究、图论和组合分析的书籍中,也有很多国际象棋术语。

C语言/C++学习加群556791282

马踏棋盘的问题其实就是要将1,2,……,64填入到一个8×8的矩阵中,要求相邻的两个数按照“马”的移动规则放置在矩阵中。

例如数字a放置在矩阵的(i,j)位置上,数字a+1只能放置在矩阵的(i-2,j+1),(i-1,j+2),(i+1,j+2),(i+2,j+1),(i+2,j-1),(i+1,j-2),(i-1,j-2),(i-2,j-1)之中的一个位置上。将矩阵填满并输出。

首先,国际象棋和数学的思维形式十分接近,所以,有数学天赋的人往往也具有下好国际象棋的才能。当然,并非所有数学系的高材生都会去钻研国际象棋,因为同时想精通这两者,一般说来是十分困难的。

这样在矩阵中从1,2……遍历到64,就得到了马踏棋盘的行走路线。因此本题的最终目的是输出一个8*8的矩阵,在该矩阵中填有1, 2……64这64个数字,相邻数字之间遵照“马走日”的规则。

为什么学国际象棋的孩子通常数学都很好?

一代棋王卡尔波夫在他读大学时就曾说过:“我的思路适应数学,有希望攻克尖端,因此,我进修数学力学专业。我发觉国际象棋和数学之间有着共同点,问题是经常参加棋赛,数学练习实在无暇对付。数学理论还能忙里偷闲突击,但不能做练习又有何益呢?还是棋,棋艺事业!”于是,卡尔波夫决定转系改学经济学,以便腾出更多的时间、精力从事棋艺活动。

算法设计

其次,数学和国际象棋还有一个共同点,即它们都有一种通俗的引人入胜的数学形式。棋盘上的数学游戏、解题和智力测验均属这种数学形式。我们把这种数学叫做国际象棋数学。几乎在每一本奥林匹克数学习题集、智力游戏和趣味数学的书中,都可找到与国际象棋棋盘和棋子有关的精彩的难题。其中很多题都包含有趣的历史故事,因而引起一些著名学者的注意。

解决马踏棋盘问题的一种比较容易理解的方法是应用递归的深度优先搜索的思想。因为“马”每走一步都是盲目的,它并不能判断当前的走步一定正确,而只能保证当前这步是可走的。

例如瑞士伟大的数学家奥伊勒解过关于马的行进路线(“骑士巡回”)的棋题,德国伟大的数学家则解过八个后的棋题。”值得注意的是,奥伊勒醉心于国际象棋是在18世纪,而高斯是在19世纪中,在整整100年的过程中,数学权威们似乎都不曾仔细地研究过国际象棋(这里指的是国际象棋走法的科学性)。由于控制论和计算技术突飞猛进地发展,在本世纪中叶,情况发生了急骤的变化。国际象棋便成为运用数学来解析电子计算机程序设计现代方法的一种最方便的模式。杰出的学者,如维涅尔、秋林格和申农等经常在自己的著作中涉及国际象棋。

“马”走的每一步棋都是从它当前位置出发,向下一步的8个位置中的1个行走(在它下一步有8个位置可走的情况下)。因此“马”当前所走的路径并不一定正确,因为它可能还有剩下的可选路径没有尝试马”的行走过程实际上就是一个深度探索的过程。“探索树”的根节点为“马”在棋盘中的初始位置。

接下来“马”有两种行走方式,于是根节点派生出两个分支。而再往下一步行走,根节点的两个孩子又能够分别派生出其他不同的“行走路线”分支,如此派生下去,就得到了 “马”的所有可能的走步状态。

可以想见,该探索树的叶子节点只可能有两种状态:一是该节点不能再派生出其他的“走步”分支了,也就是“马”走不通了;二是棋盘中的每个方格都被走到,即“马”踏遍棋盘。于是从该探索树的根节点到第二种情况的叶节点构成的路径,就是马踏棋盘的行走过程。

如何才能通过搜索这棵探索树,找到这条马踏棋盘的行走路径呢?可以采用深度优先搜索的方法以先序的方式访问树中的各个节点,直到访问到叶节点象棋技巧

如果叶节点是第二种情况的叶节点,则搜索过程可以结束,因为找到了马踏棋盘的行走路径;如果叶节点为第一种情况的叶节点,即走不通了,则需要返回到上一层的节点,顺着该节点的下一条分支 继续进行深度优先搜索下去。

很多数学家都是国际象棋的好手

在尖端科学领域内的著名专家和学者中,不乏国际象棋的好手,例如,数学家阿?阿?马尔科夫院士,机械专家阿?尤?伊斯林斯基院士,物理学家、诺贝尔奖金获得者波?拉?卡比察院士等等。还有一位数学家,名叫阿伯拉罕?特?莫伊勒,他是17世纪概率论的先驱者,在讨论谁发明了微积分,是莱布尼兹还是牛顿这个问题上,他是个中心人物。由于他的数学研究虽很有趣但不合实用,因此他入不敷出,遂成为职业棋手。这位数学家生性怪癖,他发誓要连续每天多睡一刻钟。开始还可以,直到睡眠时间增加到23小时3刻钟时,你可以猜到,他就一睡不起了。莫伊勒与罗杰以及更伟大的数学家里奥奈德.奥伊勒一样,他解答了“骑士巡回”(马的行进路线)这一数学和国际象棋相结合的课题的答案。

因此在设计“马踏棋盘”的算法时可以借鉴图的深度优先遍历算法和二叉树的先序遍历算法。但是在这里并不需要真正地构建这样一棵探索树,只需要借用探索树的思想。

为什么学国际象棋的孩子通常数学都很好?

与此同时,很多国际象棋的高级棋手都不同程度接受过数学学科的教育和训练。国际象棋历史上第一位世界棋王斯坦尼茨就对数学很感兴趣。第二位世界棋王拉斯克更是一位数学家。尽管他在数学系只念了4个学期,但在厄兰根大学顺利地通过了数学和哲学博士论文的答辩,获得双博士学位。爱因斯坦对拉斯克的数学和哲学专著曾给予很高的评价:“我喜欢拉斯克的不可摧毁的独立精神,对于人类来说,这种品质如此少见。”

在实际的操作过程中,所谓的探索树实际就是深度优先搜索的探索路径,每个节点实际就是当前的棋盘状态,而所谓的叶节点或者是在当前棋盘状态下,“马”无法再进行下一步行走;或者是马踏棋盘成功。

完整程序

备注:因为程序涉及深度搜索,运行中叶节点不能再派生出其他的“走步”分支时,也就是“马”走不通了,则返回上一节点,比较复杂,运行较慢。(一般需要一分钟左右出现结果,请耐心等待。)

世界棋王尤伟最初是阿姆斯特丹一所女子中学的数学教师,后来成为一名大学教授。弈棋之余,他仍在数学领域继续深造。二战后,他曾领导一个计算中心并兼任一家大公司的科学顾问。他的棋艺特点是擅长计算,这与他的数学造诣分割不开。

#include <stdio.h>

#define X 8

#define Y 8

为什么学国际象棋的孩子通常数学都很好?

卡尔森,人称“棋坛莫扎特”从5岁起学习国际象棋,通过做数学题不断提高自己分析能力,下棋速度之快似乎完全不假思索。让人匪夷所思的是,卡尔森居然一次能够心算20步棋,运算速度简直比电脑还快。更令人惊讶的是,卡尔森甚至还能清楚地记得 6年前比赛的每一步棋。在卡尔森现任教练、前俄罗斯棋王卡斯帕罗夫看来,卡尔森拥有超人的象棋“方位感”,是百年难遇的天才棋手,前途不可限量。

int chess[X][Y];

来源于网络,文中观点不代表本公号,如侵权请联系删除。

长按下面的二维码,然后点击“识别图文的二维码”,就可以快速关注本微信号!

国际象棋爱好者交流平台,我所做的一切都是为了让国际象棋变得更简单。

int nextxy(int *x, int *y, int count) /*找到基于x,y位置的下一个可走的位置*/

邮箱:bjqychess@163.com,及时交流qq:北京国际象棋家长群B, 437920362;北京国际象棋(仅限教练、裁判以及国际象棋工作者):436237869;北京北奥棋迷俱乐部群 437940603。

{

switch(count)

{

case 0:

if(*x+2<=X-1 && *y-1>=0 && chess[*x+2][*y-1]==0)

{

*x=*x+2;

*y=*y-1;

return 1;

}

break;

case 1:

if(*x+2<=X-1 && *y+1<=Y-1 && chess[*x+2][*y+1]==0)

{

*x=*x+2;

*y=*y+1;

return 1;

}

break;

case 2:

if(*x+1<=X-1 && *y-2>=0 && chess[*x+1][*y-2]==0)

{

*x=*x+1;

*y=*y-2;

return 1;

}

break;

case 3:

if(*x+1<=X-1 && *y+2<=Y-1 && chess[*x+1][*y+2]==0)

{

*x=*x+1;

*y=*y+2;

return 1;

}

break;

case 4:

if(*x-2>=0 && *y-1>=0 && chess[*x-2][*y-1]==0)

{

*x=*x-2;

*y=*y-1;

return 1;

}

break;

case 5:

if(*x-2>=0 && *y+1<=Y-1 && chess[*x-2][*y+1]==0)

{

*x=*x-2;

*y=*y+1;

return 1;

}

break;

case 6:

if(*x-1>=0 && *y-2>=0 && chess[*x-1][*y-2]==0)

{

*x=*x-1;

*y=*y-2;

return 1;

}

break;

case 7:

if(*x-1>=0 && *y+2<=Y-1 && chess[*x-1][*y+2]==0)

{

*x=*x-1;

*y=*y+2;

return 1;

}

break;

default:

break;

}

return 0;

}

int TravelChessBoard(int x, int y, int tag) /*深度优先搜索地"马踏棋盘"*/

{

int x1=x, y1=y, flag=0, count=0;

chess[x][y]=tag;

if(tag == X*Y)

{

return 1;

}

flag=nextxy(&x1, &y1, count);

while(flag==0 && count<7)

{

count=count+1;

flag=nextxy(&x1, &y1, count);

}

while(flag)

{

if(TravelChessBoard(x1, y1, tag+1))

return 1;

x1=x;

y1=y;

count=count+1;

flag=nextxy(&x1, &y1, count); /*寻找下一个(x,y)*/

while(flag==0 && count<7)

{ /*循环地寻找下一个(x,y)*/

count=count+1;

flag=nextxy(&x1, &y1, count);

}

}

if(flag == 0)

chess[x][y]=0;

return 0;

}

int main()

{

int i, j;

for(i=0; i<X; i++)

for(j=0; j<Y; j++)

chess[i][j]=0;

if(TravelChessBoard(2, 0, 1))

{

for(i=0; i<X; i++)

{

for(j=0; j<Y; j++)

printf("%-5d", chess[i][j]);

printf("\n");

}

printf("The horse has travelled the chess borad\n");

}

else

printf("The horse cannot travel the chess board\n");

return 0;

}

运行结果:

43 50 47 38 57 52 61 32

48 37 44 51 46 33 58 53

1 42 49 56 39 60 31 62

36 15 40 45 34 29 54 59

41 2 35 16 55 24 63 30

14 5 12 9 22 19 28 25

3 10 7 20 17 26 23 64

6 13 4 11 8 21 18 27

The horse has travelled the chess borad

看“马”如何走完方格——带注释和解析

C语言/C++学习加群556791282