Is there an algorithm for finding elements that uniquely define Sudoku?

Question

Algorithms

I propose the following puzzle.
There is Sudoku. For example, like this:

146 572 893
829 134 576
753 896 241

287 413 965
695 728 314
431 659 782

364 985 127
972 341 658
518 267 439

I would like to solve the problem in the general case to determine the combinations of elements that will uniquely determine it.
Who has any ideas?

Answer 1

I'm afraid that the number of options, even if you look for the minimum ones, will be comparable to 2 ^ 80 (or at least 2 ^ 60) - you are tormented to look. But if you really want to, then you can try this:
- let you have a solver (optimized to the limit), which, for a given set of cells, says the answer - 0 solutions, one or more than one.
Looking for tree search. First, you assume about the first cell whether it is open or not, then for both cases - about the second, and so on.
For any set of open cells in the process of enumeration, there are at least two solutions (otherwise, if there is one, we got an answer option, and there is no zero, we go from a known solution).
When we decide whether to open the next cell, we do the following:
1) suppose we don't want to open it. Let's open all the cells following it and see how many solutions we have. If there are two, then this cell must be opened, if not, then you can not open it.
2) let's see if we need to open this cell. To do this, we substitute into it in turn all the numbers, except for the correct one, and see if there is a solution. If at least once it is, then the cell can be opened. If a solution has never been found (for example, this cell is the 9th in a row in which 8 cells have already been opened), then it is not necessary to open it, because otherwise the set will not be minimal.
Thus, at each step, we get either one or two options for further enumeration. On a good note, after we have opened the next cell, we need to double-check all previously opened cells using the method from paragraph (2), and if at least one of them did not need to be opened, then we are no longer in the minimum set, and continue to enumerate this branch is meaningless. It may be that such a check is not performed every time (it is very expensive), but, for example, if the number of open cells is divisible by 4.