Comments 14
Есть старая (но мне очень нравится) программа:
www.angusj.com/sudoku
Можно и решать всякие судоку, можно и обучаться разным хитрым приемам. А описанный алгоритм X, конечно, универсальный и для машинного перебора подходит, но изящества в нем не больше, чем в бульдозере.
К сожалению, справка (а в ней как раз и описаны пояснения к этим изящным приемам) будет работать только под Win9x/2K/XP. Для более старших надо скачать патч:
support.microsoft.com/ru-ru/help/917607/feature-not-included-help-not-supported-error-opening-help-windows
А для Win10 и патча такого нет…
Можно и решать всякие судоку, можно и обучаться разным хитрым приемам. А описанный алгоритм X, конечно, универсальный и для машинного перебора подходит, но изящества в нем не больше, чем в бульдозере.
Да, для обучения подходит чуть менее, чем никак. По сути — вычеркнуть всех одиночек, найти клетку с минимумом возможных вариантов, подставить один из них и продолжить решение; если найдено противоречие — откатиться к последнему ветвлению и попробовать другой вариант.
Меня тут поразило, что настолько лобовой подход настолько эффективен при использовании структуры данных, позволяющей быстрый откат из рекурсии.
В образовательных целях — на этом сайте в терминах матрицы покрытия объясняются некоторые техники решения в терминах матрицы покрытия. Наверное, поиск специфических паттернов даже можно сразу в алгоритм включить и сделать его побыстрее.
… найти клетку с минимумом возможных вариантов
Кстати, а почему именно с минимумом?
Как изменится эффективность алгоритма, если брать случайную клетку или даже с максимумом вариантов?
Ну это просто жадная стратегия поиска.
Логика, как мне кажется, тут следующая. Поиск ограничения, которое можно удовлетворить минимальным числом способов, всё равно нужен. Потому что если этот минимум ноль — то ветка тупиковая, и надо возвращаться. Если он равен единице — то элемент, удовлетворяющий ограничению, точно входит в покрытие. Ну а дальше, раз минимум всё равно нашли, давайте его и будем использовать.
В терминах О-большого асимптотика худшего случая не меняется, т.к. задача NP-полная. Для лучшего случая просто получается, что поиск одиночек не нужно программировать как какую-то особую стратегию, выбор клетки с минимальным числом вариантов именно их в первую очередь и будет заполнять.
Интересно было бы посмотреть на рост времени в зависимости от сложности.
От сложности в каком смысле? Уровень сложности классического судоку или при переходе к полям 16×16, 25×25 и т.д.?
В первом смысле: из той самой задачки с Project Euler самое простое судоку решается за 3.8 мс, самое сложное — за 4.6. Пример из комментария про "самое сложное судоку" в статье mrHobbY решается за 69 мс. Если в функциях нормально прописать аннотации типов, то цифры быстрее раза в 3-4, но соотношение между самым простым и самым сложным вариантом на порядок так и остаётся.
Во втором смысле: задача NP-полная, поэтому в худшем случае — время растёт очень сильно. Для простых случаев, когда не нужно ничего сложнее поиска цифр-"одиночек" — точно не хуже квадрата от числа клеток. Если поиск элемента, покрываемого минимальным количеством оставшихся подмножеств, сделать не линейным поиском, а через эффективную очередь — то, наверное, даже и O(NlogN) от числа клеток будет.
И таких перестроений будет превеликое множество. А еще возвраты надо делать после откатов из тупиков.
Так что, слухи об эффективности O(N*log(N)) сильно преувеличены.
Если говорить про лучший случай, когда всё решается последовательным заполнением одиночек, то тупиков не будет. Это я специально оговорил.
Эффективная очередь — это когда гарантирован только минимум в голове, а дальше может быть что угодно. Тогда смену приоритета одного элемента можно сделать за O(logN). Каждая строка в матрице имеет не больше 4 единиц, а столбец — не больше N1/2. Т.е. дописали циферку в решение — удаляем O(N1/2) строк из матрицы и тратим ещё O(N1/2logN) на обновление приоритетов в очереди.
Ну да — O(N3/2logN) (где N — число клеток, а цифр — N1/2). Но всё-таки лучше, чем квадрат. Хотя на классическом поле 9×9 все эти очереди с перестроениями могут тупо против линейного поиска ещё не сыграть.
И вообще… Вот поставили в клетку кандидата. Он вычеркивается из всех клеток, смежных по вертикали, горизонтали и по квадрату. Какие из этих клеток переносить в голову? Как я понимаю, те, у которых число кандидатов меньше, чем у головы. Простым обменом.
Нужно только сделать так, чтобы просматривать не все смежные клетки, а только те, которые еще не заполнены. Тогда их число будет постепенно снижаться.
Ну да, примерно так.
Только у всех смежных клеток пересматриваются приоритеты, и они двигаются к голове очереди, например, по алгоритму обновления двоичной кучи. То, что уже заполнено, по алгоритму автоматом вычёркивается и повторно не просматривается, это само собой.
Только на самом деле там кроме ситуации "на клетку Г, В осталось мало кандидатов" нужно просмотреть "на горизонтали Г для цифры А осталось мало возможных мест" и аналоги для вертикали и квадрата. Вычёркивается, соответственно, не только цифра из кандидатов в другие клетки, но и вертикаль из доступных для других цифр на этой горизонтали и т.д.
Более сложные судоку имеют меньшее количество стартовых цифр. Собственно все. Генерализация на разные основания систем счисления уже не настолько интересно.
С псевдо-кодом было бы великолепно! (не все мы Julia)
Решаем судоку с помощью Алгоритма X