263 — Solving Sudoku with Ant Colony Optimisation

Ant colony optimization (ACO) is a family of algorithms in which individual, simple automaton agents navigate a graph according to a naïve, simple ruleset — and out of which complex emergent behaviors solve a more complex task.

ACOs are great for tasks that don’t have clear graph-traversal answers, such as complex mathematical challenges or challenges of prohibitively large graph-scale.

Sudokus are NP-complete, and can be represented as a graph traversal, or map-coloring problem, where peers — cells that are prohibited by the rules of sudoku from having the same value — are connected to non-peers (all other cells).

Ants are each given a copy of the puzzle, onto which they attempt to “fix” as many values as possible. They drop “pheromone” when they have high confidence of having made a correct value fixation, and which attracts ants on further iterations to attempt the same initial steps. This value is normalized to the global highest-pheromone-concentration but gradually “evaporated,” which prevents the algorithm from converging on a local maximum (“stagnation”).

Using biology to solve complex problems is becoming increasingly popular, and I’ve read a bit about similar methods in the past ([#91], [#6]). This motion-coordination work is particularly exciting as we get closer to high-speed multi-core hardware.