3
$\begingroup$

Suppose someone got stuck solving a Sudoku and asks you to figure out, what went wrong. Unfortunately that person only sends you a copy of the instance, where you neither see which of the numbers constituted to the initial set of numbers, nor do you get any information about the order in which the other numbers have been entered.
Note that some of the fields may not have entries because the Sudoku was not finished when the contradiction to the filling rules was realized.

Question:
what is the complexity of detecting the minimal set of entries, whose removal would restore the solvability of the Sudoku instance?


Edit:
as a clarification in response to Brendan McKay's comment I would ask for the complexity of fixing Sudokus generalized to boards of size $n^2\times n^2$, where each of $n^2$ symbols must appear exactly once in each row, in each column and in each of the $n\times n$-sized subsquares whose disjoint union covers the board's cells; this kind of generalization is depicted in the wikipedia article on generalized games

Improve this question
$\endgroup$
7
  • 4
    $\begingroup$ It takes constant time, because there are only finitely many possibilities. Perhaps you meant to consider some generalization of Sudoku to arbitrarily large boards, but there is more than one way to generalise and you need to specify which you want. $\endgroup$
    – Brendan McKay
    Commented Mar 17, 2018 at 10:07
  • 1
    $\begingroup$ @BrendanMcKay good point; I simply overlooked that. I now edited the question, so that possible answers will be more interesting. $\endgroup$
    – Manfred Weis
    Commented Mar 17, 2018 at 14:51
  • $\begingroup$ Is it known whether solving a Sudoku is in NP? If so, then this problem is likely of the same complexity. I imagine this is equivalent to finding a maximal set of consistent constraints in a CSP system. Gerhard "Coffee: Foundational To My Consistency" Paseman, 2018.03.17. $\endgroup$
    – Gerhard Paseman
    Commented Mar 17, 2018 at 15:03
  • $\begingroup$ In general solving n x n Sudoku is NP-complete. If you are promised there's a unique solution (as is often the case with actual Sudoku puzzles) it is in UP, but still hard for NP under randomized poly-time reductions. $\endgroup$
    – Joshua Grochow
    Commented Mar 17, 2018 at 15:11
  • $\begingroup$ @JoshuaGrochow but my question is not aimed at actually solving a Sudoku, but rather at removing entries of a partially filled Sudoku to restore solvability; is that problem also of the same complexity? $\endgroup$
    – Manfred Weis
    Commented Mar 17, 2018 at 15:18

1 Answer 1

Reset to default
1
$\begingroup$

An algorithm that finds a minimal set of entries whose removal restores the solvability of a Sudoku puzzle has essentially the same complexity as one that solves the puzzle. Just repeat trying each possible single entry in turn, keep those for which the algorithm returns the empty set.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .