騎士旅遊（Knight tour）在十八世紀初倍受數學家與拼圖迷的注意，它什麼時候被提出已不可考，騎士的走法為西洋棋的走法，騎士可以由任一個位置出發，它要如何走完所有的位置？
騎士的走法，基本上可以使用遞歸來解決，但是純綷的遞歸在維度大時相當沒有效率，一個聰明的解法由J.C. Warnsdorff在1823年提出，簡單的說，先將最難的位置走完，接下來的路就寬廣了，騎士所要走的下一步，「為下一步再選擇時，所能走的步數最少的一步。」，使用這個方法，在不使用遞歸的情況下，可以有較高的機率找出走法（找不到走法的機會也是有的）。
基本介紹
- 中文名：騎士旅遊
- 輝煌時期：十八世紀初
- 類別：西洋棋的走法
- 適用：西洋棋
在一個n m 格子的棋盤上，有一隻西洋棋的騎士在棋盤的左下角，騎士只能根據象棋的規則進行移動，要么橫向跳動一格縱向跳動兩格，要么縱向跳動一格橫向跳動兩格。 例如， n=4，m=3 時，若騎士在格子(2;1) ，則騎士只能移入下面格子：(1;3),(3;3) 或 (4;2)；對於給定正整數n，m，I，j值 (m,n<=50,I<=n,j<=m) ，你要測算出從初始位置(1;1) 到格子(i;j)最少需要多少次移動。如果不可能到達目標位置，則輸出"NEVAR"。
騎士旅遊的偽碼：
FOR(m = 2; m <= 總步數; m++)
[
測試下一步可以走的八個方向，記錄可停留的格數count。
IF(count == 0)
[
遊歷失敗
]
ELSE IF(count == 1)
[
下一步只有一個可能
]
ELSE
[
找出下一步的出路最少的格子
如果出路值相同，則選第一個遇到的出路。
]
走最少出路的格子，記錄騎士的新位置。
]
