3
$\begingroup$

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).
$\endgroup$
  • 1
    $\begingroup$ Welcome to CS.SE! We get asked about how to apply dynamic programming a lot, so we've prepared some general tips for you: cs.stackexchange.com/tags/dynamic-programming/info. I suggest you study that material, try to apply it to this problem, and if you're still stuck, edit the question to show what steps you've taken so far, what progress you've made, and where specifically you got stuck. $\endgroup$ – D.W. Mar 22 '17 at 21:19
2
$\begingroup$

Use dynamic programming to calculate the maximum number of non-attacking knights on the left $3\times m$ part of your board with holes, given the placement of knights in the last two columns of this part of the board.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.