We propose a novel mathematical framework to address the problem of automatically solving large jigsaw puzzles. The latter problem assumes a large image, which is cut into equal square pieces that are arbitrarily rotated and shuffled and asks to recover the original image given the rotated and shuffled pieces. We propose a method for recovering the unknown rotations of the puzzle pieces by using the Graph Connection Laplacian associated with the puzzle. The Graph Connection Laplacian is also used to form a metric between puzzle pieces and this metric is more accurate than the common metric used. It thus results in better recovery of the unknown locations of the puzzle pieces. Numerical experiments demonstrate the competitive performance of the proposed method.