How *not* to solve a Sudoku

Adriana F. Gabor; Gerhard J. Woeginger

doi:10.1016/j.orl.2010.09.001

How not to solve a Sudoku

Adriana F. Gabor
, Gerhard J. Woeginger

Mathematics

Eindhoven University of Technology

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

We prove the NP-hardness of a consistency checking problem that arises in certain elimination strategies for solving Sudoku-type problems.

Original language	British English
Pages (from-to)	582-584
Number of pages	3
Journal	Operations Research Letters
Volume	38
Issue number	6
DOIs	https://doi.org/10.1016/j.orl.2010.09.001
State	Published - Nov 2010

Keywords

Assignment problem
Computational complexity
Matching problem

Access to Document

10.1016/j.orl.2010.09.001

OpenUrl availability

Full text

Cite this

@article{0e3d7a5a55814fd59e93283570a539da,

title = "How *not* to solve a Sudoku",

abstract = "We prove the NP-hardness of a consistency checking problem that arises in certain elimination strategies for solving Sudoku-type problems.",

keywords = "Assignment problem, Computational complexity, Matching problem",

author = "Gabor, \{Adriana F.\} and Woeginger, \{Gerhard J.\}",

note = "Funding Information: This research has been supported by the Netherlands Organisation for Scientific Research (NWO) , grant 639.033.403 , by DIAMANT (an NWO mathematics cluster), and by BSIK grant 03018 ( BRICKS: Basic Research in Informatics for Creating the Knowledge Society ).",

year = "2010",

month = nov,

doi = "10.1016/j.orl.2010.09.001",

language = "British English",

volume = "38",

pages = "582--584",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - How *not* to solve a Sudoku

AU - Gabor, Adriana F.

AU - Woeginger, Gerhard J.

N1 - Funding Information: This research has been supported by the Netherlands Organisation for Scientific Research (NWO) , grant 639.033.403 , by DIAMANT (an NWO mathematics cluster), and by BSIK grant 03018 ( BRICKS: Basic Research in Informatics for Creating the Knowledge Society ).

PY - 2010/11

Y1 - 2010/11

N2 - We prove the NP-hardness of a consistency checking problem that arises in certain elimination strategies for solving Sudoku-type problems.

AB - We prove the NP-hardness of a consistency checking problem that arises in certain elimination strategies for solving Sudoku-type problems.

KW - Assignment problem

KW - Computational complexity

KW - Matching problem

UR - https://www.scopus.com/pages/publications/77958089000

U2 - 10.1016/j.orl.2010.09.001

DO - 10.1016/j.orl.2010.09.001

M3 - Article

AN - SCOPUS:77958089000

SN - 0167-6377

VL - 38

SP - 582

EP - 584

JO - Operations Research Letters

JF - Operations Research Letters

IS - 6

ER -