You are given an n x n chessboard with k knights (of the same color) on it. Someone has spilled superglue on k of the squares, and if a knight ever finishes his move on one of these glue squares, it becomes stuck forever. Additionally (and this is why we can't have nice things) someone has cut out some of the squares so the chessboard has holes in it. You are given an initial position of the knights. The knights move as they do in regular chess, but unlike regular chess, on each turn all the knights move at once (except of course the stuck ones). At the end of each move, a square cannot be occupied by more than 1 knight. Hole squares can't be occupied by knights either (but they do count as squares that the knight can jump over). Give an 0(t x poly(n))-time algorithm to determine whether you can use < t moves to move all the knights from their initial positions to new positions where they are each stuck at a glue square.
My initial thought is to formulate this problem into a maximum flow problem and use Ford-Fulkerson algorithm to solve it. But I am not sure what my nodes and edges should be. Any idea? Thanks!
The described problem can be modeled as a layered network problem as follows. The node set of the network consists of an artificial starting node s and an artificial terminal node t. The intermediate node set consists of k copies of the n * n chessboard, which means that there are
2 + k * n * n
nodes in total. Imagine s at the top, followed by the k layers of the chessboard copies. The terminal node t would be at the bottom.
Connect s to the initial knight positions in the first chessboard and connect t to all desired terminal positions of the knights in the k-th chessboard.
For every i in {1,...,k-1} connect each square in the i-th chessboard to every square in the i+1the chessboard if and only if it can be reached by a legal knight's move. Finally, delete all edges which leave a superglued square (except if t is its tail) and delete all edges which lead to a hole. Furthermore, every edge is constrained to permit a flow of at least 0 and at most 1. In total, the network has at most
2 * k + k * n * n = k * ( 2 + n * n )
edges. To furthermore take into account that every square is to be occupied by at most one knight, the flow in every intermediate node must also be constrained by 1. This can be done by expanding each intermediate node into two nodes and connecting them by an additional edge in which the flow is constrained by 1, which causes the set of nodes and edges to grow by a factor of at most 2.
The k knights can be moved from their initial positions to their terminal positions if and only if the network admits an s-t-flow of value k, where the sequence of knight's movements and the realizing network flows bijectively correspond.