Demo implementation of the original red-blue pebble game by Hong & Kung, STOC '81
Development assisted by DeepSeek AI
Fast Memory (Red)
Slow Memory (Blue)
Empty Node
Moves: 0
Click "Generate Layered DAG" to start!

Game Rules:

  1. Generate Layered DAG: Creates a directed acyclic graph with nodes in layers
  2. Place Blue: Place a blue pebble on any node that has a red pebble. Cost: 1 move
  3. Place Red: Two ways:
    • On a node where all predecessors have red: Cost: 0 moves
    • On a node with a blue pebble: Cost: 1 move
  4. Delete Red: Remove a red pebble from any node. Cost: 0 moves
  5. Initial State: Source nodes (no incoming edges) start with blue pebbles
  6. Memory Limits: Red pebbles limited, blue pebbles unlimited
  7. Goal: Cover all output nodes with blue pebbles using minimal number of moves