Comments 33
Есть одно существенное замечание. Что считать одним судоку? Окончательное решение или начальную задачу? Для одного и того же окончательного решения можно составить множество различных начальных задач разной сложности.
Мне кажется что для решающего эти разные задачи вообще говоря и есть разные судоку, т.е. задач судоку больше чем его решений.
Тут авторы считают количество решений, т.е. количество полностью заполненных сеток.
Я понял что считают авторы. А вот что считать судоку? Решение или задачу?
Это уже вопрос терминологии. Можно считать что угодно, но написать «Под судоку мы будем понимать...». В статье авторы как судоку определяют начальную задачу, а конечную — как решение или полностью заполненную сетку. Каюсь, кое-где я заменяю одно другим, но из контекста ясно, о чем идет речь, просто мне в голову не приходило явно разделять эти понятия. Могу дополнительно все прописать более четко, если режет глаз.
Подсчитать число задач, конечно, намного сложней, но сама эта задача более интересная. Правда, нужно уметь отбрасывать всякие вырожденные случаи (типа заполненной доски с одной неоткрытой клеткой). Надеюсь прочитать про её решение (если оно, конечно, есть).
Тут еще есть такой вопрос: какие полузаполненные сетки считать судоку — которые имеют ровно одно решение, или же просто подходят под Главное Правило. Второй вариант явно легче первого, а первый, вероятно, на сегодняшний день вообще не решаем.
Начальная задача это когда удаление еще одной клетки дает несколько решений. Таких начальных задач намного больше чем решений.
Встречал мнение, что хорошая задача судоку допускает единственное решение. В этом случае число задач и число судоку будет одинаковым, и можно их не разделять. Или вы о том, что таких задач тоже можно придумать множество?
Проблема в том, что несколько задач могут иметь одно и то же решение. Например, если мы из полной сетки удалим одно из чисел (81 способом), то получим 81 задачу на одно решение, и все эти задачи будут различны.
Судоку это логическая головоломка. Начальные задача имеет единственное решение, иначе можно нарисовать пустое поле и как говориться найди все решения ;)
Понял вас. Тогда можно зафиксировать одно решение и искать способы удаления значений в ячейках, чтобы решение задачи оставалось однозначным. И выкинуть повороты из результата. Тогда останется умножить на количество независимых решений. Или я что-то упускаю?
У разных решений можно дооткатываться до разного количества начальных задач. Впрочем, их можно разбить на классы, где в каждом классе одно и то же число различных задач (тогда можно откатываться только для одного решения из класса). Насчет этих вот классов — будет расписано во второй части перевода.
Встречал мнение, что хорошая задача судоку допускает единственное решение.
Отмечу, что знание этого можно использовать как априорную информацию при решении. Допустим, перебирая варианты, вы пришли к чему-то такому:
...
?** ?** ***
?** ?** ***
...
Где "?" — либо 1, либо 2, а "*" — неважно. Это значит, что если решения есть, то их как минимум два, и вариант можно отбросить.
Это значит, что цифру под "?" надо делать изначально открытой, чтобы не допускать двойственности решения.
Нет, вы не поняли. Описанный паттерн это не часть задачи, а часть знания, полученного игроком в процессе вывода решения. В момент создания задачи неизвестно, где именно такая ситуация возникнет.
Ну так этот момент в статье описан следующим образом:
Вот здесь описаны хорошие методы для решения.
Существует еще несколько операций, которые сокращают количество сеток для рассмотрения. Если у нас есть пара чисел {a,b} такая, что a и b находятся в одном столбце, причем a — на i-й строке, а b — на j-ой, и, ко всему прочему, есть такая же пара в другом столбце, причем для этого столбца a уже находится на j-ой строке, а b — на i-ой (т.е. эти четыре числа находятся в углах некоторого прямоугольника, и противоположные числа равны), то мы можем поменять местами числа в обеих парах и получить новую корректную полосу с тем же количеством конечных сеток.Правда там в контексте количества возможных сеток, но эти же трюки можно применять и при эвристике решения.
Вот здесь описаны хорошие методы для решения.
Предложенного мною метода там как раз и нет.
Это те же «голые пары», только в разных блоках, а не в одном.
Решение судоку из примера
395 271 486
746 835 219
821 469 573
539 748 621
278 516 934
614 392 758
962 187 345
153 624 897
487 953 162
746 835 219
821 469 573
539 748 621
278 516 934
614 392 758
962 187 345
153 624 897
487 953 162
Спасибо за статью, -2 часа на работе)
Блин. Надо поскорее дописывать свою статью, а то так скоро писать не о чем будет.
Я больше года назад начал идти по тому пути, что здесь описан, но в итоге, когда всё скатывается в реальный перебор, а не понятный и простой устный подсчёт, бросил и пошёл по другому пути (который изначально показался сложнее и менее перспективным). Подозреваю, что авторы оригинальной статьи тоже что-то про это знают и частично это и использовали при сокращении количества комбинаций для полос.
Кстати, у меня те же числа получались — 36888 и 416. Только либо я чего-то не понял, либо сам ошибаюсь, но это лишь для одного стартового набора данных (стандартный набор в терминологии перевода).
Буду ждать перевода второй части, поскольку сам первый путь до конца не осилил, может он поможет мне дописать статью :)
Я больше года назад начал идти по тому пути, что здесь описан, но в итоге, когда всё скатывается в реальный перебор, а не понятный и простой устный подсчёт, бросил и пошёл по другому пути (который изначально показался сложнее и менее перспективным). Подозреваю, что авторы оригинальной статьи тоже что-то про это знают и частично это и использовали при сокращении количества комбинаций для полос.
Кстати, у меня те же числа получались — 36888 и 416. Только либо я чего-то не понял, либо сам ошибаюсь, но это лишь для одного стартового набора данных (стандартный набор в терминологии перевода).
Буду ждать перевода второй части, поскольку сам первый путь до конца не осилил, может он поможет мне дописать статью :)
Верно, сначала мы сокращаем число полос 2612736 -> 36288 -> 416 -> 174 -> 71, а потом уже добиваем реальным перебором за 6 часов (вместо 6/71*36288, или сколько там было полос).
Вообще, используя такой же подход, что и в статье (берём стартовый набор и допустимыми манипуляциями получаем эквивалентные комбинации, которые не учитываем при дальнейшем рассмотрении, а просто умножаем на их количество), а дальше дополняем стартовый набор новыми данными и снова вычёркиваем для расширенного набора и получаем новые множители.
Я в качестве первого набора данных брал только заполненную первую строку, а не первый блок (я его квадратом называю). Ну и при заполненном первых строке, столбце и квадрате, у меня получалось 40 стартовых наборов данных, которые между собой не эквивалентны.
Пробовал менять подход и расширять стартовый набор в другом порядке, но всё равно утыкался в необходимость перебора слишком большого числа не эквивалентных наборов и в итоге сдался и решил пойти по другому пути, комбинируя перебор с масками (возможно, про это будет во второй части Вашего перевода).
Я в качестве первого набора данных брал только заполненную первую строку, а не первый блок (я его квадратом называю). Ну и при заполненном первых строке, столбце и квадрате, у меня получалось 40 стартовых наборов данных, которые между собой не эквивалентны.
Пробовал менять подход и расширять стартовый набор в другом порядке, но всё равно утыкался в необходимость перебора слишком большого числа не эквивалентных наборов и в итоге сдался и решил пойти по другому пути, комбинируя перебор с масками (возможно, про это будет во второй части Вашего перевода).
UFO just landed and posted this here
Там проблема в том, что некоторые решения при повороте на 90 градусов переходят друг в друга, а остальные — нет. Т.е. нам нужно все решения как-то разбить на 2 кучи и размер одной из них делить на 4, а размер другой — нет. А теперь представьте как их нужно разделять, если у нас есть кроме поворотов есть перемешивание строк, столбцов, и прочее (а также все их комбинации). И еще нужно понять какую кучу на что делить.
Я как-то раз задумывался над этим. Нашёл чисто эмпирически такое свойство: если взять решение
123 456 789
456 789 123
789 123 456
234 567 890
567 890 234
890 234 567
345 678 901
678 901 345
901 345 678
То если заменить цифры по правилу перестановки — тоже получится решение судоку. Если поменять местами столбцы внутри троек или тройки столбцов — тоже получится решение судоку. То же для строк.
Я, правда, это наблюдение никак не анализировал, поэтому подозреваю, что описанные манипуляции +транспонирование не порождают всё множество возможных решений.
Это лишь одно уникальное заполнение сетки.
Путём перестановок\поворотов\отражений и перенумерований можно получить эквивалент, но не уникальную сетку.
По сути, Вы будете каждый раз решать одну и ту же задачку. Этим грешат многие генераторы головоломок.
Путём перестановок\поворотов\отражений и перенумерований можно получить эквивалент, но не уникальную сетку.
По сути, Вы будете каждый раз решать одну и ту же задачку. Этим грешат многие генераторы головоломок.
Не успел поправить, не 0, а 1, и в строках 7-9 не 1, а 2.
Пользуясь случаем даю ссылку на самописную программу, которая может найти все возможные решения для любого судоку (даже если неизвестны все поля судоку :) ). Написана на Go, поэтому для сборки необходим компилятор Go.
Она использует алгоритм танцующих ссылок и находит решение очень быстро.
В частности для примера в статье:
найдено одно и единственное решение:
Она использует алгоритм танцующих ссылок и находит решение очень быстро.
В частности для примера в статье:
3 _ _ 2 _ 1 _ _ _
7 4 _ _ _ _ _ 1 9
_ 2 _ _ 6 _ 5 _ _
_ 3 _ 7 4 _ _ _ 1
_ _ 8 _ _ _ 9 _ _
6 _ _ _ 9 2 _ 5 _
_ _ 2 _ 8 _ _ 4 _
1 5 _ _ _ _ _ 9 7
_ _ _ 9 _ 3 _ _ 2
найдено одно и единственное решение:
3 9 5 2 7 1 4 8 6
7 4 6 8 3 5 2 1 9
8 2 1 4 6 9 5 7 3
5 3 9 7 4 8 6 2 1
2 7 8 5 1 6 9 3 4
6 1 4 3 9 2 7 5 8
9 6 2 1 8 7 3 4 5
1 5 3 6 2 4 8 9 7
4 8 7 9 5 3 1 6 2
Sign up to leave a comment.
Судоку: так сколько же их? Часть 1/2