Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.disc.2012.07.022 | Discrete Mathematics |
Keywords | Field | DocType |
Latin square,Quasigroup,Sudoku,NP-complete | Discrete mathematics,NP-complete,Combinatorics,Mathematics of Sudoku,Latin square,Time complexity,Quasigroup,Mathematics,Special case | Journal |
Volume | Issue | ISSN |
312 | 22 | 0012-365X |
Citations | PageRank | References |
2 | 0.43 | 11 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ramón Béjar | 1 | 305 | 36.72 |
| Cèsar Fernández | 2 | 157 | 19.19 |
| Carles Mateu | 3 | 79 | 14.22 |
| Magda Valls | 4 | 67 | 8.68 |