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.

These two optimizations should allow us to run fast enough. [[Category:DFS