Given a rectangular board of cells with some number of holes in it, determine whether it is possible to complete a "holey knight's tour" (That is, a path that visits every non-hole cell exactly once using only chess knight moves, not returning to the starting cell) that starts on the top-left cell.
For the sake of completeness of the challenge definition, knights move by teleporting directly to a cell that is two cells away along one axis and one cell along the other axis.
Examples
Using .
for open spaces and X
for holes
1
. . .
. X .
. . .
YES
2
. . . X
. X . .
. . X .
X . . .
NO
3
. . . . .
X . . . .
. . X . .
. X . . .
. . . . .
YES
4
. . X . .
X . . . X
. . . . .
. X . . .
X . . X X
YES
5
. . . . . .
. . X . . .
. X . . . .
. . . . . .
. . . . . .
NO
Rules and Assumptions
- You must theoretically be able to support boards up to 1000x1000
- Boards do not necessarily have to be square
- As this problem could potentially have exponential time complexity in the worst case, and in an effort to not make testing solutions take forever, board sizes up to 6x6 must return an answer within one minute on modern hardware.
- A board with a hole in the top-left corner (where the knight starts) is always unsolvable
Shortest code wins