广义象棋盘中的马步哈密顿圈问题及其实证研究  

Research on Knight′s Circuit Problem in Generalized Chessboards and Their Solutions

作　　者：宁宣熙[1] Angelika Ning 

机构地区：[1]南京航空航天大学经济与管理学院,南京210016

出　　处：《南京航空航天大学学报》2004年第3期383-387,共5页Journal of Nanjing University of Aeronautics & Astronautics

基　　金：国家自然科学基金 ( 79970 0 0 3 )资助项目

摘　　要：国际象棋中骑士旅游圈问题一直是图论中吸引众多国内外学者关注的研究问题 ,但到目前为止仍然是一个未完全解决的难题之一。特别是对 m×n,m≠n的广义象棋盘中是否存在骑士旅游圈的问题研究得更少 ,如中国象棋 9× 1 0的棋盘中的马步哈密顿圈的解就尚无相关的报导。本文利用作者研制的算法 ,给出了中国象棋9× 1 0棋盘中的马步哈密顿圈的解和 5× 6,6× 6,7× 6,5× 8,6× 8,7× 8,5× 1 0 ,6× 1 0 ,7× 1 0 ,8× 1 0 ,9× 1 0 ,9× 8和 9× 6这 1 3个被称为根棋盘中的马步哈密顿圈的解 ,并提出了用这 1 3个根棋盘构造更大棋盘中的马步哈密顿圈的方法。结果证明了在广义象棋 m× n棋盘中 ,当 m和 n均大于等于 5 ,且 m乘 n的积为偶数时 ,均存在马步哈密顿圈 。The knight′s circuit problem is an attractive research point for a long time and a completely unsolved hard nut. Especially, the problem of whether there is a knight′s circuit in a generalized chessboard of m×n, m≠n , is less studied. For example, there has been no published result about the solution to the knight′s circuit in a 9×10 Chinese chessboard. In this paper the solutions to the 9×10 Chinese chessboard and to the 5×6,6×6,7×6,5×8,6×8,7×8,5×10,6×10,7×10,8×10,9×10,9×8,9×6 generalized chessboards, which are defined as root chessboards, are given. The method for constructing a knight′s circuit in a larger chessboard from these 13 root chessboards is also presented. It is proved that there are knight′s circuits in the chessboards m×n, when m≥5,n≥5 and the product of m and n is an even number.

关 键 词：骑士旅游圈 马步哈密顿圈 图论 国际象棋 算法 

分 类 号：G891.1[文化科学—体育学] G80-05