4
$\begingroup$

What are the strategies one can use to keep maximum number of non attacking pieces (all pieces other than pawn) on an $n\times n$ board? It is like an $n$-queen problem but here instead of only queen other pieces also come into picture. Like if I have a knight, queen, king, bishop, knight what are the best strategies to keep them on a $n\times n$ board such that non of the pieces attack each other?

Just to add to it, I will be getting pieces one after another in a random manner, so basically I don't have any control over the sequence and count of pieces that come along. Like 1. Queen 2. Bishop 3. Queen 4. Knight and I have to keep them on an $n\times n$ board such that no pieces attack each other.

$\endgroup$
  • $\begingroup$ Are all the pieces independed, i.e. can any piece attack any other piece or are there black and white pieces? And I am assuming you mean no attacks in a single move? $\endgroup$ – Godric Seer Jun 7 '13 at 15:47
  • $\begingroup$ all the pieces are independent , so no difference in black or white. It is very similar to arranging N queens on an N X N chess board. Just that here instead of queens there are other pieces also ( other than pawn ) $\endgroup$ – user1387 Jun 7 '13 at 15:50
  • $\begingroup$ I rolled back to question text, since the recent edit removed all hints as to what you were asking. $\endgroup$ – Godric Seer Aug 25 '13 at 17:02
1
$\begingroup$

While this isn't a full algorithm, I think I can point you to a goal. Every piece has a specific number of spaces it can move in the greater 15x15 grid with itself at the center. Whenever you place a piece on the board, the spaces that it can move to become "unsafe". Your overall goal is to retain safe spaces for as long as possible so that you can continue to place more pieces.

Since you don't know the order and type of pieces beforehand, all I can suggest is the greedy algorithm. When you get the next piece, cycle through all the "safe" spaces and see if any of them are invalid due to the new piece being able to attack another from that position. Once you have a set of valid "safe" spaces, choose the one that minimizes the number of new "unsafe" spaces. In other words you are trying to put as many of the new piece's moveable spaces either off the edges of the board, or on top of pre-existing "unsafe" spaces.

If you knew beforehand the pieces you would be getting, you could come up with something more sophisticated.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes, it would be fairly trivial to implement, since with at most 64 "safe" spaces and I am guessing a dozen or two pieces, even a quick write up cycling through each space for each piece would run relatively quickly. $\endgroup$ – Godric Seer Jun 7 '13 at 16:31

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