2

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
  • 1
    Erm that is not a good example of a hidden set, because with 5 empty cells you should have only 5 numbers.
    – durron597
    Jan 23 '15 at 15:09
  • I did not list all the cells and I made up the numbers. One can assume that any other cells not shown here do not contain 1, 2 or 8. For the purpose of the example, they work fine (1,2, and 8 are only present in cells A B and C) And the constraint you mentioned only applies to sudoku. Granted, this will be used in a sudoku solver, but I'm asking about the general problem. The fact that in sudoku there are only N distinct values in N empty cells does not affect this in any way. The hidden set criteria still hold for the above set of "cells" Jan 23 '15 at 15:19
  • 1
    Have you tried a brute force approach? It will likely be exponential, O(2^n), but thankfully the input size is small so it might not matter.
    – user22815
    Jan 23 '15 at 15:58
  • Yes I have and it works. Basically I enumerated all the possible subsets of cells from the original set, and for each subset of size N I checked whether they contain N distinct values. If true, I then checked whether any of those values are in cells outside of the current subset. If no other cells are found containing them then I have found a match. However this seems horribly inefficient and I'd like to know if there is some algorithm that would help with this kind of thing. Jan 23 '15 at 16:05
  • 1
    In the given example, the obvious optimization would be to find the "hidden set {1}" first, so A must contain 1 and will be removed from the set of free cells. This leaves you with {2,8} as a valid hidden set. But I guess that is not what you are looking for. Maybe adding 1 to C will generate a better example?
    – Doc Brown
    Jan 23 '15 at 17:51
7

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
  • Thinking one step further: looking for hidden sets of size 1,2,3,4 will be enough, when also searching for naked sets of size 1,2,3,4. That's because each hidden set of size n is complementary to a naked set of size 9-n. This answer illustrates that for cases n=8 and n=7, but it can be extended to n=6 and n=5.
    – Doc Brown
    Jan 24 '15 at 22:25
  • @DocBrown While I'm not seeing a rebuttal off the top of my head it must exist--otherwise there would be no reason to look for hidden sets as they would always be revealed by finding the naked sets. Jan 25 '15 at 2:21
  • Technically, there is no reason. Practically, looking for naked sets of size 5...9 is more work than looking for the correspondig hidden set of size 1..4, and vice versa. That's the reason why it may be better to look for both. See, for example, zitowolf.net/sudoku/strategy.html#nakedandhidden
    – Doc Brown
    Jan 25 '15 at 7:04
  • I implemented something like this. I generated a set of cells for each candidate with each set containing just the cells containing that candidate from the unit (row/col/square). Then I enumerated all combinations of length 1 up to N-1 (N being the number of unsolved cells in the unit) of candidates present in the unit and checked whether the union of all the candidates' cell set (precalculated previously, as described) contained the same number of cells as the number of candidates in the combination. This method finds both hidden and naked sets (singles, pairs, triples, quads etc) Jan 26 '15 at 12:36
  • While the brute forcing is longer, I also don't have separate checks for naked/hidden singles, pairs and triplets. With the added benefit that the method finds even quads and bigger sets. Because, as someone mentioned, every hidden set has a corresponding naked set this method works for both (it'll find a bigger hidden set instead of a smaller naked set, which doesn't matter as I'm brute forcing anyway) Jan 26 '15 at 12:39
2

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.

graph

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
  • An old answer and a very good algorithm, but it needs a little correction. "...We can temporarily prune 2, 3, and 5 from consideration in this set, because they are all present in at least three cells." that is not correct. An hidden triple can have the same number in 3 cells. Nonetheless it deserve a + Now would be to see if it can be generalised, without loosing its 'elegance', to find any random set with an unknown size. Aug 20 '21 at 3:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.