| 词条 | Longest uncrossed knight's path | ||||
| 释义 |
The longest uncrossed (or nonintersecting) knight's path is a mathematical problem involving a knight on the standard 8×8 chessboard or, more generally, on a square n×n board. The problem is to find the longest path the knight can take on the given board, such that the path does not intersect itself. A further distinction can be made between a closed path, which ends on the same field as where it begins, and an open path, which ends on a different field from where it begins. Known solutionsThe longest open paths on an nxn board are known only for n ≤ 9. Their lengths for n = 1, 2, …, 9 are: 0, 0, 2, 5, 10, 17, 24, 35, 47 {{OEIS|A003192}} The longest closed paths are known only for n ≤ 10. Their lengths for n = 1, 2, …, 10 are: 0, 0, 0, 4, 8, 12, 24, 32, 42, 54 {{OEIS|A157416}}
GeneralizationsThe problem can be further generalized to rectangular n×m boards, or even to boards in the shape of any polyomino. Other standard chess pieces than the knight are less interesting, but fairy chess pieces like the camel ((3,1)-leaper), giraffe ((4,1)-leaper) and zebra ((3,2)-leaper) lead to problems of comparable complexity. See also
References
External links
4 : Mathematical chess problems|Recreational mathematics|Chess problems|Computational problems in graph theory |
||||
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。