This is the first blog entry to talk about where Rogo comes from. It has two origins – Rogaining, and Operations Research. Last week I talked about Rogaining, so today it will be Operations Research.
Dr Rogo discovers Operations Research
First, a little personal history. I loved mathematics at school and liked problem solving and puzzles (though Sudoku was not yet around), so when in the final section of an introductory Economics College course I was introduced to Operations Research, or Operational Research as it used to be called in New Zealand, it was love at first sight. I couldn’t believe my luck at finding a subject that used mathematics to solve problems in the real world, that related to people. Back then there were no personal computers, so we did more computation by calculator, and simulation was onerous, but rather fun. I changed my major, and now have a PhD in Management Science (which is yet another name commonly used for Operations Research.) I now teach Management Science at the University of Canterbury, along with the other inventor of Rogo.
Operations Research (OR) has incredibly diverse applications. As I write, the tangled mess of timetables resulting from extreme weather in Europe is being untangled. Each plane and crew member needs to get back into their correct slot as quickly as possible – and there are also the passengers to think of! Scheduling flight crews is a complex problem, with astronomically large possible combinations, which may or may not be feasible. This would be much simpler if money were no object – you could have crew and planes sitting around waiting for emergencies. But it is always a trade off between cost and convenience. Often the objective of an OR problem is to minimise cost, while obeying a multitude of constraints or rules.
The Travelling Salesperson Problem
Okay, this is all very interesting, but what does it have to do with Rogo? Well there is an area of OR which is called the Travelling Salesperson Problem (TSP). The classic scenario is that you have a travelling salesperson who has certain destinations that must be visited, and they wish to do it in the minimum amount of time or distance, and then return to their starting point. This problem should sound familiar to Christmas shoppers, sporting mums, courier drivers… The interesting thing is that it is surprisingly hard. If you have 5 destinations, and wish to visit them all, then there are 12 possible routes that take you to all of them. For those of you who are interested, the formula for this is (n-1)!/2. So for 5 destinations the number of routes is 4 x 3 x 2 x 1/2. This is fine for very few destinations, but the number of possibilities gets big REALLY fast. If you have 10 destinations, then there are over 180,000 possible routes. You can read much more about TSP at this excellent site.
Rogo is a puzzle based on the TSP
Rogo is a special case of the TSP. To start with, you are limited in the distance you can travel by the number of steps or squares you can use. Secondly you can’t go to all the destinations, so you need to choose which ones to visit. Thus it is a “subset selection” TSP. And the destinations have different reward values (the numbers in the squares), so it is a “Prize-collecting, subset selection TSP.” In order to make it more fun and easier to print, we decided to put it on a rectilinear grid. (A set of squares). This makes it easier to count how far apart the different rewards are, but also can make it a little deceptive. Things can look further apart or closer than they really are, and there are multiple routes of exactly the same length. Many of our cities are pretty close to being rectilinear grids. (Christchurch, NZ within the central Four Avenues is a neat grid, though the earthquake repairs have compromised this for a while.)
Believe it or not, the computer program that solves each Rogo puzzle that is devised, is quite a tricky little thing, written by Dr Shane Dye. We can only solve fairly small Rogos, and occasionally if I give it a difficult one, my poor laptop overheats and shuts down. Another interesting aspect is that a problem that is difficult for our computer algorithm could well be trivial for humans, and vice versa.
This was a brief introduction to the relationship between OR and Rogo. Remember to tell your friends about it. There is much more to come, both in the blog and in Rogo.