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
Chess Stack Exchange is a question and answer site for serious players and enthusiasts of chess. It only takes a minute to sign up.
Sign up to join this communityWhat 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
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!
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.
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:
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.
The two main points are:
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: