Algorithm dossier

  • Category: Game AI
  • Worst-case complexity: O(2ⁿ)
  • Approach: Backtracking
  • Data structure: Array
  • First formalised: 1850s

Why this snippet is N-Queens

Why N-Queens. Backtracking on an n×n board. Try placing one symbol per row; for each row, scan columns and reject any that conflict with a prior row on column equality or on the diagonal check abs(p[i] - c) == r - i. The pop after the recursive call is the *backtrack* step — undo the placement before trying the next column. Distinguishing feature. Two-conflict check (same column OR same diagonal) is the give-away; the diagonal arithmetic is the elegant compression — same diagonal iff row-difference equals column-difference.

How to read a redacted algorithm

Algodle strips identifier names so the snippet has to be read for its shape: the control flow, the data structures it manipulates, the order in which it visits its input. Loops with two pointers crawling toward each other are usually search or partition. A recursion that splits its input in half and recurses on both halves is divide-and-conquer. A priority queue plus graph traversal is almost certainly Dijkstra, Prim, or A*. Six hint columns — category, complexity, approach, data structure, era — let you triangulate even when the snippet itself is opaque.