Remove all the pieces from a chess board except for one knight. Then try to move the knight across all 64 squares of the board, touching each once. (As a reminder, knights move in a L-shape, two spaces in one direction, and then one space left or right, or up or down, at a 90- degree angle.) This so-called “knight’s tour” is very difficult to achieve for a single person, but mathematicians have calculated that there are a mind-boggling number of ways to pull it off. If you end up at the spot you started, you’d be completing a so-called “closed tour.” There are more than 26 trillion ways to do this. If you merely touch every spot, without returning to your point of origin, it’s called an open tour. The number of ways to do this is so large that scientists haven’t calculated it.
Searching for new solutions to the knight’s tour, a problem that has intrigued mathematicians for centuries, University of Nottingham computer scientist Graham Kendall and a colleague turned to simulated ants. They used the ant colony optimization algorithm, a swarm intelligence technique based on the behavior of ants looking to find a path between their colony and a food source. It works like this, as Kendall explains at The Conversation:
A computer program is used to simulate a population of ants. These ants are assigned the task to find a solution to a problem. As each ant goes about their task they lay a pheromone trail – a smelly substance that ants use to communicate with each other. In the simulated algorithm, the most successful ants (the ones that solve the problem better), lay more pheromone than those that perform poorly.
This program is repeated hundreds of thousands of times, placing more “pheromones” on paths that complete a tour. But a balance must be struck between reinforcing paths that work, and emphasizing finding new trails.
Using the program, Kendall and his colleague found nearly 500,000 novel solutions to the knight’s tour. Who knew that (simulated) ants could find new answers to a question that has intrigued peope for centuries?
