Constraint Satisfaction in Fair Draws

Randomised restart, and why it works here

Randomised restart is exactly what it sounds like: generate a candidate uniformly at random, test it against every constraint, and if it fails, generate another. Repeat until something passes or you give up.

Its efficiency depends entirely on what fraction of candidates are valid. If half of all arrangements satisfy the rules, you expect to find one in two attempts. If one in a thousand does, you expect a thousand attempts — still fast for a computer, but a signal that the constraints are nearly saturating.

For the problems on this site the valid fraction is usually high. A derangement — no element in its original position — is satisfied by about 37% of all permutations, so a valid one turns up in about three attempts. A gift exchange with two excluded pairs among six people is satisfied by a large fraction of derangements. A seating plan with three keep-apart rules in a twenty-seat room is satisfied by most layouts.

Why not use a proper solver

A constraint solver would find a valid arrangement in cases where randomised restart gives up, and would do it faster on tightly constrained problems. It has one property that disqualifies it for most of these tools: it is deterministic.

A solver run twice on the same input produces the same answer twice. For a seating plan that is a serious failure — the whole point is that the arrangement is not predictable, and a plan that is identical every time is a fixed plan with extra steps. The same objection applies to a gift exchange, a rota and a bracket draw.

Solvers can be randomised, by shuffling the variable order or the value order before searching. At that point you have a randomised solver, which is the right tool for genuinely hard constraint problems and considerably more machinery than a fair gift exchange needs.

• Randomised restart: simple, genuinely random when it succeeds, gives up honestly when it fails.
• Deterministic solver: complete and fast, produces the same answer every run.
• Randomised solver: complete, fast and random — and much more code.

When there is no answer at all

The most important behaviour of a constrained draw is what it does when the constraints cannot be satisfied. This is not an edge case: seating plans with several keep-apart rules in a full room hit it constantly, and any accumulating exclusion list eventually reaches it.

The condition that decides it is Hall's, and it is worth knowing because it is checkable by hand. An assignment exists if and only if every group of k givers has at least k permissible recipients between them. The smallest natural failure needs only four people and three exclusion rules: bar Ana from Ben, Ben from Cleo and Cleo from Ana in a group with Dev, and all three are funnelled onto Dev alone. Three givers, one available recipient, condition violated.

It is worth flagging the case people expect and which does not fail. Couple exclusions alone almost never make a gift exchange impossible — six people in three couples can be assigned as two three-cycles, and every partner is skipped. Only a single couple on their own is stuck, because each person's one possible recipient is the other.

The right response is to say so. A tool that quietly dropped a constraint to produce a result would return something that looks perfectly valid and violates a rule the user set, and the user would find out at the worst possible moment. The refusal has to be explicit and it has to say which direction to relax.

Distinguishing 'no answer' from 'gave up'

There is an honest ambiguity in randomised restart that a solver does not have: after five thousand failed attempts, you do not know whether there is no solution or whether you were unlucky. Both look identical from inside the loop.

In practice the distinction rarely matters, because the attempt budget is set far above the point where a genuinely solvable problem would have succeeded. If one in five thousand arrangements is valid, five thousand attempts finds one about 63% of the time — so a failure at that budget means the valid fraction is well below that, which is functionally unsolvable for a tool that has to respond immediately.

What matters is that the message is honest about which claim it is making. Saying "no valid answer exists" when you mean "I did not find one" is a small lie that costs credibility the first time somebody constructs a counterexample.

Fairness under constraints

One consequence of randomised restart is worth stating plainly: the result is not perfectly uniform across valid arrangements. Arrangements that are easier to reach from a random shuffle come up slightly more often than those that are not.

The effect is small for the constraint types on this site, and the alternative — enumerating all valid arrangements and picking uniformly — is computationally infeasible for anything beyond about ten items. Twelve people have 479 million permutations, and enumerating the valid ones is not something a browser should attempt.

So the honest claim for a constrained draw is: every valid arrangement is reachable and no invalid arrangement is possible, with a slight and unmeasured preference among the valid ones. That is weaker than the uniformity claim an unconstrained shuffle can make, and it is the accurate one.

Frequently asked questions

Tools that use this

Related guides