In the 4x4 grid below, 32 consecutive two digit numbers (45 to 76) have been packed in it.

1 3 5 9
2 5 4 8
0 7 6 2
1 6 3 9

*****
The challenge: Pack as many consecutive 3 digit numbers as possible into a 9x9 grid. The numbers may be read from any direction. No leading zeros.

Firstly to Brian - I wrote the program in Delphi 6, if you want the source code I'll happily email it to you :)

And now for everyone else that's interested...

I used a genetic algorithm to find my solutions. I start with a population of 500 random "genes". Each gene is a string of 81 digits (enough to fill the 9x9 grid). I test the genes and find the longest run of consecutive numbers in each, and store this as the "fitness" score for each gene. When all the tests are done, a new genepool is generated. For each new gene, two genes are selected using roulette wheel sampling and "bred" by mixing them together at random. There is a probability of about 0.001 that a gene will mutate and contain a digit that is different from both parents. The old genepool is replaced with the new genepool and the process begins again.

So basically the algorithm is:

Test, breed, mutate, repeat.

...But this is the same for pretty much any GA.

Sorry for the poor explanation - I'm not very good at explaining things like that :P

Peace,
Rawlyn.

Posted by Rawlyn on 2004-02-04 18:48:41