The Field That Schedules Your World

Nurse rostering, crew assignment, delivery planning and exam timetabling all contain constrained decision problems. Constraint programming is one useful way to model them: express the permitted assignments and let a solver search for a feasible or optimal result.

The following project uses scheduling to explore those ideas in Python and Kotlin.

ELI5: the Sudoku shape of the world

You know Sudoku. Nine rows, nine columns, nine 3x3 boxes, each digit 1-9 appearing exactly once in each. Give someone a half-filled grid and they don't try every possible arrangement — 9⁸¹ is a universe's worth of possibilities. They look at one empty cell, see which digits can still legally go there given its row, column, and box, and start narrowing things down. When they fill one cell, it propagates: other cells now have fewer legal options too. They keep narrowing until the grid is solved or they hit a wall and have to guess.

That is constraint programming in a sentence. You describe what must be true (each row contains 1-9, each column contains 1-9, each box contains 1-9). A solver figures out what arrangement satisfies the rules. You don't write the search algorithm. You don't write a for-loop. You describe the universe of the problem and let the solver inhabit it.

Now scale up. The problem isn't Sudoku but scheduling 200 nurses across 28 days and 4 shifts, with labor laws about rest periods, required skill coverage per shift, vacation requests, contract hours, and fairness constraints. And just to make it interesting, you want the best legal schedule, not just any legal one.

A nurse-scheduling formulation can have a very large combinatorial search space. That raw count does not determine runtime: constraints, symmetry, objective structure, solver settings and instance difficulty all matter. Some instances solve quickly; others remain difficult.

The stumbling

Neural models are one part of AI. Constraint programming offers a complementary approach for problems where variables, domains and admissible assignments can be stated explicitly.

It also overlaps with operations research and mathematical optimization. Practical systems may combine constraint solvers, mixed-integer programming, local search, heuristics and learned components.

The useful distinction is the problem representation and the guarantees a particular method can establish.

The vocabulary you need, in three words

• Variables. Symbols that take values from a set. x ∈ {1..9}. start_time ∈ {0..1440 minutes}. is_nurse_alice_working_monday_night ∈ {0, 1}.
• Domains. The set of allowed values for each variable. Starts large, shrinks as the solver infers facts.
• Constraints. Relations that must hold. x ≠ y. sum(nurses_working_monday_night) ≥ 3. end_of_shift_A + 11h ≤ start_of_shift_B.

A constraint model names variables and relations. The solver handles search, while the application may still use loops to construct the model, preprocess input and interpret results.

Google’s OR-Tools is an operations-research toolkit. Its CP-SAT solver combines constraint-programming and satisfiability techniques with other optimization machinery. It can return a feasible solution, prove optimality or infeasibility, or stop without resolving the problem under the configured limits. There is no universal 0.2-second guarantee for scheduling.

The interesting work is learning how a formulation affects both the result and the search required to obtain it.

So I built a repo

The public cp-deep-dive repository explores these ideas through Python and Kotlin examples, a Kotlin DSL and a nurse-scheduling application scaffold. Treat the project as an educational implementation under development, not as evidence that a production deployment has been validated.

Implementing the same formulation in more than one language can help separate the mathematical model from host-language conventions. It complements reading and theory rather than replacing them.

Let me give you the tour.

The dual-language rationale

Everything lives in both Python and Kotlin. Most "learn X" repos pick one language. I picked two for a specific reason: the cleanest way to understand a solver's conceptual model is to see it expressed in two very different host languages and notice what is essential versus what is just ceremony.

OR-Tools provides Python bindings among its supported language interfaces. Python is convenient for prototyping and exploring a model interactively.

Kotlin can call the Java API. The project’s cpsat-kt layer explores a more idiomatic internal DSL; this example illustrates its intended modeling interface.

val model = cpModel {
    val x = intVar("x", 0..10)
    val y = intVar("y", 0..10)

    constraint {
        +(3 * x + 2 * y eq 12)
        +(x + y le 5)
    }

    minimize { x + y }
}

val result = model.solveBlocking { randomSeed = 42 }
// result is SolveResult.Optimal(objective = 4L, values = {x=4, y=0})

That reads like math. Operator overloading for +, *, eq, le. A DSL block for constraint posting. A typed result ADT (Optimal | Feasible | Infeasible | ModelInvalid). Under the hood it is doing all the model.addLinearExpressionInDomain(...) gymnastics the raw Java API demands.

An internal Kotlin DSL still uses the Kotlin compiler and runtime. Its benefit is a domain-oriented vocabulary over the underlying API, not the absence of compilation. Validate the wrapper’s semantics and compatibility before depending on it in production.

MiniZinc as Rosetta Stone

Halfway through, the repo takes a detour into MiniZinc — a solver-agnostic declarative modelling language. Why? Because MiniZinc forces you to write the model in pure mathematical form, with no reference to any particular solver. You describe the problem. MiniZinc compiles it down to FlatZinc and hands it to whichever backend you want: CP-SAT, Gecode, Chuffed, or even an MILP solver.

This is the Rosetta Stone moment. Once you have written a model in CP-SAT Python, then again in cpsat-kt Kotlin, then again in MiniZinc, you start to see which parts are the problem and which parts are just the language. The repo uses MiniZinc as a prototyping tool — write it declaratively first, debug at the math level, then port to CP-SAT in production.

The Nurse Scheduling Problem as canonical teacher

Five of the eighteen chapters are the NSP. Not because I have any nursing background — I don't. I chose it because it is the canonical real-world CP scheduling problem: well-studied since the 1970s, has standard benchmark datasets (NSPLib, INRC-I, INRC-II), and maps cleanly onto CP-SAT's Boolean and interval machinery.

The core decision variable is disarmingly simple:

# x[(nurse_id, day, shift_id)] = 1 iff the nurse works that shift on that day
for n in nurses:
    for d in days:
        for s in shift_ids:
            if _cell_allowed(instance, n.id, d, s):
                x[(n.id, d, s)] = model.new_bool_var(f"x_{n.id}_d{d}_{s}")

One Boolean per (nurse, day, shift) triple. For 50 nurses x 28 days x 4 shifts, that is 5,600 Booleans. The constraints then layer on top:

• HC-1 coverage — for each shift on each day, between min and max nurses must be assigned.
• HC-2 one shift per day — sum(x[(n, d, s)] for s in shifts) ≤ 1 for each nurse/day.
• HC-3 forbidden transitions — can't work night-then-morning, enforced pairwise.
• HC-4 max consecutive working days and HC-5 max consecutive nights — rolling window over any k-day slab.
• HC-6 minimum rest hours — derived from shift end times, folded into forbidden transitions.
• HC-7 skill coverage — at least one nurse with skill X per shift requiring X.
• HC-8 contract hours — rolling 7-day window of shift durations, bounded by contract ± tolerance.

Hard constraints define admissible schedules. Soft constraints encode preferences or penalties in an objective. More complex scheduling domains may require additional rules, multiple objectives or a different formulation; one nurse-roster example is not a universal model.

Make solver comparisons comparable

The initial ports do not yet establish a controlled performance comparison. A feasibility-only model and an optimization model have different goals, and scores from differently weighted objectives cannot be ranked against one another.

Until those conditions hold, report implementation status rather than declaring a fastest or best solver. For optimization, also record the objective direction, incumbent value, bound or gap, termination status and resource limit. A feasible value cannot contradict a proven optimum for the same minimization model; such a mismatch calls for investigation.

The spec-first discipline

Before any backend code existed in the apps/ directory, I wrote and locked ten specification documents under specs/nsp-app/:

00-overview.md
01-vision-and-goals.md
02-domain-model-and-glossary.md
03-functional-requirements.md
04-non-functional-requirements.md
05-architecture.md
06-api-contract.md           <- references apps/shared/openapi.yaml
07-data-contracts.md
08-ui-flows.md
09-acceptance-criteria.md

The spec was frozen at v1.0. Then the code was written to conform to it. The OpenAPI contract under apps/shared/openapi.yaml was the authority: both the Python FastAPI backend and the Kotlin Ktor backend had to match it, endpoint for endpoint, shape for shape, enum value for enum value.

A specification provides shared acceptance criteria. It is most useful when paired with executable contract checks and review of ambiguous requirements. A frozen document alone cannot prevent drift or prove that an implementation matches the intended problem.

Twin backends, one contract

Identical OpenAPI contract. Two implementations.

• apps/py-api/ — FastAPI + SQLModel + sse-starlette + Pydantic v2. Thirteen endpoints. Thirty unit tests.
• apps/kt-api/ — Ktor 3.x + Exposed + kotlinx.coroutines. Thirteen endpoints. Seventeen unit tests.

Two backends can help expose differences, but they are not a debugging oracle. A shared failure may come from the model, a copied implementation error, shared test data or a wrong expectation. A difference between backends is a lead to investigate, not a diagnosis by itself.

The frontend — apps/web/, built on Vite + React 19 + React Router v7 (framework mode) + Tailwind 4 + shadcn/ui + TanStack Query 5 — doesn't know which backend it's talking to. It just speaks OpenAPI. Server-Sent Events stream solve progress to the UI live. Watch the solver chew through branches in real time. It is hypnotic.

The eighteen chapters

The path from "what is a constraint" to "benchmark a production solver against three engines" is eight phases:

Phase 1   Intuition + vocabulary           ch. 1-3
Phase 2   Core modelling                   ch. 4-6
Phase 3   Bridges (MiniZinc to CP-SAT)     ch. 7-8
Phase 4   Scheduling primitives            ch. 9-10
Phase 5   Nurse Scheduling I / II / III    ch. 11-13
Phase 6   Your own DSL library             ch. 14
Phase 7   End-to-end NSP application       ch. 15-17
Phase 8   Ecosystem port                   ch. 18

Every chapter has the same shape: intuition, then formal math, then Python implementation, then Kotlin implementation, then MiniZinc variant (where it adds clarity), then exercises. You read it, you run it, you break it, you fix it, you move on.

The agentic knowledge base

The project describes Markdown overview files and local workflow instructions alongside a searchable QMD index. Indexing is a separate process that can fail or lag behind a commit. Observe update status and retain failed maintenance work rather than assuming a hook guarantees freshness.

Search can retrieve relevant chapters, specifications and decision records with citations. The answer still needs to be checked against the source. Instruction files guide an agent; permissions, review and automated checks enforce specific boundaries.

This structure can make AI-assisted implementation easier to inspect: requirements, changes and validation results have named locations. It does not make an agent’s output ground truth or establish production readiness without further evidence.

PhD corner: the machinery under the hood

If you want to descend past the API surface, here is what is actually happening inside CP-SAT.

Propagation narrows domains using consequences of the constraints. For example, assigning a value in an AllDifferent group can remove it from other variables. The amount of work avoided depends on the model and instance; there is no general 99% share attributable to propagation.

Clause learning records explanations for conflicts so that search can avoid repeating related failures. It is an important technique, but comparative solver performance still depends on the formulation, implementation and workload.

Lazy clause generation (LCG). The deepest trick. Instead of picking one representation (SAT clauses or CP domains), the solver maintains both simultaneously and translates between them on demand. When propagation infers a fact in CP-land, it lazily generates the SAT clauses that explain the fact — which then feed the clause learner. This is why CP-SAT is called a hybrid solver: it is literally a CP engine and a SAT solver sharing a belief state.

Symmetry breaking. Scheduling problems are riddled with symmetries — swap any two identical nurses and you get an equivalent solution, and a naive solver would waste time exploring both. You add symmetry-breaking constraints that force a canonical ordering, pruning the duplicates before search begins.

Global constraints such as AllDifferent, Cumulative and NoOverlap expose structure that specialized algorithms may exploit. Their consistency strength and computational cost vary by constraint and implementation. They are modeling tools, not a universal polynomial-time solution to hard problems.

Sixty years of algorithmic cleverness compounded into a single hybrid engine. The repo covers these mechanisms over chapters 4-10 with working examples of each.

Why this matters

Discrete planning and scheduling can benefit from explicit constraints and optimization. Gradient-based methods can contribute through relaxations, learned heuristics and hybrid systems; the challenge is preserving or checking the required discrete feasibility and optimality properties.

Constraint programming offers a precise way to express those requirements and examine what a solver has established.

It is a useful part of an engineer’s toolkit alongside other AI and optimization methods.

Go dig

The public repository is an educational project in development. Check the current implementation and documentation for the exercise you want to run. A scaffold, a passing test suite and a production-ready scheduling service are distinct stages.

Start with the overview and introductory constraint-programming chapter. Run the examples, alter a constraint and inspect the result status. Before using any component operationally, validate the domain rules, failure behavior, performance and integration requirements.

The durable skill is learning to state a problem precisely and interpret the solver’s answer within the limits of that model.

Primary references: OR-Tools CP-SAT guide and result statuses; cp-deep-dive source repository.