通过分析欧拉所给出Knight’s Tour Problem的解法,结合哈密尔顿路和哈密尔顿圈的相关知识,得出其解法对应着二部图中的一条哈密尔顿圈.由此再充分利用8×8棋盘所对应的8×8表格的对称性及同格图的特性,对欧拉所给出的Knight’s...通过分析欧拉所给出Knight’s Tour Problem的解法,结合哈密尔顿路和哈密尔顿圈的相关知识,得出其解法对应着二部图中的一条哈密尔顿圈.由此再充分利用8×8棋盘所对应的8×8表格的对称性及同格图的特性,对欧拉所给出的Knight’s Tour Problem的解法作了进一步的探讨,得出了以欧拉的解法为基础的以任一棋格为骑士周游起点的另外一系列解法.最后,把Knight’sTour Problem推广到m×n棋盘上,考虑到移动规则的特殊性,利用图论的相关知识,得到3×4,8×16和16×16棋盘上的Knight’s Tour Problem的解法,同时给出8m×8n(m>2,n>2)棋盘上Knight’s Tour Problem的猜想.展开更多
The following theorem is proved: A knight’s tour exists on all 3 x n chessboards with one square removed unless: n is even, the removed square is (i, j) with i + j odd, n = 3 when any square other than the center squ...The following theorem is proved: A knight’s tour exists on all 3 x n chessboards with one square removed unless: n is even, the removed square is (i, j) with i + j odd, n = 3 when any square other than the center square is removed, n = 5, n = 7 when any square other than square (2, 2) or (2, 6) is removed, n = 9 when square (1, 3), (3, 3), (1, 7), (3, 7), (2, 4), (2, 6), (2, 2), or (2, 8) is removed, or when square (1, 3), (2, 4), (3, 3), (1, n – 2), (2, n – 3), or (3, n – 2) is removed.展开更多
文摘通过分析欧拉所给出Knight’s Tour Problem的解法,结合哈密尔顿路和哈密尔顿圈的相关知识,得出其解法对应着二部图中的一条哈密尔顿圈.由此再充分利用8×8棋盘所对应的8×8表格的对称性及同格图的特性,对欧拉所给出的Knight’s Tour Problem的解法作了进一步的探讨,得出了以欧拉的解法为基础的以任一棋格为骑士周游起点的另外一系列解法.最后,把Knight’sTour Problem推广到m×n棋盘上,考虑到移动规则的特殊性,利用图论的相关知识,得到3×4,8×16和16×16棋盘上的Knight’s Tour Problem的解法,同时给出8m×8n(m>2,n>2)棋盘上Knight’s Tour Problem的猜想.
文摘The following theorem is proved: A knight’s tour exists on all 3 x n chessboards with one square removed unless: n is even, the removed square is (i, j) with i + j odd, n = 3 when any square other than the center square is removed, n = 5, n = 7 when any square other than square (2, 2) or (2, 6) is removed, n = 9 when square (1, 3), (3, 3), (1, 7), (3, 7), (2, 4), (2, 6), (2, 2), or (2, 8) is removed, or when square (1, 3), (2, 4), (3, 3), (1, n – 2), (2, n – 3), or (3, n – 2) is removed.