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.
6
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.
5
If you build a graph like below, it’s not too difficult to solve. You still have to test a lot of combinations, but you can do a lot of pruning. I took Doc Brown’s suggestion to add 1 to C to make it a little more interesting.
Start by looking at the numbers with only one edge. These are the sets of 1. You can remove them from the graph.
Next we find sets of two. We can temporarily prune 2, 3, and 5 from consideration in this set, because they are all present in at least three cells. That leaves 1, 4, and 8.
Loop through them and follow the edges up. If you start with 1, then A and C must be in the set. Follow the edges of A and C back down, which gives you 4 and 8 as candidates for the set. In order for it to be a set of two, neither must introduce a new cell, but 4 introduces D and 8 introduces B, so we know there are no sets of two containing 1, so it can be temporarily pruned.
Backtrack and repeat with 4 and 8 and we can determine there are no sets of two. If we had found sets of two, we could remove those from the graph.
Sets of three work similarly. We just recurse one level deeper.
1
I think that yes, a ‘brute force’ O(n^2) approach gives the upper bound for the
complexity. Of course that is feasible, but not necessarily desirable. With
an iteration over the board, we are looking at O(n*3).
The OP needs to think a lot harder about the problem domain (yes, this is a late
response).
For starters, and most importantly, naked subsets and hidden subsets are not the same and cannot be searched for using the same algorithm.
Second, as for all solvers, an iterative approach means that one will examine the same section many times over. It helps to constrain this search from getting out of hand.
Examples of what to look for:
- Consider the cells that are already solved in this section! Certainly they are not interesting in terms of finding a subset.
- Consider any subsections previously identified before in the section! Again, not useful to include them in the search.
- Consider the triplets of cells forming the intersection of a row and block.
These have their own constraints, and they will eventually have some candidates that will be constrained to reside in that triplet. Again, these constrained candidates will eventually not be part of a subset, or otherwise the subset will fully reside in the triplet. In my mind resolving triplets is not to a useful part of this exercise, even though formally they are subsets. - Consider the range of sought cell locations and candidates (min,max).
- Consider other approaches (faster, and more often invoked) to find pairs of candidates, either hidden or naked. This leaves sets of 3 or 4 candidates/cells.
- It was already pointed out, the range size searched for is half the number of cells/candidates available.
As to the algorithm itself, this smells like a recursive function, not very hard, to narrow down the placement and the subset at the same time (or fail, most often).
1