- 3D printing
- Audio IO on RISC OS
- Desktop Tracker
- Dune II
- Matrix Orbital
- PCB Drill
- Talking Canvas Jnr
- Active project
- Source code
Travelling salesman problem
This is quite long, I'm afraid!
One of the most well-known problems in computing (or mathematics) is known as the travelling salesman problem. This is basically all about a salesman who has to travel to a certain number of cities and they need to know the quickest way to achieve this.
Working out the most efficient way to drill the holes on the board is basically this problem.
And the problem is quite difficult to solve - if you had 5 different locations, then there are 5x4x3x2(x1) possible answers (also known as 5 factorial, or 5! for short). If it took 1 second to calculate a solution, then it'll take you 120 seconds to find all the answers. If you add a new location, then it's now 6! - or 720 seconds. A seventh point increases this to 5040 seconds, or 1 hour 24 minutes.
The board above has 130 points on it, which means that there are 6.466x10219 possible solutions. Even if it took 1µs (1 millionth of a second) to find the answer, it'll take 6.466x10213 seconds - or 7.484x10208 days. Or 2.0499x10206 years. In case you don't know what that is, here it is in full:
I think that's right!
Since I can't wait that long - and nor can most people - you don't normally try every possible combination to see what is the best.
As it is a well-known problem, there are plenty of people who have written up on this. But copying someone else is not any kind of challenge to me!