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?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.