Last Christmas I received a puzzle from my secret Santa. Upon receiving the puzzle I wanted to solve it using a computer because it would be fun if it worked. Full details on the puzzle can be found here. In summary the puzzle requires that all rows to add up to 38 by arranging the numbers 1 to 19 on the grid.
I decided to use a Genetic Algorithm (GA) to solve this puzzle as it is suited to large discrete problems such as this. In total I spent about 8 hours coding, testing and running the program before solving the puzzle.
Let’s jump into some code, below is the pseudo python code for my GA. The original implementation was written in python and shall go up on my git hub account when I get the time. Due to the simple data structure used for each solution (an array) there are additional steps such as the addition then removal of the fitness, this was done to stop the fitness becoming part of the solution at any of the mutation/recombination stages.
def main(): # limit the runs as the problem is unknown and may not produce a solution MAX_RUNS = 100000 TARGET_FITNESS = 0 # init population with random solutions population =  generatePopulation() # if we can solve the eval_list then return results while solution ==  and run < MAX_RUNS: # display algorithm progress if run % 20 == 0: print " - ga run:", run, ", fittest:", fittest # check the current population to see if there is a complete solution for item_list in population: if getFitness( item_list ) == TARGET_FITNESS: solution = copy.deepcopy(item_list) break # if we have found a good enough solution then stop running as # this part of the code is quite taxing if solution == : # get fitness for each solution so they can be ranked getPopulationFitness() # rank population so the best solutions can be used # to create children rankPopulationByFitness() # remove fitness so it doesn't get included # in the create offspring (mutation/recombination) stage removePopulationFitness() # get the best solutions in the population to create # offspring with selectParents() # create offspring createOffspring() run += 1 return solution
Some definitions from the pseudo code: A solution is a combination of all elements in the set of numbers from 1 to 19. The solution space represents all possible solutions where each solution is a unique combination.
Notes on my GA:
- The fitness of a solution is evaluated by taking the sum of each row away from 38 and then adding up the modulus of all of these values. This number represents the fitness of the solution.
- A complete solution is one where all 15 rows add up to 38 and so has a fitness of 0.
- Much tweaking to the vanilla GA was performed to get a solution.
When producing this GA I started out by keeping the general population size fixed. This resulted in a population which produced a general fitness of 4 and plateaued here. The key changes to the vanilla GA were as follows:
- Keep every item in the population, this slowed the system down after a while due to the memory requirements.
- Perform restarts when the algorithm gets stuck in a local minimum. A restart would require shuffling a child at the create offspring stage.
The final result can get a good fitness of 4 in about 5 minutes and at best a complete solution in about 1 hour. In total I have found 2 solutions however there may be many more!
Finally here is one solution with every number increased by 1 in the diagram below. Note that all horizontal and diagonal rows add up to 38 if you take 1 away from each piece on the grid.
Although this algorithm does solve the puzzle I think it would be great if it was quicker. This could be done by tweaking it and understanding how the problem is worked on by the GA to produce the final solution.
December 2013 M T W T F S S « Jul 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31