Generating All Valid KRK Chess Positions with Constraint Programming

I wanted a reliable way to generate all legal K+R vs K chess positions with White to move for AI training data.
After exploring several constraint programming tools (MiniZinc, OR-Tools, and Prolog variants), I ended up using Scryer Prolog, embedded directly from Rust.

In the end, I realized that I didn’t even need constraint programming (CLP) at all — plain Prolog was enough.
The constraints were simple, the domain small, and performance was already instant.

This setup gives me a clean separation:

• Prolog file → defines the logical rules.
• Rust code → calls Scryer, collects the results, and filters them further if needed.

Goal & Scope

• Goal: Generate all valid KRK (White King, White Rook, Black King) positions with White to move.
• Use case: Dataset creation for future AI training (e.g., “mate in n” labels).
• Constraints: Limited time (personal project) and a machine running Ubuntu.

We only care about generating valid positions, meaning:

1. All three pieces are on distinct squares.
2. Kings are not adjacent (Chebyshev distance ≠ 1).
3. (Optionally) The black king is not already in check by the rook.

Why Prolog (and Not Full Constraint Programming)

At first, I considered going with a full constraint programming approach.
Tools like MiniZinc, OR-Tools, or ECLiPSe are designed to solve constraint satisfaction problems declaratively.
However, for a small and discrete system like KRK, these tools quickly became overkill.

What I Needed

• Enumerate all possible placements on an 8×8 board.
• Apply a few logical constraints.
• Avoid duplicates or illegal configurations.

That’s something Prolog can already do naturally, thanks to backtracking and unification.
So, instead of building a solver, I simply described the rules of valid KRK positions.

Tooling Decisions

Considered

• MiniZinc + OR-Tools: Very powerful, supports non-linear constraints, but far too heavy for a simple enumeration.
• SWI-Prolog / ECLiPSe: Excellent for CLP(FD), but installing and learning them takes more time than the task itself.
• Scryer Prolog (Rust): Lightweight, easy to embed, perfect fit for my Rust-based chess project.

Chosen

Scryer Prolog, used in plain Prolog mode (not CLP(Z)).

At first, I thought I would benefit from CLP(Z) — Scryer’s constraint logic programming library for integers.
But once the generator worked, I realized that it didn’t bring any practical advantage for this problem.

Why CLP(Z) Was Unnecessary

CLP(Z) is designed for symbolic reasoning and constraint propagation.
It allows you to define arithmetic relations without immediately evaluating them, such as:

X #> 0, Y #= X + 3. 

These constraints are stored until a labeling phase (label/1) assigns concrete values.
This is powerful when solving problems with large search spaces or complex interdependencies.

However, in my case:

• The domain is small: 64 squares, 3 unique pieces → about 250k combinations.
• The constraints are purely filtering (distinctness, non-adjacency).
• There’s no dependency or propagation between variables.
• Everything can be resolved directly with recursion and is/2.

So CLP(Z) didn’t improve performance — it simply added abstraction without any real gain.
The enumeration in plain Prolog is already instant and perfectly readable.

The Prolog Program

Here’s the final generator, written in pure Prolog:

% generator 0..63 without library(between)
num(A, B, A) :- A =< B.
num(A, B, X) :- A < B, A1 is A + 1, num(A1, B, X). square(S) :- num(0, 63, S)

sq_file(S, F) :- F is S mod 8.
sq_rank(S, R) :- R is S // 8.

% kings are adjacent if Chebyshev distance is 1
kings_adjacent(S1, S2) :-
   sq_file(S1, F1), sq_rank(S1, R1),
   sq_file(S2, F2), sq_rank(S2, R2),
   DF is abs(F1 - F2),
   DR is abs(R1 - R2),
   max3(DF, DR, M),
   M =:= 1.

% simple max/3
max3(A,B,M) :- A >= B, M is A.
max3(A,B,M) :- A <  B, M is B.

% KRK positions: distinct squares, non-adjacent kings
krk(WK, WR, BK) :-
   square(WK),
   square(WR), WR =\= WK,
   square(BK), BK =\= WK, BK =\= WR,
   \+ kings_adjacent(WK, BK). 

How it works

• num/3 recursively enumerates integers.
• sq_file/2 and sq_rank/2 extract coordinates from 0–63 indices.
• kings_adjacent/2 ensures the kings don’t touch.
• krk/3 enforces distinct squares and non-adjacent kings.

That’s all. No need for CLP, no solver setup, no domain declarations.

Integration with Rust

The Rust side simply calls Scryer Prolog to run the krk/3 generator and collects the resulting triples (WK, WR, BK).
Because the generation happens once (batch mode), performance isn’t a concern.

This architecture keeps the rules declarative and data handling procedural, making it both simple and elegant:

• Modify the Prolog file to add or adjust constraints.
• Keep Rust focused on iteration, filtering, and integration with downstream AI code.

Lessons Learned

• The hardest part was choosing the right tool, not writing the code.
• MiniZinc and OR-Tools were overkill for such a small combinatorial problem.
• Prolog alone was expressive enough to describe the relationships and generate valid states.
• I learned that CLP(Z), although elegant, provides no benefit in a purely filtering, small-domain enumeration context.

Once the positions are generated, I can move on to labeling (“mate in n”) and AI training (NNUE, PyTorch, or hybrid architectures).

Closing Thoughts

What I appreciated most in this small project was rediscovering the simplicity of Prolog:
pure logic, no boilerplate, and perfect for tasks where rules can be expressed as relations.

The final solution is minimalistic yet extensible — and that’s exactly what I wanted for this first data-generation stage.