|
Title:
|
The Sudoku completion problem with rectangular hole pattern is NP-complete
|
|
Author:
|
Béjar Torres, Ramón; Fernàndez Camon, César; Mateu Piñol, Carles; Valls Marsal, Magda
|
|
Notes:
|
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.
The research was partially supported by the Spanish CICYT, MICINN and MINECO Projects MTM2010-21580-C02-01, ARINF (TIN2009-14704-C03-01), and TASSAT (TIN2010-20967-C04-03). |
|
Subject(s):
|
-Latin square
-Quasigroup
-Sudoku
-NP-complete |
|
Rights:
|
(c) Elsevier, 2012
info:eu-repo/semantics/restrictedAccess |
|
Document type:
|
article
publishedVersion |
|
Published by:
|
Elsevier
|
|
Share:
|
|
