Once Visited, Never Forgotten

A soprano enters, then four beats later the alto follows with the same melody. The tenor waits another four beats, then the bass. Each voice must remember not just their own notes, but when they started — otherwise the canon collapses into chaos. This is memoization in music: storing computed results to avoid redundant work.

Consider a knight’s tour solver that checks if position (x,y) leads to a solution. Without memory, it might visit the same failing position thousands of times. Memoization fixes this by remembering: “I’ve been to (3,4) and it doesn’t work.”

local memo = {}

function knight_tour(x, y, visited)
  local key = x .. "," .. y
  if memo[key] then return memo[key] end
  
  if visited == 64 then return true end
  if x < 1 or x > 8 or y < 1 or y > 8 then 
    memo[key] = false
    return false 
  end
  
  -- Try knight moves: (2,1), (2,-1), etc.
  for _, move in ipairs({{2,1}, {2,-1}, {-2,1}, {-2,-1}}) do
    if knight_tour(x + move[1], y + move[2], visited + 1) then
      memo[key] = true
      return true
    end
  end
  
  memo[key] = false
  return false
end

Lua’s table-as-hash-map makes memoization elegant. The C version trades readability for speed:

int memo[64] = {0}; // 0=unknown, 1=success, -1=failure

int knight_tour(int pos, int moves) {
    if (memo[pos] != 0) return memo[pos] == 1;
    if (moves == 64) return memo[pos] = 1;
    
    int x = pos % 8, y = pos / 8;
    int knight_moves[] = {-17,-15,-10,-6,6,10,15,17};
    
    for (int i = 0; i < 8; i++) {
        int next = pos + knight_moves[i];
        if (next >= 0 && next < 64 && 
            abs((next % 8) - x) <= 2 &&
            knight_tour(next, moves + 1)) {
            return memo[pos] = 1;
        }
    }
    return memo[pos] = -1;
}

Both store failure as eagerly as success. In choral canons, this prevents voices from entering at impossible moments — the music remembers its own constraints. The knight remembers dead-end squares; the canon remembers impossible harmonies. Memory makes both elegant.