Friday 1 December 2017

骑士跳的起源

  骑士巡逻(英语:Knight's tour)是指在按照国际象棋中骑士的规定走法走遍整个棋盘的每一个方格且每个网格只能经过一次。假若骑士能够从走回到最初位置,则称此巡逻为“封闭巡逻”,否则,称为“开巡逻”。对于8*8棋盘,一共有26,534,728,821,064 种封闭巡逻,但是到底有多少种开巡逻仍然未知。

  由骑士巡逻引申出了一个著名的数学问题 :骑士巡逻问题--找出所有的骑士巡逻路径。编写一个程序来找出骑士巡逻路径经常在计算机系的学生的练习中出现。骑士巡逻问题的变种包括各种尺寸的棋盘甚至非正方形的棋盘。

No comments:

Post a Comment