Christian Skaarup Hansen Abstract This report deals with the problematics of developing a computer programme which is able to solve geometric jigsaw puzzles correctly. The idea is that the programme can be further upgraded in such a way that it could work as a support tool in the future in industries where the demand of solving naturally generated puzzles is requested. There are several ways to make such a programme and it is not easy to predict the way leading to the best result before the different methods have been tested. This may complicate the development of the mentioned programme and the progress has ended up in being rather drawn-out relative to the efficiency of the programme. After having developed an algorithm its functionality is tested. In view of the test results a series of optimizations of the implemented methods are carried out. The methods are tested again to see whether the rate of searching has increased in the optimized version. The structure of the algorithm has similarities with many of the different existing solving algorithms.The most efficient approach developed to solve puzzles is the Cocktail Method combined with backtracking. Both methods exist in two versions: One where the searching process has been optimized and one where it has not. Tests have shown that the optimized version of backtracking is the one working fastest whilst for the Cocktail Method the non-optimized version is faster than the optimized version. It is not possible to generate a combined version of the algorithm in such a manner that both the Cocktail Method and the backtracking is working optimally. Firstly the methods are tested on a simple jigsaw puzzle where each side of a piece only fits together with one other side of another piece. Subsequently there are runned tests on small jigsaw puzzles containing composite sides. Furthermore tests are carried out where the pieces are rotated in such a way that each piece has to be rotated before the actual position of the piece could be determined. Finally tests are runned on a jigsaw puzzle consisting of 23 pieces in order to test whether the algorithm is able to handle puzzles with a larger number of pieces. Type Master's thesis [Academic thesis] Year 2007 Publisher Informatics and Mathematical Modelling, Technical University of Denmark, DTU Address Richard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby Series IMM-Thesis-2007-56 Note Supervised by Prof. Jens Clausen, IMM, DTU. Electronic version(s) [pdf] BibTeX data [bibtex] IMM Group(s) Operations Research