We were wondering about puzzles with two completions.

Call a sudoku puzzle with exactly two completions a pseudo-puzzle, or pseudo for short.

We all think that a 16 clue sudoku does not exist.

The next best thing is a 16 clue pseudo, and what is interesting is that these do exist.

As far as I know, there is only one example known of a 16 clue pseudo, found by Gordon.

5.2...4.....71...3..............46...7.2......1.......6....2.......3..1.4........

So 16 clue pseudos could be much rarer than 17s (although we haven't been looking very hard for them).

The two completions of this pseudo are

562389471849716253137425896358194627974263185216857349691542738725638914483971562

562398471948716253137425986359184627874263195216957348681542739725639814493871562

and the set of cells where they differ is (by definition) an unavoidable set.

In this case the unavoidable set consists of all cells containing 8 and 9.

Either one of these grids is the SF grid.

We were wondering about an exhaustive search of a grid for a pseudo, and the connection to unavoidable sets.

Here is one way to proceed, but there may be better ways.

Recall the method checker uses to search a grid exhaustively for an n clue puzzle.

(The key point is that a puzzle with one completion will have to intersect all unavoidable sets.)

1. Find a decent collection C of unavoidable sets.

2. Enumerate all hitting sets (sets of size n that intersect all unavoidables in C).

3. Run a solver on each hitting set to see if there is a unique solution.

For a pseudo-puzzle, it is no longer true that there has to be one clue in each unavoidable.

However, any pseudo with n clues will arise from removing a clue from a hitting set with n+1 clues (*proof below).

Therefore, to enumerate all candidate pseudos with 16 clues, we need to enumerate all hitting sets with 17 clues and remove one clue in all possible ways.

This is not terribly efficient. Is there a better way?

[*Proof: let G be a completed grid and let X be the set of clues in a pseudo-puzzle in G. Say X has n clues. Let U be any unavoidable set in G that does not intersect X. Then removing U from G leaves a pseudo-puzzle with 2 solutions, the 2 solutions of X. So the 2 solutions of X differ only in cells that are in U. This is true for any U that does not intersect X, so the 2 solutions of X differ only in cells that are in all such U's. Choose a cell in the intersection of all such U's, add it to X, and we have a hitting set with n+1 clues.]