Tuesday, September 29, 2026

[kxdvujsv] N queens of two colors (peaceable queens)

Q/2 white queens, Q/2 black.  how many can fit on a chessboard (i.e., maximize Q) with no queen attacking one of the opposite color?  queens of the same color may attack (actually defend) each other (but don't have to).

I'm sure this problem has been proposed before because it makes sense for regular chess. but it is hard to search for it, dominated by results of the traditional N queens problem all of the same color, (or, to be consistent with actual chess, all of different colors, because queens of the same color defending each other is not something to avoid in chess).

update: OEIS A250000, found by luck from Pictures from the OEIS, calls the problem Peaceable Queens.  the problem seems young, much younger than the chess queen itself, with the oldest reference 1977, and the OEIS sequence itself created in 2014.  (Sloane himself arranged for it to get a nice OEIS A-number because he likes the problem, with lower bounds findable by simulated annealing and upper bounds findable by integer programming.)  but certainly chess players had considered the problem earlier?

the maximum for the 8x8 board is 9 queens of each color, which coincidentally corresponds to the original queens plus all pawns promoted to queens.  how many maximal solutions are there for the 8x8 board?

for NxN board sizes larger than N=8, the known solutions are larger than N+1 of each color, lower bound O(N^2), i.e., a constant fraction of the board.  how many solutions are there for an NxN board?  (note well: N denotes the board size, not the number of queens.  in the traditional N queens problem, N could denote both, but in Peaceable Queens the numbers usually different.)

(for chess variants on larger boards, consider letting the sequence minus the number of initial queens define the initial number of pawns.)

the 8x8 solution of 9 queens each, diagrammed on A250000, can easily be changed to 8 queens and 1 king of each color, neither king in check.  but more elegant is to designate one of the 9 queens as royal: capture ends the game.  designate it with the queen piece; the other queens with pawns.  then play real chess starting from this "peaceable" start position.  bloody war likely breaks out very quickly.

while the sequence gives the number A = A250000(N) such that A white queens and A black queens fit on an NxN board, sometimes we can a fit a few more of one color, say, A+d white queens and A black queens.  one commenter on OEIS A250000 calls the situation "aggressors" and mentions that N = 15, A = 32, d = 2 is possible (without actually showing it).  we need another OEIS sequence giving the sequence of maximum d relative to A250000.

No comments :