Project Abstract

For my dissertation I am creating an automatic jigsaw solver program. It functions using a genetic algorithm to “evolve” a population of poor solutions into correct ones.Jigsaw puzzle solvers are useful for more than games, having applications in archaeology (in particular the restoration of broken artifacts), in shredded document recovery and in speech descrambling. In particular I am using a genetic algorithm because few jigsaw puzzle solvers exist which function this way.The main aim of my work is to successfully implement a genetic algorithmic puzzle solver. I am seeking to run extensive tests on my implementation and record its performance in varying circumstances, altering the dimensions of the jigsaw puzzle, population sizes and more.The jigsaw puzzle solver I have implemented performs relatively well, and can successfully optimise and improve a solution over multiple generations. However, there are many ways in which it could still be improved. One difficulty in using a genetic algorithm to solve a jigsaw puzzle is in creating a “crossover operator” – a method in which the program can combine two parent solutions and produce a child solution, possessing a mixture of traits from both parents. With the current crossover operator, my jigsaw puzzle solver performs poorly on puzzles with high numbers of pieces in particular.I have produced an additional example of a genetic algorithm-based jigsaw puzzle solver. My implementation and results from testing will hopefully allow further insight into the applications, benefits and drawbacks of genetic algorithms, both within the topic of puzzle solving and in other areas.

Keywords: Genetic Algorithms, Puzzle Solving, Machine Learning

 Conference Details

Session: Presentation Stream 33 at Presentation Slot 6

Location: GH022 at Wednesday 8th 13:30 – 17:00

Markers: Manlio Valenti, Pardeep Kumar

Course: MSci Computer Science FI, Masters 4th Year

Future Plans: I have a job lined-up