I have found a 2-clue FP puzzle for a SudokuX.

- Code: Select all
` +-------+-------+-------+`

| . . . | . . 9 | . . . |

| . . . | . . . | . . . |

| . . . | . . . | . . . |

+-------+-------+-------+

| . . . | . . . | . . . |

| . . . | . . . | 6 . . |

| . . . | . . . | . . . |

+-------+-------+-------+

| . . . | . . . | . . . |

| . . . | . . . | . . . |

| . . . | . . . | . . . |

+-------+-------+-------+

- Code: Select all
` +-------+-------+-------+`

| 3 2 1 | 4 6 9 | 8 7 5 |

| 8 7 5 | 1 2 3 | 9 6 4 |

| 9 6 4 | 5 7 8 | 3 2 1 |

+-------+-------+-------+

| 6 4 8 | 9 5 7 | 2 1 3 |

| 7 5 9 | 3 1 2 | 6 4 8 |

| 2 1 3 | 8 4 6 | 7 5 9 |

+-------+-------+-------+

| 1 3 2 | 7 8 4 | 5 9 6 |

| 5 9 6 | 2 3 1 | 4 8 7 |

| 4 8 7 | 6 9 5 | 1 3 2 |

+-------+-------+-------+

It is perhaps of interest to describe the search process, as it involves a little Graph Theory, and I happen to like that very much!

As I mentioned above, the 18-FP truth-table seemed the obvious place to start looking. This is the maximum number of FP's that can be used, and so gives the maximum potential for restricting the applicable grid solution space.

The first question to answer was, how many TT18's are there, or more importantly, how many ED flavours are there? Consider this example:

- Code: Select all
` . . . . . X X X X`

. . . . X . X X X

. . . X . . X X X

. . X . X X . . X

. X . X . X . X .

X . . X X . X . .

X X X . . X . . .

X X X . X . . . .

X X X X . . . . .

Now if we invert the dots and the X's (excluding the main diagonal), then this becomes an adjacency table (as against a forbidden pair table), and one that has the same properties. There are still 4 X's in each row and column. Adjacency tables are just graphs in another form. And since each vertex has 4 edges joining it to other vertices, our TT is a 9V 4-regular graph, and we know quite a bit about these guys.

There are only 16 ED graphs in this category, and so there are just 16 flavours of TT18's. In my list the TT above is #5.

*Adjacency Graph AG5*
- 09_4_3-5.gif (2.68 KiB) Viewed 50 times

Now, it turns out that only 3 of these 16 adjacency graphs can be used, since the rest do not correspond to any Sudoku grids. 9 of them do not allow the completion of a 3x3 box, and 4 more are found to be incompletable, that is, there are boxes but they can't be assembled to form a valid grid. The only valid ones are the final 3 in my list, ie AG14, AG15, and AG16. (Note: validity here refers to satisfying the TT, not just getting a valid Sudoku grid).

*Valid AG's*
- AG14-15-16.png (18.69 KiB) Viewed 50 times

It is interesting to note how "regular" these are compared to AG5, and there is probably something more to be learned there. But now we have just 3 TT18's as candidates, and so can use the brute-force clue-pattern method to search for low-clue puzzles for each case.

AG14 disappoints, it produces no 3-clue puzzles, but both AG15 and AG16 produce 3-clue puzzles in standard Sudoku form. Since we already know that the NC case has no 3-clue puzzles, this is progress! We find millions of 3-clue puzzles for AG15 and AG16, but alas, no 2-clue puzzles. So we look to add constraints, and by starting with SudokuX, are rewarded with an abundance of 2-clue puzzles (53,088).

None for AG16 though. AG15 is the only TT18 which yields 2-clue puzzles.

The next step is to consider other TT's with less than 18 FP's. Can they produce 2-clue puzzles?

And does the 1-clue puzzle exist in this FP form?

Watch this space