Here is a word on how

CHECKER could be speeded up, in case anyone is interested and has any ideas.

Recall how checker works:

1. Find some unavoidable sets,

2. Enumerate all hitting sets of size n, i.e., enumerate all sets of n clues that intersect all the unavoidable sets found in part 1,

3. Check if any of these hitting sets uniquely determines the grid.

In step 2 some hitting sets are enumerated twice. This means that checker could be speeded up if we can eliminate this duplication, but we could not see how to do this.

--------------

Let me explain. The cells are numbered 11 to 99, ij means row i, column j.

For an example, suppose we are looking for a 16 clue puzzle.

In step 2, checker finds a max clique (a maximal set of pairwise disjoint unavoidables). Let's suppose a max clique here has 12 sets. Checker orders the 12 sets, chooses one clue from each of these 12 unavoidables, and adds 4 further clues, in all possible ways, and then sees if the result is a hitting set for all unavoidables found in step 1. If yes, go to step 3.

So checker generates all possible 16-tuples in a systematic way. It only became apparent to us later that some 16-tuples are generated twice, as follows.

Suppose that from step 1 we have unavoidable sets {12,13,42,43} and {41,42,71,72}. Suppose also that the first of these sets is not part of the max clique checker uses, but the second set is. And suppose that no other unavoidable in the max clique contains any of 12,13,42,43.

Checker will choose each of 41,42,71,72 when forming possible hitting sets, as one of the 12 clues. In that order.

(I know there are lots of other clues hanging around, but lets just stick to these cells for this example)

First, when choosing 41, each of 12, 13, 42, 43, could (and must) be chosen as one of the final 4 clues.

Second, when choosing 42, the first unavoidable is already hit, so when choosing the final 4 clues, each of 12, 13, 43, 41, 71, 72 could be chosen as one of the final 4 clues. Actually 41 is not chosen since {41,42} arose in the previous step. Anyway, the point is that in particular, {42,71} is chosen.

Third, when choosing 71, each of 12, 13, 42, 43, could (and must) be chosen as one of the final 4 clues. Again {71,42} will be chosen.

And so, the problem is that {42,71} arises twice with this method. To eliminate all such duplication might speed checker up by a considerable factor, but we cannot see how to do this in a simple way. The duplication of {41,42} is easy enough to take into account, but this type of duplication is more difficult.

We would be very grateful to receive any ideas on how to get around this.