Introduction

Picture a golfer standing on a hilly landscape — the height of the terrain is the quality of a solution to some hard problem. The golfer wants to reach the highest peak, but they can only take steps to neighboring spots. The trap: many hills have local peaks that are not the global best. A climber who only ever steps upward gets stuck there.

Simulated annealing escapes by occasionally accepting a downhill step, with a probability that shrinks over time — mimicking how a metal cools and its atoms settle. The idea works, but the temperature schedule and the acceptance probability add complexity that can be tricky to tune.

In 1993, the physicist Günter Dueck published a strikingly simpler idea: instead of a cooling temperature, imagine the landscape flooding with water. The water level rises steadily from the starting quality. You may move to any neighboring solution — as long as it stays above the waterline. As the flood rises, solutions below the current level become forbidden; the search is squeezed upward until only high-quality solutions remain reachable.

No probability. No temperature schedule. Just a rising threshold and the rule: stay above the water.

The algorithm was named the Great Deluge (after the biblical flood) and published alongside a companion heuristic called Record-to-Record Travel in the journal Journal of Computational Physics. Both have since found a home in scheduling, timetabling, and combinatorial optimization.

Try It

Below is a one-dimensional landscape. The dot is the current solution; the blue fill is the rising water. At each step the algorithm tries a random neighbor and accepts it only if it stays above the waterline. Watch as the flood closes off lower valleys and forces the dot upward.

<!-- Main layout — controls bar + canvas + status line -->
<div class="controls">
  <label>Rain Rate <span id="rain-val">3</span>%
    <input type="range" id="rain-slider" min="1" max="10" value="3" step="1">
  </label>
  <button id="btn-step" type="button">Step</button>
  <button id="btn-run" type="button">Run</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<canvas id="cv" width="560" height="230"></canvas>
<div class="status" id="status">Press Run to start, or Step one move at a time.</div>

/* Minimal reset + layout styles */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; background: transparent; }
.controls { display: flex; gap: .6rem; flex-wrap: wrap; align-items: center; margin-bottom: .6rem; }
label { font-size: .85rem; display: flex; align-items: center; gap: .4rem; white-space: nowrap; }
input[type=range] { width: 80px; accent-color: #1d3557; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
canvas { display: block; width: 100%; max-width: 560px; border-radius: 8px;
         background: #f4f7fa; border: 1px solid #cdd9e3; }
/* Status line color coding */
.status { font-size: .9rem; font-weight: 600; margin-top: .5rem; min-height: 1.4em; }
.status.running { color: #1d63b0; }
.status.done { color: #0a7d33; }
.status.stuck { color: #c92f3c; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// Landscape function — sum of sinusoids to create multiple peaks and valleys
const W = 560, H = 230, PAD = 30;
const PLOT_W = W - PAD * 2, PLOT_H = H - PAD * 2;

// Multiple sinusoids produce a bumpy landscape with a clear global peak
function landscape(x) {
  return 0.55 * Math.sin(x * 1.8) +
         0.25 * Math.sin(x * 4.5 + 1.2) +
         0.12 * Math.sin(x * 9.0 + 0.7) +
         0.08 * Math.sin(x * 17.0 + 2.1);
}

// Sample the landscape at N evenly spaced positions
const N = 200;
const xs = Array.from({ length: N }, (_, i) => i / (N - 1));
const ys = xs.map(landscape);
const yMin = Math.min(...ys);
const yMax = Math.max(...ys);
const yRange = yMax - yMin;

function norm(y) { return (y - yMin) / yRange; } // Map y to [0,1] for water-level comparisons

// Algorithm state
let pos = 0;        // current index into xs/ys
let waterLevel = 0; // normalized water level in [0,1]
let running = false;
let animId = null;
let stepCount = 0;
const MAX_STEPS = 600;
const NEIGHBOR_RADIUS = 12; // max index distance for a single step

const cv = document.getElementById('cv');
const ctx = cv.getContext('2d');
const statusEl = document.getElementById('status');
const rainSlider = document.getElementById('rain-slider');
const rainVal = document.getElementById('rain-val');
const btnStep = document.getElementById('btn-step');
const btnRun = document.getElementById('btn-run');
const btnReset = document.getElementById('btn-reset');

// Map logical coordinates to canvas pixels
function toCanvasX(i) { return PAD + (i / (N - 1)) * PLOT_W; }
function toCanvasY(y) { return PAD + PLOT_H - norm(y) * PLOT_H; }

function draw() {
  ctx.clearRect(0, 0, W, H);

  // Blue water fill below the water level
  const wlY = toCanvasY(waterLevel * yRange + yMin);
  ctx.fillStyle = 'rgba(100,160,230,0.25)';
  ctx.fillRect(PAD, wlY, PLOT_W, H - PAD - wlY + 2);

  // Draw the landscape curve
  ctx.beginPath();
  ctx.moveTo(toCanvasX(0), toCanvasY(ys[0]));
  for (let i = 1; i < N; i++) ctx.lineTo(toCanvasX(i), toCanvasY(ys[i]));
  ctx.strokeStyle = '#1d3557';
  ctx.lineWidth = 2;
  ctx.stroke();

  // Dashed waterline
  ctx.beginPath();
  ctx.moveTo(PAD, wlY);
  ctx.lineTo(PAD + PLOT_W, wlY);
  ctx.strokeStyle = 'rgba(50,130,220,0.8)';
  ctx.lineWidth = 1.5;
  ctx.setLineDash([6, 4]);
  ctx.stroke();
  ctx.setLineDash([]);

  // Red dot for current solution position
  const dx = toCanvasX(pos);
  const dy = toCanvasY(ys[pos]);
  ctx.beginPath();
  ctx.arc(dx, dy, 7, 0, Math.PI * 2);
  ctx.fillStyle = '#e63946';
  ctx.fill();
  ctx.strokeStyle = '#fff';
  ctx.lineWidth = 2;
  ctx.stroke();
}

function getRainRate() {
  return Number(rainSlider.value) * 0.001 * 0.5;
}

// One step of the Great Deluge algorithm
function step() {
  const lo = Math.max(0, pos - NEIGHBOR_RADIUS);
  const hi = Math.min(N - 1, pos + NEIGHBOR_RADIUS);
  const candidate = lo + Math.floor(Math.random() * (hi - lo + 1));
  const candidateNorm = norm(ys[candidate]);

  // Accept the move only if the candidate is at or above the current water level
  if (candidateNorm >= waterLevel) {
    pos = candidate;
  }
  // Raise the water level by the rain rate after each step
  waterLevel = Math.min(waterLevel + getRainRate(), 1);
  stepCount++;
}

function setStatus(msg, cls) {
  statusEl.textContent = msg;
  statusEl.className = 'status ' + cls;
}

function reset() {
  cancelAnimationFrame(animId);
  running = false;
  pos = Math.floor(Math.random() * N);
  waterLevel = norm(ys[pos]) * 0.05;
  stepCount = 0;
  btnRun.textContent = 'Run';
  btnStep.disabled = false;
  draw();
  setStatus('Press Run to start, or Step one move at a time.', '');
}

function runLoop() {
  if (!running) return;
  const quality = norm(ys[pos]);
  for (let i = 0; i < 3; i++) step(); // Run 3 steps per animation frame for visible motion
  draw();
  if (stepCount >= MAX_STEPS || waterLevel >= 0.98) {
    running = false;
    btnRun.textContent = 'Run';
    btnStep.disabled = false;
    const pct = Math.round(norm(ys[pos]) * 100);
    setStatus(i18nFmt('Settled at quality %pct%% — flood complete.', { pct: pct }), 'done');
    return;
  }
  setStatus(i18nFmt('Step %step% — water at %wl%%', { step: stepCount, wl: Math.round(waterLevel * 100) }), 'running');
  animId = requestAnimationFrame(runLoop);
}

btnStep.addEventListener('click', () => {
  if (running) return;
  step();
  draw();
  const pct = Math.round(norm(ys[pos]) * 100);
  setStatus(i18nFmt('Step %step% — quality %pct%%, water at %wl%%', { step: stepCount, pct: pct, wl: Math.round(waterLevel * 100) }), '');
});

btnRun.addEventListener('click', () => {
  if (running) {
    running = false;
    cancelAnimationFrame(animId);
    btnRun.textContent = 'Run';
    btnStep.disabled = false;
    setStatus('Paused. Press Run to continue.', '');
  } else {
    running = true;
    btnRun.textContent = 'Pause';
    btnStep.disabled = true;
    runLoop();
  }
});

btnReset.addEventListener('click', reset);
rainSlider.addEventListener('input', () => { rainVal.textContent = rainSlider.value; });

reset();
Result
Console

Drag the Rain Rate slider to control how fast the water rises. A slow rain gives the search more time to explore; a fast rain rushes the dot to higher ground before it has mapped the terrain. The best setting depends on the landscape — tuning the rain rate is the main practical knob on the Great Deluge.

The Real Complexity

The Great Deluge is a metaheuristic — a strategy for searching large solution spaces that offers no polynomial-time guarantee on hard problems.

  • Each step is cheap. Evaluating a neighbor and comparing it to the water level costs the same as one quality evaluation — O(1)O(1) extra work per move.
  • No guarantee of optimality. For NP-hard problems like scheduling or graph coloring, no efficient algorithm is known to always find the global optimum, and the Great Deluge is no exception.
  • Deterministic acceptance. Unlike simulated annealing, the Great Deluge never accepts a worse solution. It only accepts neighbors that are at least as good as the current water level. This makes behavior easier to reason about — and sometimes easier to tune.
  • Rain rate is everything. If the water rises too fast the search locks in prematurely; too slow and it wastes time exploring swamped terrain. In practice, the rain rate is set as a fraction of the initial quality range: rain=α⋅(qmax⁡−qmin⁡)\text{rain} = \alpha \cdot (q_{\max} - q_{\min}) per step, where α\alpha is typically between 10−510^{-5} and 10−310^{-3}.
  • Variants extend the idea. The flex-deluge resets the water if progress stalls; the star-deluge adjusts the rate dynamically. Each trades simplicity for robustness.

The practical payoff is that the Great Deluge is often faster to implement and tune than simulated annealing, and on many benchmark problems it finds solutions of comparable or better quality.

Where It Matters

The Great Deluge's combination of simplicity and effectiveness has made it a practical choice wherever combinatorial search is needed:

  • University timetabling: assigning lectures, rooms and timeslots so no student has a clash is a classic NP-hard problem. The Great Deluge consistently ranks among the top metaheuristics in the International Timetabling Competition benchmarks.
  • Nurse and staff scheduling: hospital rosters must satisfy dozens of hard constraints (shift lengths, rest periods, qualifications). The rising water level naturally enforces hard constraints as forbidden zones.
  • Graph partitioning: dividing a chip's circuit graph into balanced parts with few cut edges is a core step in VLSI design, and the Great Deluge has been applied successfully here.
  • Vehicle routing: finding good delivery tours under time windows and capacity limits is another domain where the algorithm's deterministic acceptance simplifies parallelization.
  • Teaching metaheuristics: because the idea — stay above the flood — is so vivid, the Great Deluge is an excellent first example of how not every good algorithm relies on probability.

Together these uses show that "accept anything above the waterline" is a surprisingly powerful primitive for hard combinatorial problems, complementing approaches like simulated annealing and exact methods.

Conclusion

The Great Deluge algorithm distills a deep idea into a single vivid image: your current solution stands on a landscape, and the water is rising. Every move that keeps you above the flood is allowed; every move that drowns you is forbidden. As the level climbs, bad valleys disappear, and only high-quality ground remains.

The elegance is in what it removes. No temperature. No acceptance probability. No cooling schedule. Just a steadily rising threshold — and the pressure it applies is enough to guide a random walk toward good solutions in a surprisingly wide range of hard problems.

The next time you face a problem too large for exact methods, remember the flood. Sometimes the simplest constraint — stay above the waterline — is all the guidance a search needs.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/great-deluge-algorithm/Content licensed under CC BY-NC 4.0.