Since a puzzle solver, for the puzzle reconstruction problem, can be applied to many other real world problems, various studies have focused on improving the end result of the puzzle solvers they proposed for several years. In spite of these efforts, the puzzle reconstruction problem, however, has never fully solved by using a search algorithm with a limited computation time. In this paper, and effective search algorithm is presented for the puzzle reconstruction problem. The proposed algorithm uses ant colony optimization to guide the search directions toward the global optimal solution, the color information to measure the similarity between pairs of puzzles, and an effective reconstruction strategy to improve the end result. To evaluate the performance of the proposed algorithm, we compare it with several state-of-the-art puzzle reconstruction algorithms. The simulations results show that the proposed algorithm out performs all the state-of-the-art algorithm we compared in this paper.