Chapter XVII 3-Dimensional Matching

Backtracking in Swift

Swift's value types and pattern matching keep the search tight; Sets give O(1) membership.

01

Define the triple as a value-typed struct. Hashable lets us put it in a Set; Equatable falls out for free with the synthesized conformance.
```
struct Triple: Hashable {
    let x: Int; let y: Int; let z: Int
}
```

Recursive search: try every still-feasible triple at this depth, mark its three elements used, recurse. On failure, unmark and try the next triple.

func match(triples: [Triple],
           usedX: Set<Int>, usedY: Set<Int>, usedZ: Set<Int>,
           picked: [Triple], target: Int) -> [Triple]? {
    if picked.count == target { return picked }
    for t in triples {
        guard !usedX.contains(t.x),
              !usedY.contains(t.y),
              !usedZ.contains(t.z) else { continue }
        if let sol = match(
            triples: triples,
            usedX: usedX.union([t.x]),
            usedY: usedY.union([t.y]),
            usedZ: usedZ.union([t.z]),
            picked: picked + [t],
            target: target
        ) {
            return sol
        }
    }
    return nil
}

Wrap with a friendlier signature. The whole search is one recursive function, plus an entrypoint — Swift's expressive type system pulls its weight here.

func threeDM(_ ts: [Triple], target: Int) -> [Triple]? {
    return match(triples: ts,
                 usedX: [], usedY: [], usedZ: [],
                 picked: [], target: target)
}

Try it on a small instance. For n ≤ 20, simple backtracking is fast enough. For larger, you'd LP-relax to bipartite-matching subproblems and round — that is what commercial assignment solvers do.

let ts: [Triple] = [
    .init(x:0,y:0,z:0), .init(x:1,y:1,z:1),
    .init(x:2,y:2,z:2), .init(x:0,y:1,z:2)
]
print(threeDM(ts, target: 3) as Any)
// Optional([Triple(x:0,y:0,z:0), Triple(x:1,y:1,z:1), Triple(x:2,y:2,z:2)])

Grammar — Swift

Swift's value types and protocol-oriented design make small immutable shapes — like a Triple — fast and ergonomic. Optionals force you to handle absence at the type level: a function returning T? cannot pretend nothing went wrong.

struct T: Hashable { ... }: a value type. The `: Hashable` declares conformance — Swift synthesizes `==` and `hash(into:)` automatically.
let x = ...: immutable binding. Use `var` for mutable.
func name(_ x: T) -> R?: function declaration. Underscore makes the argument unlabeled at call sites; the trailing ? makes the return optional.
[T]: array of T. Set<T> is the hash-based set.
T?: optional — short for Optional<T>. Either `.some(value)` or `.none` (also written `nil`).
guard cond else { ... }: early-exit check. If cond fails, run the else (which must exit). Otherwise continue with bindings still in scope.
if let x = opt { ... }: optional unwrap — run the body only if opt is non-nil, with x bound to the unwrapped value.
0..<n: half-open range — 0, 1, ..., n−1. Use `0...n` for the closed range.
for x in xs: iterate. Pair with where clauses: `for x in xs where x.isEven`.

A triple is a struct of three integers, automatically Hashable so it slots into Sets and Dictionaries with no boilerplate. Compare to other languages where this would need a class with manual hashCode/equals.

struct Triple: Hashable {
    let x: Int; let y: Int; let z: Int
}

let candidates: [Triple] = [
    Triple(x: 0, y: 0, z: 0),
    Triple(x: 1, y: 1, z: 1)
]
var seen = Set<Triple>()
seen.insert(candidates[0])  // works — Hashable is automatic

Swift Fiddle — try Swift in your browser →