Какие есть варианты проверить, что у судоку только одно решение?

Question

[mk11]

Пишу судоку. Какие есть варианты проверить, что у судоку только одно решение? Самый простой вариант посчитать количество возможных решений. Может быть существуют какие-то другие, менее затратные и более простые, варианты?

Comments

[Сергей Соколов]

тут пишут, что решение всегда единственное, задача NP-полная, и минимум требуется 17 заранее открытых позиций.

Изначально раскрытые поля должны быть таковыми, что решение единственно.

[mk11]

Сергей Соколов, я знаю, что решение единственное, генерирую полное поле. Потом я хочу скрыть некоторые числа сохраняя это условие. Я правильно понял, что надо оставить минимум 17 совершенно любых чисел видимыми для сохранения условия единственного решения? И что значит "существует разрешимая головоломка с не более чем 21 подсказкой для каждой решаемой сетки"?

[Сергей Соколов]

mk11, пока не разбирался, жду умных ответов: самому интересно! : )

[shurshur]

mk11, нет, вполне очевидно, что просто оставить 17 произвольных чисел недостаточно. Например, если оставить 9 чисел в 1 строке и 8 во второй, то судоку будет иметь много решений, хоть в нём и будет 17 чисел.

Суть ограничения в 17 чисел состоит в том, что вообще никакое судоку с раскрытием меньшего количества чисел не будет иметь единственного решения.

[mk11]

shurshur, я скачал приложение судоку. Погенерировал несколько раз самые сложные, я не вижу там какого-то конкретного алгоритма, думал что или в каждом поле 3х3 или в каждой строке/столбце должно быть минимум одно число, нет. Бывают пустые 3х3 поля и пустые строки/столбцы.

[shurshur]

mk11, я привёл наивный алгоритм. Возможно, уже придуманы алгоритмы, которые позволяют оптимизировать процесс. Плюс во многих есть режимы от лёгкого до сложного, скорее всего, это определяется количеством чисел, которые удаляются при подготовке.

В одной реализации судоку я заметил, что там часто бывает тройка одних и тех же чисел в одной строке, только в вертикальном столбце квадратов 3x3 эта строка имеет разный порядок. Но так было не всегда, но даже в иных случаях часто это выражалось в том, что одно из чисел тройки просто перекочёвывало в другую строчку в каком-то из квадратов. Вероятно, это был побочный дефект использованного автором алгоритма, который в погоне за простотой и скоростью обеспечивает не совсем случайное распределение цифр.

[Akina]

Сергей Соколов,

тут пишут, что решение всегда единственное

Вы неверно понимаете. Судоку является "правильным", если оно имеет единственное решение. Однако ничто, кроме практической проверки на единственность решения, не гарантирует его единственности - даже минимальное судоку может иметь более одного решения и не быть правильным.

Самый простой вариант посчитать количество возможных решений. Может быть существуют какие-то другие, менее затратные и более простые, варианты?

Это не самый простой, а единственный вариант. Если и существуют способы получить количество решений без собственно решения - мысль человеческая этих способов пока не придумала.
Решение само по себе - ничуть не затратно. К тому же емнип существует доказательство, что любое судоку может быть решено логически без привлечения перебора.

На всякий случай. Вот тут: sudopedia.enjoysudoku.com/Solving_Technique.html описаны практически все известные на текущий момент алгоритмы поиска кандидата при решении судоку.

[Adamos]

Akina, тут есть еще один практический нюанс: головоломки, для решения которых компьютеру придется запускать перебор, просто никому на хрен не нужны, поскольку человек с этим не справится, а головоломка - это таки для человека, а не какая-то математическая абстракция.
Поэтому "правильность" головоломок обычно дополнительно ограничена человеко-решаемостью.
А то и вовсе - обывателе-решаемостью, без слишком сложных техник ;)

[Akina]

Судоку является "правильным", если оно имеет единственное решение. Однако ничто, кроме практической проверки на единственность решения, не гарантирует его единственности - даже минимальное судоку может иметь более одного решения и не быть правильным.

Более того - некоторые методы решения основаны именно на постулате единственности решения для решаемого судоку.

[Akina]

Adamos,

головоломки, для решения которых компьютеру придется запускать перебор, просто никому на хрен не нужны, поскольку человек с этим не справится

Позвольте не согласиться.
Как раз судоку - яркий пример того, что перебор может служить основой решения. Наиболее сложные методы поиска кандидатов при решении судоку настолько лихо заверчены, что применение их человеком мне лично представляется крайне маловероятным. И вот как раз человек запросто решает подобные позиции вульгарным перебором (впрочем, в большинстве случаев весь перебор представляет из себя выбор из двух возможных вариантов - с последующим до-решением на основании логики до решения или, наоборот, до тупика).
А типичный пример нужных задач, которые перебором решает компьютер - это, скажем, шахматы. Не говорю пока об игре и даже о решении этюдов - решение шахматных задач, компьютер всегда решает их перебором.

[Adamos]

Akina, согласен с уточнением: перебор может использоваться компьютером - для эмуляции человеческих методов решения, напрямую компьютеру недоступных. Либо для реализации "человеческого" перебора, ограниченного объемом данных, которые нужно удерживать в быстрой памяти.

Answer 1

[Adamos]

Вариант проверить, что у головоломки есть только одно решение, только один.
Написать решатель такой головоломки и скормить ему задание. Если он успешно ее решает - результат единственный. Если упирается в "вилки" - значит, головоломка составлена неправильно.
Все подобные головоломки составляются на компьютере именно таким образом:
- заполняется готовое поле решения
- убирается по одной цифре, после чего запускается решатель
- если он не смог решить головоломку, цифра возвращается на место
- цикл повторяется до перебора всех цифр (или не всех, если нужно составить головоломку меньшего уровня сложности).
Например, в наборе головоломок от Simon Tatham судоку тоже есть (под названием Solo), и составляется она именно так.

Comments

[mk11]

А не увеличится ли время генерации при проверке после удаления каждой цифры?

[Adamos]

mk11, по сравнению с чем? Решение судоку совершенно тривиально для компьютера, проверка занимает миллисекунды, и даже 81 такая проверка занимает меньше секунды - судоку, с точки зрения человека-наблюдателя, составляется "моментально".

Answer 2

[Ян Соколов]

Делаешь прямоугольный массив, загоняешь исходные данные, затем рекурсивно пробегаешься по всем "заполненным" клеткам и отмечаешь по строке, столбцу и квадрату 3*3, каке решения могут быть в каждой ячейке. Таким образом, если возможное решение в данной ячейке только 1, то это оно и есть. Разные варианты могут появляться при разных обходах заполненных ячеек. Условие выхода из рекурсии - все ячейки заполнены. Результаты сравниваешь, если есть хотя бы 2 различных, вылетаешь с результатом false