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

Additional Metadata
Keywords Assignment problem, Assignment problems, Computational complexity, Consistency checking, Matching problem, Matching problems, NP-hardness
Persistent URL dx.doi.org/10.1016/j.orl.2010.09.001, hdl.handle.net/1765/22168
Citation
Gabor, A.F., & Woeginger, G.J.. (2010). How *not* to solve a Sudoku. Operations Research Letters, 38(6), 582–584. doi:10.1016/j.orl.2010.09.001