The Night Watch Knight

A museum's rectangular storage yard is marked out as a grid of n rows and m columns. The night guard is a chess enthusiast and patrols it like a knight: every step is two squares in one direction and one square in a perpendicular direction. Starting on the square start = [r, c], the guard wants to stand on every square of the yard exactly once. The patrol does not have to end next to the start.

Write knight_patrol(n, m, start) that returns such a patrol as a list of n*m squares [row, col] (0-based) beginning with start, or None if no patrol from that start exists. Any valid patrol is accepted.

Examples

Input:  n = 5, m = 5, start = [2, 2]
Output: [[2, 2], [3, 4], [4, 2], [3, 0], [1, 1], ...]   (25 squares, one of many valid answers)

Input:  n = 4, m = 4, start = [0, 0]
Output: None
Explanation: no knight's path covers a 4 x 4 yard, from any start.

Input:  n = 1, m = 1, start = [0, 0]
Output: [[0, 0]]

Constraints

• 1 <= n, m <= 30, and start is a square of the yard
• in the tests, every yard with more than 20 squares has a patrol from the given start
• each test must finish in well under a second, so a search that tries moves in a fixed order and backs up blindly is far too slow on big yards

Goals

• Order the choices of a backtracking search with a look-ahead rule so it rarely backs up
• Validate a long path square by square