The Knight’s tour is a classic chess problem which was studied (and probably solved) over 1000 years ago. The problem is, from an arbitrary starting position, move a Knight chess piece around a chessboard visiting all other squares on the board exactly once. A related problem is to find all starting positions that get us to a
solution. For instance, in the chessboard above you can get a solution starting at the position numbered with 1 as well as 26, 54 and 7 (due to symmetry). This problem is more interesting if the board is not necessarily a square. Given a grid of n rows and m columns representing a board, 6 ≤ n, m ≤ 10000, find the minimum number of starting positions you must examine, such that we can find all the solutions for the Knight’s tour.

For example, in the grid on the right, the cells with the same color represent one cell and its symmetric ones; so we can examine only one cell of each color.

騎士巡邏問題是一個經典的西洋棋問題，早在1000多年前就已經被研究（甚至可能已經被解出）。該問題的目標是：從棋盤上任意一個起始位置開始，讓西洋棋的騎士（Knight）依規則移動，恰好拜訪棋盤上的每一格一次且僅一次。 現在我們試著找出所有可以產生完整解的起始位置。 舉例來說，在上圖中的棋盤，從編號為 1、26、54 和 7 的格子開始，都可以得到一個有效解，因為它們互為對稱。而這個問題在棋盤不一定是正方形的情況下更有趣。