Uncovering Exact Cover Encodings

Exact cover encoding (XCC) is a relatively young addition to the domain of NP-complete problem solving. With a simple, yet, efficient solving algorithm (algorithm X) and vast collection of translated example problems, its main bottleneck is a lack of formalized fundamentals for encoding techniques. This thesis explores the schematics of exact cover encoding and formalizes its fundamental principles. Encoding methods for diverse problem types, including tiling, graph structures, logical formulas, and task scheduling are elaborated. The primary objective is to establish a robust foundation for the application of XCC within the realm of generalized NP-complete problem-solving.