Боюсь, что количество вариантов, даже если искать минимальные, будет сравнимо с 2^80 (или, хотя бы, 2^60) - замучаетесь искать. Но если очень хочется, то можно попробовать так:
- пусть у вас есть решатель (оптимизированный до предела), который по заданному набору клеток говорит ответ - 0 решений, одно или больше одного.
Ищете перебором по дереву. Сначала про первую клетку предполагаете, открыта она или нет, потом для обоих случаев - про вторую, и т.д.
Для любого набора открытых клеток в процессе перебора есть не меньше двух решений (иначе если оно одно - мы получили вариант ответа, а нуля не бывает, мы идём от известного решения).
Когда мы решаем, открывать ли следующую клетку, делаем следующее:
1) предположим, что мы не хотим её открывать. Откроем все клетки, идущие за ней, и посмотрим, сколько у нас решений. Если два - значит эту клетку нужно открыть обязательно, если нет, то можно и не открывать.
2) посмотрим, нужно ли открывать эту клетку. Для этого подставляем в неё по очереди все цифры, кроме правильной, и смотрим, есть ли решение. Если хотя бы один раз оно есть, то клетку можно и открыть. Если ни разу решения не нашлось (например, эта клетка - 9-я в ряду, в котором уже открыто 8 клеток), то открывать её не нужно, поскольку иначе набор будет не минимальным.
Таким образом, на каждом шагу мы получаем либо один, либо два варианта дальнейшего перебора. По хорошему, после того, как мы открыли очередную клетку, надо перепроверить все открытые ранее клетки методом из пункта (2), и если хотя бы одну из них открывать было не надо, значит, мы уже в не минимальном наборе, и продолжать перебор этой ветки не имеет смысла. Может быть, делать такую проверку не каждый раз (она очень дорогая), а, например, если число открытых клеток делится на 4.
