Puzzle Solving Using Diffusion Models

Abstract

Spatial puzzle solving refers to the process of arranging or assembling elements within a spatial context to form a coherent and complete structure. This work aims to introduce an architecture that learns to solve spatial puzzles using a denoising diffusion model formulation. The proposed system takes a set of specially crafted puzzles, where each piece is represented as a polygon curve, and then aligns the pieces by estimating their 2D correct position. What sets our work apart from other approaches to puzzle solving using diffusion models is our unique utilization of 2D coordinates as the sole feature in our architecture. Central to our training phase approach is the utilization of a forward strategy of the diffusion process, wherein we deliberately introduce noise into the positions of the puzzle elements. This intentional perturbation effectively transforms the elements from their initial fixed positions to randomized locations within a continuous spatial domain by cor- rupting training data through the successive addition of Gaussian noise. Following the training phase, our architecture is trained to reverse the perturbation process, aiming to restore the puzzle elements to their original positions. Subsequently, we utilize the trained architecture during the denoising phase of the diffusion process on new data, with the goal of resolving a given puzzle. We tested our approach on a synthetic dataset.