I'm trying to to create an algorithm (working in polynomial time) to solve the following problem:
What maximum number of knights that any two of them don't attack each other can be placed on a 3✕n chessboard with holes (knight can't be placed on a hole). Width of the chessboard (n) and positions of holes are given. Besides the maximum number of knights that can be placed, the algorithm should return their positions.
I think some dynamic programming techniques can be used here but I have no idea how to get a solution for bigger chessboard having a solution for a smaller one. What I make out about the problem so far is:
- the chessboard is a bipartite graph, where nodes are the normal (not holes) fields and edges are legal knight moves (white fields in the "left" set and the black ones in the "right" set)
- the maximum degree of a node is 4 (knight can move to maximum 4 fields because the width of chessboard equals 3).