Revisions to Algorithms for Fixing Sudokus

provided a generalization of Sudoku, th which the question shall refer

Source Link

edited Mar 17, 2018 at 14:48

13.2k
4
34
76

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](https://en.wikipedia.org/wiki/Generalized_game)

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?

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](https://en.wikipedia.org/wiki/Generalized_game)