This is a documentation of the Peaceable Armies of Queens problem, originally written as a Constraint Programming assignment at Charles University Prague (March 2017).

1. Description of the Problem

We consider a chess board with size D and queens from both colors, black and white. We want to place all queens on the given board such that no queen can beat a queen from another color. So we have two armies of queens where no queen can reach a queen from the other team within one round. The queens’ movement follows standard chess rules — they can move any number of steps in the same row, column, or diagonal in each direction. The goal is to maximize the number N of queens (N black queens, N white queens) for a given board size D.

2. Constraint Model

We use a constraint model to calculate the maximum number of possible queens for a given size D. We instantiate D² variables — one for each field on the board — encoded as: -1 (black queen), 1 (white queen), 0 (free field). Each variable is assigned a value from the domain {−1, 0, 1} subject to the following constraints:

• The same number of -1 and 1 values are assigned
• Exactly N variables assigned -1 and N assigned 1
• Each row contains only -1 and 0, or only 1 and 0
• Each column contains only -1 and 0, or only 1 and 0
• Each diagonal contains only -1 and 0, or only 1 and 0

3. Prolog Implementation

The implementation uses SICStus Prolog 4.3.5 with the clpfd and lists libraries.

3.1 Basic Usage

| ?- use_module(library(clpfd)), use_module(library(lists)).
| ?- consult('/PATH/TO/FILE/queensarmies.pl').

% Find max queens for board size 5:
| ?- qa0(S, 5, N).
S = [[0,-1,0,-1,0],[-1,0,0,0,0],[0,0,1,0,1],[-1,0,0,0,0],[0,0,1,0,1]],
N = 4 ? yes

3.2 Constraint Implementation

The cardinality of queens per color is enforced using global_cardinality/2. Row, column, and diagonal consistency is checked via a custom predicate:

global_cardinality(Sol1, [-1-N, 1-N, 0-_]),

check_rows_a([]).
check_rows_a([H | T]) :-
  global_cardinality(H, [1-N1,0-_,-1-N2]), (N1#=0 #\/ N2#=0),
  check_rows_a(T).

3.3 Maximization

The domain of N is bounded by the floor of D²/4. The formula and the corresponding labeling code:

N#> 0, N#< L/4,
labeling([maximize(N), ffc], Sol1).

Using the ffc labeling option (variable with most constraints and smallest domain assigned first) roughly halves the runtime compared to the default leftmost strategy.

3.4 Optimizations

• qa1: First row restricted to -1/0, avoiding symmetric duplicate checks
• qa1_extended: Additionally restricts first column, last row/column, and forces bottom-right field to 1
• qa1_rec: Uses solution for size D−1 as a lower bound for N, recursively narrowing the search

4. Test Results

Tests were run on an Intel Core i5-6200U @ 2.30 GHz on Windows 10. Runtimes in seconds:

Standard labeling (leftmost)

D	N	qa0	qa1	qa1_extended	qa1_rec
4	2	0.015	0.015	0.0	0.015
5	4	0.11	0.078	0.016	0.078
6	5	2.985	1.687	0.156	1.734
7	7	59.5	33.25	2.5	34.375
8	9	1795	990.9	68.812	985.3
9	12	—	—	1387	—

FFC labeling

D	N	qa0	qa1	qa1_extended	qa1_rec
4	2	0.015	0.0	0.0	0.0
5	4	0.078	0.047	0.0	0.062
6	5	1.813	1.109	0.156	1.172
7	7	27.41	16.13	2.359	17.3
8	9	540.4	364.1	60.2	395.1
9	12	—	4599	1160	5023

5. Interpretation

qa1_extended is consistently the fastest procedure. By fixing the first row, first column, and a corner field, it eliminates large portions of the symmetric search space without (in tested cases) losing any optimal solutions — though this cannot be formally proven for larger boards.

The ffc labeling option roughly halves the runtime of all procedures, with the smallest improvement seen in qa1_extended (which already prunes heavily). The recursive approach qa1_rec adds overhead for small boards but may help at larger scales.

Overall, the runtime grows very rapidly with increasing D. For boards beyond 10×10, this pure constraint model becomes computationally infeasible without further structural insight or heuristics.

The code and written results can be found on my github repo: https://github.com/christophsaffer/Peaceable-Queens/