Есть ли алгоритм поиска элементов, однозначно определяющих судоку?

Предлагаю следующую головоломку.

Имеется судоку. Например, такая:
146 572 893
829 134 576
753 896 241

287 413 965
695 728 314
431 659 782

364 985 127
972 341 658
518 267 439


Хочется решить задачу в общем случае для определения комбинаций элементов, которые будут её определять однозначно.

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

Таким образом, на каждом шагу мы получаем либо один, либо два варианта дальнейшего перебора. По хорошему, после того, как мы открыли очередную клетку, надо перепроверить все открытые ранее клетки методом из пункта (2), и если хотя бы одну из них открывать было не надо, значит, мы уже в не минимальном наборе, и продолжать перебор этой ветки не имеет смысла. Может быть, делать такую проверку не каждый раз (она очень дорогая), а, например, если число открытых клеток делится на 4.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы