I am writing a solver for the game sudoku. I am trying to implement the hidden set check in it and I can't figure out a way to do it well.
I need to find out if there is a set of cells of size N in which a number of N candidates appear, where those N candidates are not present in any of the cells outside the set. For example suppose I have the following cells containing possible values:
A={1,2,5} B={2,3,8} C={2,3,4,5,8} D={3,4,5} E={5,6,7}
The hidden set in this case is {1,2,8} (and N in this case is 3)
{1} appears in cell A only
{2} appears in cells B and C only
{8} appears in cells B and C only
Not all three cells contain all three numbers, but together they only appear in three cells.
As a counterexample, the set {2,8} would not be valid, because even though cell B contains both and cell C does as well, the number 2 is also included in cell A, which means I have two values covered by three cells, and as I said in the beginning, I need the number of cells to be equal to the number of values in the set.
It should be mentioned that I will not know which values to test for. The only input would be the list of cells, and the algorithm needs to find any such sets that may exist in it for N = 1 to the number of cells – 1.
Best Answer
Edit: I cut it down too much here. I'll leave the original intact and then point out the flaw.
Before rejecting the brute force solution look at the problem size.
Sudoku has only 9 items in a row. Thus the naive brute force is only 512 combinations to check.
In practice there can't be a hidden set of 9 in 9 entries, this means the largest set you need to check is 8--for a maximum of 256 combinations.
However, suppose you have a hidden set of 8 in 9 entries--what does that say about the 9th value? It can only have one prospect, thus you would have already picked it and you're finding a hidden set of 8 in 8--but again that can't occur.
Thus you're down to 7, for a total of 128 cases.
However, suppose you have that? What are the values of the last two entries? If any entry had only one prospect you would have already picked it. That leaves only one possible case--both of the remaining two cells have exactly two prospects. Two cells, two prospects, you have a set--you should have found that before you were looking for hidden sets.
Now we are down to 6, for a total of 64 cases.
Brute forcing 64 cases? Horrifying!
Update: My logic as to the maximum set size you can find is correct but the number of cases is higher than I was figuring. It's not 6 out of 6, it's 6 out of 9. Therefore there are 465 combinations to check.
In practice, however, you rarely find an entire row with no known values and thus you'll rarely have to do anything like all the cases.
The conclusion is the same: Brute force is quite reasonable.