Leveraging Cellular Automata for Strip-Cut Document Reconstruction: A Path Travelling Salesman Problem Formulation

Abstract

Reconstructing shredded documents is a long-standing problem in information security, forensics, and archival recovery. This work tackles the Reconstruction of Shredded Documents Problem (RoSDP) by formulating it as a path Travelling Salesman Problem (TSP) and solving it using Cellular Automata (CA). The proposed method is framed as an intelligent control system, where the CA operates as a decision-making engine that determines optimal sequential actions for strip arrangement—similar to automated control strategies employed in robotics. The pipeline includes dataset construction, edge-based dissimilarity computation, an order-respecting 2D coordinate mapping that overcomes non-metric multidimensional scaling (NMDS) failures, CA-driven search to recover the left-to-right shred order, and deterministic page reassembly. Evaluated on 120 pages stratified by content density and shredded into 20, 25, and 30 strips, the method delivers a mean page-level reconstruction accuracy of 70.74%, achieves perfect 100% recovery on many pages, and runs in approximately 30–55 seconds per page on a single CPU. Analysis shows errors stem primarily from the boundary dissimilarity cost rather than the CA mechanism itself. Compared with a closely related optimization-based baseline, the proposed approach yields higher overall accuracy. These results position CA as a practical, reproducible, and competitive intelligent-control framework for strip-cut reconstruction and motivate future improvements to the cost function and extensions to cross-cut and hand-torn documents.