FAILURE MAP
← Case archive

FA-86626 / Procedural level generation constraints / Open access

Perfect maze validator: Reversed duplicate passages are missed · case 01

A passage listed both ways is reported as a loop.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The duplicate key keeps orientation.

THE FAILURE

The duplicate key keeps orientation.

Unsuccessful approach: Sorting flattened coordinates makes different passages collide.

Case contract

Cells (x, y) with 0 <= x < w, 0 <= y < h. First pass over passages [[x1, y1], [x2, y2]]: out-of-bounds or non-orthogonally-adjacent pairs -> 'invalid-edge'; the same passage twice in either orientation -> 'duplicate'. Then union passages in order: joining already connected cells -> 'loop'. Finally 'perfect' if all cells are connected, else 'disconnected'.

Why this case matters

Procedural generators silently emit unplayable or unfair levels when a single constraint check uses the wrong boundary, axis, neighborhood or update order; the defect is visible in exact generated geometry.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(w, h, passages):
    seen = set()
    parent = {(x, y): (x, y) for x in range(w) for y in range(h)}
    def find(p):
        while parent[p] != p:
            parent[p] = parent[parent[p]]
            p = parent[p]
        return p
    for (x1, y1), (x2, y2) in passages:
        if not (0 <= x1 < w and 0 <= y1 < h and 0 <= x2 < w and 0 <= y2 < h):
            return 'invalid-edge'
        if abs(x1 - x2) + abs(y1 - y2) != 1:
            return 'invalid-edge'
        key = ((x1, y1), (x2, y2))
        if key in seen:
            return 'duplicate'
        seen.add(key)
    for (x1, y1), (x2, y2) in passages:
        a, b = find((x1, y1)), find((x2, y2))
        if a == b:
            return 'loop'
        parent[a] = b
    roots = {find(p) for p in parent}
    return 'perfect' if len(roots) == 1 else 'disconnected'
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
  ('fault site duplicate key #1',
   [4, 1, [[[2, 0], [1, 0]], [[3, 0], [2, 0]], [[0, 0], [1, 0]], [[1, 0], [0, 0]]]],
   'duplicate'),
  ('fault site duplicate key #2',
   [3, 1, [[[1, 0], [0, 0]], [[0, 0], [1, 0]], [[1, 0], [2, 0]]]],
   'duplicate'),
  ('partial repair boundary #1',
   [4,
    3,
    [[[1, 0], [1, 1]],
     [[0, 1], [0, 0]],
     [[0, 1], [0, 2]],
     [[2, 0], [2, 1]],
     [[1, 0], [0, 0]],
     [[1, 0], [2, 0]],
     [[2, 1], [2, 2]],
     [[2, 2], [3, 2]],
     [[2, 1], [3, 1]],
     [[2, 2], [1, 2]],
     [[1, 1], [0, 1]],
     [[0, 2], [1, 2]]]],
   'loop'),
  ('partial repair boundary #2',
   [3,
    3,
    [[[1, 2], [0, 2]],
     [[1, 0], [2, 0]],
     [[0, 0], [0, 1]],
     [[1, 1], [1, 0]],
     [[2, 1], [2, 0]],
     [[1, 1], [2, 1]],
     [[0, 2], [0, 2]]]],
   'invalid-edge'),
  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
  ('single cell maze #1', [1, 1, []], 'perfect'),
  ('control #1',
   [3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],
   'invalid-edge')],
 [('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
  ('fault site duplicate key #1',
   [3, 1, [[[1, 0], [0, 0]], [[0, 0], [1, 0]], [[1, 0], [2, 0]]]],
   'duplicate'),
  ('fault site duplicate key #2',
   [3,
    4,
    [[[1, 3], [2, 3]],
     [[0, 2], [1, 2]],
     [[2, 1], [2, 0]],
     [[1, 0], [2, 0]],
     [[2, 2], [2, 1]],
     [[0, 2], [0, 1]],
     [[0, 1], [1, 1]],
     [[1, 2], [1, 1]],
     [[1, 2], [2, 2]],
     [[2, 1], [2, 2]],
     [[1, 1], [1, 0]]]],
   'duplicate'),
  ('partial repair boundary #1',
   [3,
    3,
    [[[2, 1], [2, 0]],
     [[2, 0], [1, 0]],
     [[0, 1], [0, 0]],
     [[0, 1], [1, 1]],
     [[1, 0], [1, 1]],
     [[0, 0], [1, 0]],
     [[0, 1], [0, 2]]]],
   'loop'),
  ('partial repair boundary #2',
   [3, 2, [[[2, 1], [2, 0]], [[0, 1], [1, 1]], [[1, 0], [0, 0]], [[1, 1], [1, 0]]]],
   'disconnected'),
  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
  ('single cell maze #1', [1, 1, []], 'perfect'),
  ('control #1',
   [3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],
   'invalid-edge')],
 [('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
  ('fault site duplicate key #1',
   [2,
    3,
    [[[0, 0], [1, 0]],
     [[1, 0], [0, 0]],
     [[1, 2], [1, 1]],
     [[0, 1], [0, 1]],
     [[1, 0], [1, 1]],
     [[0, 1], [1, 1]],
     [[0, 1], [0, 2]],
     [[0, 2], [1, 2]]]],
   'duplicate'),
  ('fault site duplicate key #2',
   [3, 1, [[[1, 0], [2, 0]], [[0, 0], [1, 0]], [[1, 0], [0, 0]]]],
   'duplicate'),
  ('partial repair boundary #1',
   [4,
    2,
    [[[1, 0], [0, 0]],
     [[1, 0], [1, 1]],
     [[3, 0], [2, 0]],
     [[2, 1], [3, 1]],
     [[2, 1], [2, 0]],
     [[1, 1], [2, 1]],
     [[1, 1], [0, 1]],
     [[3, 1], [3, 0]]]],
   'loop'),
  ('partial repair boundary #2',
   [4,
    4,
    [[[0, 0], [1, 0]],
     [[0, 2], [0, 1]],
     [[2, 3], [2, 2]],
     [[2, 0], [3, 0]],
     [[1, 2], [2, 2]],
     [[3, 1], [3, 0]],
     [[3, 2], [2, 2]],
     [[2, 1], [2, 0]],
     [[3, 2], [3, 3]],
     [[1, 1], [0, 1]],
     [[1, 2], [1, 1]],
     [[0, 2], [1, 2]],
     [[3, 1], [3, 2]]]],
   'loop'),
  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
  ('single cell maze #1', [1, 1, []], 'perfect'),
  ('control #1',
   [3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],
   'invalid-edge')],
 [('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
  ('fault site duplicate key #1',
   [4, 2, [[[1, 1], [1, 0]], [[2, 0], [2, 1]], [[2, 1], [1, 1]], [[2, 1], [2, 0]], [[0, 0], [0, 1]]]],
   'duplicate'),
  ('fault site duplicate key #2',
   [3,
    2,
    [[[2, 1], [2, 0]],
     [[2, 0], [2, 1]],
     [[0, 0], [0, 1]],
     [[0, 0], [1, 0]],
     [[1, 1], [2, 1]],
     [[1, 0], [2, 0]],
     [[1, 0], [1, 1]]]],
   'duplicate'),
  ('partial repair boundary #1',
   [4,
    4,
    [[[0, 0], [0, 1]],
     [[2, 0], [3, 0]],
     [[0, 2], [0, 1]],
     [[1, 0], [2, 0]],
     [[2, 1], [3, 1]],
     [[1, 3], [2, 3]],
     [[3, 3], [3, 2]],
     [[0, 2], [0, 3]],
     [[2, 1], [1, 1]],
     [[2, 2], [2, 1]],
     [[1, 3], [0, 3]],
     [[1, 1], [1, 2]],
     [[2, 0], [2, 1]],
     [[2, 2], [2, 3]],
     [[2, 3], [3, 3]],
     [[1, 2], [2, 2]]]],
   'loop'),
  ('partial repair boundary #2',
   [3, 2, [[[0, 1], [0, 0]], [[1, 1], [2, 1]], [[1, 1], [0, 1]], [[1, 0], [1, 1]], [[2, 1], [2, 0]]]],
   'perfect'),
  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
  ('single cell maze #1', [1, 1, []], 'perfect'),
  ('control #1', [4, 1, [[[2, 0], [2, 0]], [[1, 0], [0, 0]], [[2, 0], [1, 0]]]], 'invalid-edge')],
 [('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
  ('fault site duplicate key #1',
   [1, 4, [[[0, 2], [0, 3]], [[0, 0], [0, 1]], [[0, 3], [0, 2]]]],
   'duplicate'),
  ('fault site duplicate key #2',
   [1, 4, [[[0, 3], [0, 2]], [[0, 1], [0, 2]], [[0, 2], [0, 3]], [[0, 0], [0, 1]]]],
   'duplicate'),
  ('partial repair boundary #1',
   [2,
    4,
    [[[1, 2], [1, 1]],
     [[1, 0], [0, 0]],
     [[1, 1], [0, 1]],
     [[0, 1], [0, 2]],
     [[1, 0], [1, 1]],
     [[0, 2], [1, 2]]]],
   'loop'),
  ('partial repair boundary #2', [2, 2, [[[1, 1], [0, 1]], [[1, 0], [1, 1]], [[0, 0], [0, 1]]]], 'perfect'),
  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
  ('single cell maze #1', [1, 1, []], 'perfect'),
  ('control #1',
   [3,
    3,
    [[[1, 0], [1, 0]],
     [[1, 0], [2, 0]],
     [[0, 2], [0, 1]],
     [[2, 2], [2, 1]],
     [[0, 2], [1, 2]],
     [[1, 0], [0, 0]],
     [[0, 1], [1, 1]]]],
   'invalid-edge')]]
for label, args, expected in cases[N-1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
reversed duplicate #1loopduplicateFailed
fault site duplicate key #1loopduplicateFailed
fault site duplicate key #2loopduplicateFailed
partial repair boundary #1looploopPassed
partial repair boundary #2invalid-edgeinvalid-edgePassed
diagonal passage #1invalid-edgeinvalid-edgePassed
single cell maze #1perfectperfectPassed
control #1invalid-edgeinvalid-edgePassed

SHA-256 / 345245dc80a13b269211b3fc1a12c0fc472da8df94a609e3b0795cf1476059ca

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(w, h, passages):
    seen = set()
    parent = {(x, y): (x, y) for x in range(w) for y in range(h)}
    def find(p):
        while parent[p] != p:
            parent[p] = parent[parent[p]]
            p = parent[p]
        return p
    for (x1, y1), (x2, y2) in passages:
        if not (0 <= x1 < w and 0 <= y1 < h and 0 <= x2 < w and 0 <= y2 < h):
            return 'invalid-edge'
        if abs(x1 - x2) + abs(y1 - y2) != 1:
            return 'invalid-edge'
        key = tuple(sorted([x1, y1, x2, y2]))
        if key in seen:
            return 'duplicate'
        seen.add(key)
    for (x1, y1), (x2, y2) in passages:
        a, b = find((x1, y1)), find((x2, y2))
        if a == b:
            return 'loop'
        parent[a] = b
    roots = {find(p) for p in parent}
    return 'perfect' if len(roots) == 1 else 'disconnected'
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
  ('fault site duplicate key #1',
   [4, 1, [[[2, 0], [1, 0]], [[3, 0], [2, 0]], [[0, 0], [1, 0]], [[1, 0], [0, 0]]]],
   'duplicate'),
  ('fault site duplicate key #2',
   [3, 1, [[[1, 0], [0, 0]], [[0, 0], [1, 0]], [[1, 0], [2, 0]]]],
   'duplicate'),
  ('partial repair boundary #1',
   [4,
    3,
    [[[1, 0], [1, 1]],
     [[0, 1], [0, 0]],
     [[0, 1], [0, 2]],
     [[2, 0], [2, 1]],
     [[1, 0], [0, 0]],
     [[1, 0], [2, 0]],
     [[2, 1], [2, 2]],
     [[2, 2], [3, 2]],
     [[2, 1], [3, 1]],
     [[2, 2], [1, 2]],
     [[1, 1], [0, 1]],
     [[0, 2], [1, 2]]]],
   'loop'),
  ('partial repair boundary #2',
   [3,
    3,
    [[[1, 2], [0, 2]],
     [[1, 0], [2, 0]],
     [[0, 0], [0, 1]],
     [[1, 1], [1, 0]],
     [[2, 1], [2, 0]],
     [[1, 1], [2, 1]],
     [[0, 2], [0, 2]]]],
   'invalid-edge'),
  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
  ('single cell maze #1', [1, 1, []], 'perfect'),
  ('control #1',
   [3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],
   'invalid-edge')],
 [('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
  ('fault site duplicate key #1',
   [3, 1, [[[1, 0], [0, 0]], [[0, 0], [1, 0]], [[1, 0], [2, 0]]]],
   'duplicate'),
  ('fault site duplicate key #2',
   [3,
    4,
    [[[1, 3], [2, 3]],
     [[0, 2], [1, 2]],
     [[2, 1], [2, 0]],
     [[1, 0], [2, 0]],
     [[2, 2], [2, 1]],
     [[0, 2], [0, 1]],
     [[0, 1], [1, 1]],
     [[1, 2], [1, 1]],
     [[1, 2], [2, 2]],
     [[2, 1], [2, 2]],
     [[1, 1], [1, 0]]]],
   'duplicate'),
  ('partial repair boundary #1',
   [3,
    3,
    [[[2, 1], [2, 0]],
     [[2, 0], [1, 0]],
     [[0, 1], [0, 0]],
     [[0, 1], [1, 1]],
     [[1, 0], [1, 1]],
     [[0, 0], [1, 0]],
     [[0, 1], [0, 2]]]],
   'loop'),
  ('partial repair boundary #2',
   [3, 2, [[[2, 1], [2, 0]], [[0, 1], [1, 1]], [[1, 0], [0, 0]], [[1, 1], [1, 0]]]],
   'disconnected'),
  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
  ('single cell maze #1', [1, 1, []], 'perfect'),
  ('control #1',
   [3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],
   'invalid-edge')],
 [('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
  ('fault site duplicate key #1',
   [2,
    3,
    [[[0, 0], [1, 0]],
     [[1, 0], [0, 0]],
     [[1, 2], [1, 1]],
     [[0, 1], [0, 1]],
     [[1, 0], [1, 1]],
     [[0, 1], [1, 1]],
     [[0, 1], [0, 2]],
     [[0, 2], [1, 2]]]],
   'duplicate'),
  ('fault site duplicate key #2',
   [3, 1, [[[1, 0], [2, 0]], [[0, 0], [1, 0]], [[1, 0], [0, 0]]]],
   'duplicate'),
  ('partial repair boundary #1',
   [4,
    2,
    [[[1, 0], [0, 0]],
     [[1, 0], [1, 1]],
     [[3, 0], [2, 0]],
     [[2, 1], [3, 1]],
     [[2, 1], [2, 0]],
     [[1, 1], [2, 1]],
     [[1, 1], [0, 1]],
     [[3, 1], [3, 0]]]],
   'loop'),
  ('partial repair boundary #2',
   [4,
    4,
    [[[0, 0], [1, 0]],
     [[0, 2], [0, 1]],
     [[2, 3], [2, 2]],
     [[2, 0], [3, 0]],
     [[1, 2], [2, 2]],
     [[3, 1], [3, 0]],
     [[3, 2], [2, 2]],
     [[2, 1], [2, 0]],
     [[3, 2], [3, 3]],
     [[1, 1], [0, 1]],
     [[1, 2], [1, 1]],
     [[0, 2], [1, 2]],
     [[3, 1], [3, 2]]]],
   'loop'),
  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
  ('single cell maze #1', [1, 1, []], 'perfect'),
  ('control #1',
   [3, 2, [[[2, 1], [1, 1]], [[0, 1], [0, 0]], [[1, 1], [2, 2]], [[0, 0], [1, 0]]]],
   'invalid-edge')],
 [('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
  ('fault site duplicate key #1',
   [4, 2, [[[1, 1], [1, 0]], [[2, 0], [2, 1]], [[2, 1], [1, 1]], [[2, 1], [2, 0]], [[0, 0], [0, 1]]]],
   'duplicate'),
  ('fault site duplicate key #2',
   [3,
    2,
    [[[2, 1], [2, 0]],
     [[2, 0], [2, 1]],
     [[0, 0], [0, 1]],
     [[0, 0], [1, 0]],
     [[1, 1], [2, 1]],
     [[1, 0], [2, 0]],
     [[1, 0], [1, 1]]]],
   'duplicate'),
  ('partial repair boundary #1',
   [4,
    4,
    [[[0, 0], [0, 1]],
     [[2, 0], [3, 0]],
     [[0, 2], [0, 1]],
     [[1, 0], [2, 0]],
     [[2, 1], [3, 1]],
     [[1, 3], [2, 3]],
     [[3, 3], [3, 2]],
     [[0, 2], [0, 3]],
     [[2, 1], [1, 1]],
     [[2, 2], [2, 1]],
     [[1, 3], [0, 3]],
     [[1, 1], [1, 2]],
     [[2, 0], [2, 1]],
     [[2, 2], [2, 3]],
     [[2, 3], [3, 3]],
     [[1, 2], [2, 2]]]],
   'loop'),
  ('partial repair boundary #2',
   [3, 2, [[[0, 1], [0, 0]], [[1, 1], [2, 1]], [[1, 1], [0, 1]], [[1, 0], [1, 1]], [[2, 1], [2, 0]]]],
   'perfect'),
  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
  ('single cell maze #1', [1, 1, []], 'perfect'),
  ('control #1', [4, 1, [[[2, 0], [2, 0]], [[1, 0], [0, 0]], [[2, 0], [1, 0]]]], 'invalid-edge')],
 [('reversed duplicate #1', [2, 1, [[[0, 0], [1, 0]], [[1, 0], [0, 0]]]], 'duplicate'),
  ('fault site duplicate key #1',
   [1, 4, [[[0, 2], [0, 3]], [[0, 0], [0, 1]], [[0, 3], [0, 2]]]],
   'duplicate'),
  ('fault site duplicate key #2',
   [1, 4, [[[0, 3], [0, 2]], [[0, 1], [0, 2]], [[0, 2], [0, 3]], [[0, 0], [0, 1]]]],
   'duplicate'),
  ('partial repair boundary #1',
   [2,
    4,
    [[[1, 2], [1, 1]],
     [[1, 0], [0, 0]],
     [[1, 1], [0, 1]],
     [[0, 1], [0, 2]],
     [[1, 0], [1, 1]],
     [[0, 2], [1, 2]]]],
   'loop'),
  ('partial repair boundary #2', [2, 2, [[[1, 1], [0, 1]], [[1, 0], [1, 1]], [[0, 0], [0, 1]]]], 'perfect'),
  ('diagonal passage #1', [2, 2, [[[0, 0], [1, 1]]]], 'invalid-edge'),
  ('single cell maze #1', [1, 1, []], 'perfect'),
  ('control #1',
   [3,
    3,
    [[[1, 0], [1, 0]],
     [[1, 0], [2, 0]],
     [[0, 2], [0, 1]],
     [[2, 2], [2, 1]],
     [[0, 2], [1, 2]],
     [[1, 0], [0, 0]],
     [[0, 1], [1, 1]]]],
   'invalid-edge')]]
for label, args, expected in cases[N-1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
reversed duplicate #1duplicateduplicatePassed
fault site duplicate key #1duplicateduplicatePassed
fault site duplicate key #2duplicateduplicatePassed
partial repair boundary #1duplicateloopFailed
partial repair boundary #2duplicateinvalid-edgeFailed
diagonal passage #1invalid-edgeinvalid-edgePassed
single cell maze #1perfectperfectPassed
control #1invalid-edgeinvalid-edgePassed

SHA-256 / 638953ec1e36659c2771a86402e87c59d8944370d0a3c06e21fa66f7436cb70d

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 8 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

Member access is invitation-based. Sign in with your invited account to inspect the repair.

Sign in to the archive ↗

Verification & scope

Deterministic toy contract stipulated for this model; integer or exact arithmetic only, not a reproduction of any specific game engine. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:50:51.281461+00:00.

Case digest / 16f76642af7b8bd7a71f9093f7d789e0b2be9a703aad358b06fcd15c790ce056