Uncrossed Knight's Tour

The classical puzzle is to make a knight “tour” all squares of a chessboard of size 8 \times 8. A knight is a piece that moves by jumping one square in one direction and two squares in the perpendicular direction. The task is to visit every square of the board exactly once and then return to the starting square. There are many ways to do this, and the board is small enough that a human can solve the puzzle with some effort.

However, you have a computer and programming skills! Therefore, we offer you a more challenging version of the problem on a rectangular board of size m \times n with an additional restriction: the knight must never cross its own path. If we represent the route as straight-line segments connecting the centers of the squares between which the knight moves, then these segments must form a simple polygon. In other words, no two segments may intersect or touch, except for consecutive segments that share a common endpoint.

Because of this restriction, it may be impossible to visit all squares of the board. Therefore, your task is to maximize the number of squares the knight can visit. The requirement that the tour must end at the starting square remains. The figure shows an optimal solution for the first example — a 6 \times 6 board.