Sorry for the delay in getting results posted, the testing ran a bit longer than I expected and I did not have much time following the weekend I had set aside (last weekend I was speaking at a code camp, and this weekend I was camping/kayaking with my girlfriend).

I ran into a few problems generating the results for the submissions, mainly because none of them could pass my original tests. I try to write my tests before I receive any of the submissions because the method in which I write the tests can favor certain submissions over others. Due to this I was forced to rewrite all of my tests, my initial tests were done mainly on boards that were over size eight or larger.

There were two reasons why various submissions did not work well on larger problems. The largest was that they only used a brute force based search; the problem space grows exponentially so this quickly becomes a limiting factor. A brute force search could easily take one-hundred years to run on a board size of fifty-five.

The second limiting factor was people not capping their memory usage; this would quickly become an issue on larger boards as the number of possible positions grows exponentially. They would run out of memory and begin thrashing to disk. For extremely large puzzles you will actually be better off using disk but we will discuss this more later…

In the next ten or so analysis posts (roughly one a day) we will look more in depth at how we can help get around these two issues and allow our code to run efficiently on larger boards. It is important to note that this problem is NP Complete, whatever optimizations we add will eventually reach a failure point. As an example many used tables in varying forms to remember the positions they had seen in the past but at some point this optimization will fail due to not being able to save all previous positions any more (perhaps it’s a two GB limit for memory or a two TB limit if you are storing on disk either way you will eventually hit a board that you cannot possibly hold every previous position for). We will however continue this discussion in the analysis posts for now let’s get to the results.

Testing Methodology

To summarize the tests, all were written to operate upon leaf nodes in an n depth search. For instance a board size of five with a search depth of two would generate every possible board position on a board with 15 holes and 13 pegs. This makes for ease of generating large numbers and tends to help find algorithmic differences as it covers every possible position (and as we will see in analysis helps show one specific optimization).

As I have mentioned, the testing was a bit difficult since the engines were not able to run on the larger puzzles due to this not all submissions were run on the 7 size tests as some submissions would have taken a very long time to run on this test set (on the order of hours to weeks).

The Results

Rasmus will receive a copy of Michael Abrash's "Zen of Code Optimization" and the managed bonus of "Algorithms" by Sedgewick for coming in with the fastest entry. Wil who won second place will receive a copy of George Polya's classic work "How To Solve It".

Let me the first to congratulate our winners Rasmus Faber-Espensen  and Wil Laan for their great work on this problem.

Starting this evening we will delve deep into analysis of this problem.