What are the techniques one can use to for chess board?

Question

What are the techniques one can use to keep all pieces on a board ? It is like an n-queen problem

Is it a combination of n-queen

Answer 1

To address the edit to the question If you're receiving the pieces in a random order and you don't have any information about future pieces, the way to arrange the pieces would be to give pieces the least amount of scope. For example, if I were to receive a queen on the first turn, I would place it in one of the four corners. Some more rules would be to keep knights close to each other and pawns stacked one on top of the other. All of these strategies are a bit obvious, but it's difficult to have a consistent strategy to use as there are so many potential combinations of pieces.

---

This seems to me as more of a programming question than a chess one, but it's interesting nontheless! After thinking for a bit, I would hypthesize that the best way to approach this problem would be to use the knights as a baseline. It's well known that the maximum number of knights one can fit on a board is 32 (simply placing them on all squares of the same color), therefore having this as your starting position is logical as this is the maximum occupancy you can have with an individual piece. This strategy extends itself to an N x N board.

Afterwards, I would use pawns as their attacking prowess is limited to forward diagonals of one square in scope. They can occupy every other column (not rows as this would be limited to 2, 4, and 6 if following conventional rules), and this will add N/4 more occupied squares for an NxN board. This generalizes to a total number of occupied squares to N/2 + N/4, or simply 3N/4 total occupied squares.

This is the result of around 5 minutes of consideration, so my algorithm may be flawed. I hope this helps answer your question!

Answer 2

I would think that with a random selection of pieces the basic strategy would be to place them on the board to that they attacked as few squares a possible and didn't obstruct any rank or file that was not already obstructed whenever possible. ie knights in the corners, short distance moving pieces like the king and knight on the same rank or file, and bishops on the same rank or file as other pieces. In general when choosing a square for the new piece it would be similar to a king hunt. When trying to pin down the king you want to reduce the number of squares that he can safely occupy by as much as possible (without reducing it one). Here you want each piece placed to reduce the numbers of squares still not attacked by any piece by as little as possible.

Answer 3

Since the problem definition was updated recently, I'm assuming that you're starting with an empty NxN board, and are given a random piece and asked to place it. When done, you are given another random piece until no more can be placed.

For a human strategy, I guess a good rule of thumb would be to pick a (valid) position which minimises the number of still open squares denied by the new piece. There are two main components to this, on a high level:

• Placing some types of pieces near the edge of the board may be beneficial (I say some, because when placing a rook, you will deny 2N-1 squares regardless of where you place it, but the logic holds nicely for knights).
• Each square being double (or triple, etc) attacked represents a potential free square somewhere else on the board. Keep this in mind to maximise truly open squares.

For a programming strategy, we have to look at the problem again. The way it is stated above it is not really a programming problem, since our success depends on finding the best possible strategy (which clearly we haven't done). Traditional programming will not really help in this sense, because the rules of the problem deny the computer perfect knowledge of what pieces are coming. This makes the traditional approaches of brute-forcing or backtracking (typically used to solve 8 / N-Queens problem(s)) impossible to employ.

One could, however, employed various AI techniques in search of an optimal strategy. Essentially, this would boil down to finding a way to represent a strategy in some kind of data structure. This is actually the difficult part, and could get extremely tricky. You'd probably have to create some kind of domain-specific language which would allow for rules like "pick the rightmost column which doesn't yet have a knight in it", or whatever. Then you'd essentially pick some kind of optimisation algorithm (random search, genetic algorithms, particle swarms, etc) to find a particularly good set of rules, which seems to beat out all the rest you've found so far. There's a good chance that it would be so horribly convoluted that we could never understand how and why it works so well, but it may well beat the ones we've come up with by hand.

Answer 4

The two main points are:

1. Have the less amount of attacked squares at all times, which can be reworded to "always try to attack the same squares several times", the logic behind is that, if you manage to stack the attacks, it will inevitably reduce the total number of attacked squares (which is what we want), making more room for other pieces to be placed.
2. Move groups of pieces near the corners and edges of the board, this will again, reduce the number of attacked squares. We will sometimes need to flip and mirror certain groups of pieces to know what corner will save us the maximum amount of squares (image example below).

As for an example, I will post a quick study I did on knights, it is a bit silly since we already know we can place 32 knights in a 8x8 board just by putting them all on the same color, but I still did it to see how few knights should be arranged:

(notice how point #2 determines which arrangement is better when we have a tie)

Also, two useful links I found are:

• http://en.wikipedia.org/wiki/Eight_queens#Related_problems
• http://archive.vector.org.uk/art10003900

Answer 5

Keep the pieces out of the center, on the sides.