David Finch (dtfinch a t charter dot n e t)'s solution:

After posting my first heuristic solution, I was concerned about the seemingly excessive fuel usage, and sought to reduce it. While tweaking the program, I noticed a bug in the feel() function that caused it to spend half its time looping through the same moves over and over, because there is no down thruster. That reduced it to a little over 4 seconds, and some minor optimizations reduced it further to 3.5 seconds.

http://mytsoftware.com/misc/mars.c

Steps taken to compile and run:
gcc -O9 -funroll-loops -fomit-frame-pointer -march=pentium3 mars.c
time ./a.out big2.txt

Running Ubuntu Linux
gcc 3.3.5
2.4ghz Celeron. 512mb ram.

I had thought about writing a heuristic solver since the large maps were announced, but didn't set aside the time until this weekend. It took much more time to write than the previous solver, due to it being  like 3 programs in one (generate cost maps, approximate traveling salesman solution, and trace solution). Early development versions used SDL to provide debugging output, which I later removed as it became unnecessary because it could hinder others from testing the code.

Originally, the cost map generator was a full path finder, striped down to only store visited bits and the least cost found at each x,y position. One cost map must be generated per target, which allows the trace to quickly follow an approximate path from any point to that target. And as each target is hit from every other target, the cost is stored for use by the salesman solver. It took hours to generate the high resolution cost maps, so I decided to tear it out and write a faster, more approximate cost map generator. It worked at the original text resolution and didn't worry about velocity. From the generated low resolution cost maps, linear interpolation is used to estimate costs at the x10 resolution.

With the salesman solver, I figured that it was most important to know the end result of any choice along the way, rather than only looking so many moves ahead. So it'll follow a reasonable path all the way to the end to get an estimate of the cost of each decision. With a bit of recursion, and I turned that strategy into a pretty fast solver that seems to give pretty good paths.

For the tracer, I had to try several strageties before I found one that gave good results in a reasonable amount of time. Getting a good solution was difficult because small changes would sometimes have unpredictable results. In some instances, it would get stuck in a corner and I'd have to figure out why it worked the previous dozen tries with only slight tweaks each time. Often, it was the result of some optimization that seemed to be safe, and worked almost every time. Hopefully, I've solved most of those problems rather than arrive at a solution that only works on these maps. After trying several strategies, I finally settled on using a function that tried a limited set of paths to decide the value of a state rather than relying on a full search of all possible paths going so many turns ahead. This sped it up a lot while giving comparable results on all but the most random of maps. A lot of debugging, tweaking, and reworking went into the tracer, and it's pretty ugly as a result.

It was a pretty fun challenge. I'm feeling a little embarrassed that others will be trying to make sende of my code. I don't think I've written code this bad since high school. Prior to this, nearly all of my programming contest experience has been with a game called Robot Battle, which I played for about 6 years. This is definitely the biggest problem I've tried to solve. I'm 22 years old and a recent graduate of Southern Oregon University.