Magical Mystery Knight's Tour

This problems asks you to generate a knights tour on a chessboard such that the sum of the move numbers on the squares of each row and column are equal with the constraint that it matches certain "fixed" squares defined in the input.

While it seems that the search space is large, it turns out to be heavily pruned. We know we need to be able to reach any defined squares, so we can create a mask which tells us which squares are 1-move away, 2-moves away, etc. from any given point. Using this, we can limit our moves to only those that can result in our arriving at whatever the next specific square we need to land on.

Aside from that, we know exactly which move numbers are left to be "allocated" to column and row sums. We also know our current row and column sums and the average value required remaining to reach the 260 number. If we run into a situation where the remaining available "move numbers" are greater than the average of any row or column, we can prune the search.

Note that in order to compare the mask of valid moves quickly, we should encode the 64 positions on the chessboard as bits in a 64 bit integer. This allows constant time comparison, which may be necessary.

These three optimizations should allow us to run fast enough.