This study introduces a novel approach to the puzzle assembly problem, leveraging textural features and geometric constraints. The texture in regions extending beyond the boundaries of puzzle pieces is estimated using inpainting and texture synthesis techniques. Feature descriptors are extracted from both the original and the synthesized images. An affinity metric is defined to quantify the correspondence between puzzle pieces, and the assembly process is formulated as an optimization problem aimed at maximizing the overall affinity score. To accelerate the alignment procedure, an image registration technique based on the Fast Fourier Transform (FFT) is employed. Experiments were conducted using different image features to study the impact of their use on assembly quality. Experimental results are presented on real and artificial data sets. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2026.