骑士巡逻
维基百科,自由的 encyclopedia
骑士巡礼(英语:Knight's tour)是指在按照国际象棋中骑士的规定走法走遍整个棋盘的每一个方格,而且每个网格只能够经过一次。假若骑士能够从走回到最初位置,则称此巡礼为“封闭式巡礼”,否则,称为“开放巡礼”。对于8*8棋盘,一共有26,534,728,821,064种封闭巡礼,有19,591,828,170,979,904种开放式巡礼。[1][2][3]
由骑士巡礼引申出了一个著名的数学问题 :骑士巡礼问题--找出所有的骑士巡礼路径。编写一个程式来找出骑士巡礼路径经常在计算机系的学生的练习中出现。骑士巡礼问题的变种包括各种尺寸的棋盘甚至非正方形的棋盘。