Simulated Annealing

Using simulated annealing to search the solution space of a sudoku board.

TL;DR:

Simulated annealing is an optimization technique inspired by metallurgy that lets you escape local maxima by occasionally making worse moves. It's ideal when you're lost in a search space with no obvious path to follow and when "good enough" is good enough.

Why Simulated Annealing?

Imagine you're a mountain climber traversing in a whiteout with no idea where the highest peak is. Your altimeter is the only instrument you can rely on to feel your way uphill. You climb and climb… until you're stuck on a bump that feels like the summit, but isn't. That's hill climbing, and it's great - until it's not. Because it gets stuck. Simulated Annealing (SA) is your solution when:

• You need to avoid getting stuck in local maxima/minima.
• You don't have reliable heuristics or a clear gradient to follow - just vague intuition & a noisy objective function (eg your altimeter).
• You don't need the best answer, just a pretty good one, and fast.

The Physics Behind the Madness

Simulated Annealing takes inspiration from metallurgy, where materials are heated and then slowly cooled to remove defects and reach a low-energy crystalline state. The basic idea? Start hot, so atoms (or solution candidates) jiggle freely. Cool gradually, letting them settle into a stable, minimal-energy structure. In optimization terms:

• Each "atom" is a variable in your problem.
• The “energy” is the cost or objective function.
• Randomness allows exploration of poor solutions early on.
• Cooling schedules gradually reduce that randomness.

The Algorithm

1. define an initial solution
2. perturb the current solution
3. quantify the cost/fitness of the solution
4. if the current solution is better, continue in that direction, else
5. if the current solution has enough merit/viability, explore it
6. stop if a good enough solution has been found
7. stop if time limit reached
8. repeat from step 2

The algorithm is relatively simple, especially since naïve functions for cost() & perturb() can work surprisingly well. Here are the bits from my React component below that demonstrate stepping through candidate solutions:

React.useEffect(() => {
  if (!running) return

  const step = () => {
    const next = newState(perturb(current.board))
    const delta = next.cost - current.cost
    const viability = Math.exp(-delta / T)

    if (delta < 0 || viability > Math.random()) {
      current = next
      setCurrent(current)
      if (next.cost < best.cost) {
        best = current
        setBest(best)
      }
      if (best.cost === 0) {
        setRunning(false)
      }
    }

    T *= 0.999
    setTemperature(T)
    raf.current = requestAnimationFrame(step)
  }

  raf.current = requestAnimationFrame(step)
  return () => cancelAnimationFrame(raf.current!)
}, [running])

Why Accept Worse Solutions?

Think of it as a climber willing to downclimb & traverse over to a more favorable to the top. The probability P of accepting a worse solution typically follows the formula P = exp(-ΔE / T) where:

• ΔE is the difference in cost between the new & current solutions
• T is the current temperature

Early on, you're more pliable and willing to say "Sure, let's go that way even if it sucks." As the day progresses, you're more likely to commit to the path you're on. If you don't end up bagging that peak, it was still a good day.

Bit-Flipping Your Way to Bliss

Even minor random changes - tweaking a bit here or nudging a variable there - can radically transform your path through the search space. SA's magic lies in how small perturbations allow a system to self-organize into an optimal(ish) configuration. This is why simulated annealing is often used in:

• NP-hard problems (like the Traveling Salesman Problem)
• AI (e.g. neural net architecture search)
• Creative generative processes (e.g. design/layout)

Code Sample

I thought it would be interesting to see how it performs when trying to find a sudoku solution. SA is not the tool to reach for in this case but it is interesting to see how it manages to settle on decent solutions.

Parting Thoughts

Simulated Annealing is a rare blend of elegance & pragmatism. It embraces uncertainty, plays the long game, and rewards systems that let a little chaos dance through their bits until everything settles into place.

It may not always find the best solution, but sometimes the peak you're on is good enough to plant a flag. Think of it as optimization with a stoic heart: accept the heat, embrace the discomfort, and trust that in time, things will cool into order.