The Sudoku completion problem with rectangular hole pattern is NP-complete
MetadataShow full item record
The sudoku completion problem is a special case of the latin square completion problem and both problems are known to be NP-complete. However, in the case of a rectangular hole pattern – i.e. each column (or row) is either full or empty of symbols – it is known that the latin square completion problem
can be solved in polynomial time. Conversely, we prove in this paper that the same rectangular hole pattern still leaves the sudoku completion problem NP-complete.
Is part ofDiscrete Mathematics, 2012, vol. 312, núm. 22, p. 3306-3315
Showing items related by title, author, creator and subject.
Ansótegui Gil, Carlos José; Béjar Torres, Ramón; Fernàndez Camon, César; Gomes, Carla; Mateu Piñol, Carles (Springer, 2011)Sudoku problems are some of the most known and enjoyed pastimes, with a never diminishing popularity, but, for the last few years those problems have gone from an entertainment to an interesting research area, a twofold ...
Béjar Torres, Ramón; Domshlak, Carmel; Fernàndez Camon, César; Gomes, Carla; Krishnamachari, Bhaskar; Selman, Bart; Valls Marsal, Magda (Elsevier, 2005)We introduce SensorDCSP, a naturally distributed benchmark based on a real-world application that arises in the context of networked distributed systems. In order to study the performance of Distributed CSP (DisCSP) ...
Ansótegui Gil, Carlos José; Béjar Torres, Ramón; Fernàndez Camon, César; Mateu Piñol, Carles (Association for the Advancement of Artificial Intelligence, 2007)Tractable cases of the binary CSP are mainly divided in two classes: constraint language restrictions and constraint graph restrictions. To better understand and identify the hardest binary CSPs, in this work we propose ...