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