I am motivated by the post, Complexity of n-queens-completion. I am interested in completion problem of non-attacking rooks on a chessboard.
Input: Given a chessboard of size $n*n$ with $n-k$ rooks placed in non-attacking positions, and certain chessboard diagonals represented by multi-set of integers $D=\{j_1, j_2, ..., j_k\}$
Output: Can we place additional $k$ rooks such all $n$ rooks are non-attacking and each new rook is placed on exactly one diagonal in $D$?
Has anyone investigated the complexity of this problem? Is it NP-complete?
