1. Paper title: Genetic Algorithm-Based Solver for Very Large Multiple Jigsaw Puzzles of Unknown Dimensions and Piece Orientation. ------------------------------------------------------------------------------- 2. Author contact details: Dror Sholomon Department of Computer Science, Bar-Ilan University, Ramat-Gan 52900, Israel dror.sholomon@gmail.com Omid E. David Department of Computer Science, Bar-Ilan University, Ramat-Gan 52900, Israel mail@omiddavid.com Nathan S. Netanyahu Department of Computer Science, Bar-Ilan University, Ramat-Gan 52900, Israel nathan@cs.biu.ac.il ------------------------------------------------------------------------------- 3. Corresponding author: Dror Sholomon dror.sholomon@gmail.com ------------------------------------------------------------------------------- 4. Paper abstract: In this paper we propose the first genetic algorithm (GA)-based solver for jigsaw puzzles of unknown puzzle dimensions and unknown piece location and orientation. Our solver uses a novel crossover technique, and sets a new state-of-the-art in terms of the puzzle sizes solved and the accuracy obtained. The results are significantly improved, even when compared to previous solvers assuming known puzzle dimensions. Moreover, the solver successfully contends with a mixed bag of multiple puzzle pieces, assembling simultaneously all puzzles. ------------------------------------------------------------------------------- 5. Relevant criteria: B, G, H ------------------------------------------------------------------------------- 6. Statement: (B) In this paper we presented, for the first time, a GA-based solver capable of handling puzzles with (1) pieces of unknown orientation, (2) unknown image dimensions, and (3) pieces originating from multiple images. Our solver sets a new state-of-the-art in terms of the accuracy achieved and the complexity of the puzzles handled. We improved significantly results obtained by previous works, making almost no assumptions. Specifically, we successfully tackled puzzles of more than twice the size that has been attempted before with the same relaxed assumptions. Finally, we showed how to assemble mixed puzzles, i.e., puzzles with pieces from multiple different images. As far as we know, the mixed puzzle solved in this paper is the largest and most complex in terms of the total number of pieces and the number of mixed images. (G) Jigsaw puzzles are a popular form of entertainment, well known to every human being from childhood. The solution of a single puzzle requires a tremendous (enjoyable) effort lasting from hours to days, weeks and even years depending on the puzzles size and complexity. A quick search on Amazon reveals a variety of puzzles with 100, 500 and 1,000 pieces. In this paper, we successfully tackle puzzle of more than 22,000 pieces. Human solvers heavily rely on the pieces shape, starting the solution process by assembling the puzzles border (pieces with a strait border or corner pieces) and later quickly rejecting false assignments due to misaligned borders. Our solver deals with square pieces, disallowing any shape based cues, preventing all human employed strategies. The puzzles solved by our solver are indisputably the hardest in terms of both puzzle size and complexity. (H) Jigsaw puzzle assembly championships were held at the past and are still held to this day by multiple organizations and in numerous venues. No single, normalized rating system exist, nevertheless one might be observed through the various reports. The winner of the US National Jigsaw Puzzle Championships in 1984 successfully assembled a 500 piece puzzle in 54:10 minutes. Two years later, a 1000 piece puzzle was assembled in 1:01:29 hours. In 2012, during 24-hours puzzle tournament (an event annually held in Belgium since 1987), a 500 piece puzzle was assembled in 47 minutes. Our solver handles puzzles of larger sizes in less than a minute. ------------------------------------------------------------------------------- 7. Citation: Dror Sholomon, Omid E. David and Nathan S. Netanyahu (2014): Genetic algorithm-based solver for very large multiple jigsaw puzzles of unknown dimensions and piece orientation. In Proceeding of the 16th Genetic and Evolutionary Computation Conference. ------------------------------------------------------------------------------- 8. Any prize money, if any, is to be divided equally among the co-authors. ------------------------------------------------------------------------------- 9. "Best" statement: We believe the problems solved in this paper is virtually an impossible challenge for a human. The puzzle pieces are square; each piece might appear anywhere (no detectable border pieces) and in any rotation. The original image is unknown and cannot be used as a reference. The dimensions of the original image are also unknown and we dont even guarantee that the original image is a rectangle. All of this, not with the standard 1,000 pieces, but with thousands of pieces (10,000  30,000). We successfully solve tens of such puzzles. Finally, we mix the 16,405 pieces of seven different puzzles, seven different images of different size, asking the solver to handle this bag of pieces as a single puzzle. All seven original images are fully reconstructed. ------------------------------------------------------------------------------- 10. Method used: Genetic Algorithms (GA).