Comments 27
Лень читать. Просто поделюсь своим.
https://github.com/grunmouse/sudocu
Доки нет. Почитайте код.
То, что не может решить этот алгоритм, - я сам тоже без перебора решить не могу. Проверял на игре для телефона.
Мне эта тема уже не интересна, отпускаю в свободное плаванье, если кому-то нужно.
Ну, без перебора в любом случае не обойтись... вопрос только "что перебираем". У меня вырисовывается задумка перебирать крупные валидные варианты сразу, коих даже может оказаться не так уж и много.
За ссылку спасибо, гляну, как будет время)
После прохода всех эвристик, остаются варианты, считаемые по пальцам одной руки.
По крайней мере, так было, когда я пробовал на игре.
Я поставил эту двойку в центре не перебирая варианты. Я чётко знаю, что она там будет, прогнозируя позиции двоек всего на один ход вперед:
Я вижу "лёгкую двойку" в квадрате 5 из-за обилия двоек вокруг, но пока непонятки с квадратом 4.
Я смотрю на квадрат 4, вижу, что ячейки 1,4,5,6,7,8,9 не могут содержать двойки, значит двойка будет либо в 2, либо в 3, и мне абсолютно все равно где именно, ибо в данный момент я на уровне абстракции горизонтальных линий
Я занимаю горизонтальные и вертикальные линии в квадрате 5, оставляя только одну доступную ячейку - 5, куда и ставлю двойку.
Это не перебор вариантов, это анализ. Мне нет смысла пытаться расставлять 9-ки в 3м квадрате, пока там не будет 2-3х свободных клеток, либо пока этот квадрат не будет "окружен" девятками из других квадратов.
Первый этап алгоритма (который описан в статье и работает) - можно сказать, тоже анализ. Хоть мб из него еще не все выжато.
Дальше уже сборка всего в единое целое, тут явно нужен какой-то перебор.
Судоку простого уровня решаются без перебора, на голых эвристиках.
Я только для примера выбрал такое, где не надо вглубь далеко ходить. А так, тем же алгоритмом решаю "эпические" (название, чтоб самооценку у пользователей поднимать, видимо) на том же сайте. Но там добавляется ещё один алгоритм, а именно "занять пару клеток парой цифр", и аналогично тройками, которые точно также закрывают ряды/столбцы в соответствующих квадратах. Типа: расставляем все возможные варианты; видим, что в квадрате в 2х клетках есть пара цифр, которые больше никуда в квадрате встать не могут; значит другие цифры в этих двух клетках быть не могут. И это всё ещё не перебор. Если судоку решается только перебором, т.е. имеет 2 и более решений - это неправильное судоку.
"занять пару клеток парой цифр", и аналогично тройками, которые точно также закрывают ряды/столбцы в соответствующих квадратах.
В моём алгоритме это тоже есть. Занять N клеток N цифрами.
И на сложном уровне я сталкивался с судоку, которые имеют одно решение, но его нельзя найти из исходных данных без пробной подстановки.
Читал, читал и как то не понял прикола с опорными точками. Ты типо собираешься относительно опорных точек подбирать значения?
Я как то давно делал авторешатель судоку. (Только я работал с кодом на C++, но это не важно).
У меня было несколько этапов:
1) сбор полной информации о всех свободных клеток (при этом собирал я их в разные массивы: общий где абсолютно все клетки, клетки находящиеся в одном большом квадрате, по горизонтали, по вертикали. получились 4 блока для анализа)
2) для каждой свободной клетки я собирал массив из возможных вариантов (для этой цели я использовал массив битов, для того чтобы хоть как-то сэкономить на памяти, то есть соответственно 0 бит отвечал за число 1, 2 бит за число 3 ну и так далее)
3) я проводил анализ каждого блока (из 1 этапа) для массива, где хранятся все свободные клетки, я искал клетки у которых имеется единственное возможное значение после чего записывал его и удалял клетку из всех блоков. Для остальных блоков была задача на поиск единственного возможного значения, которого нет в других клетках, ну и снова записывал его и удалял из всех блоков.
4) провожу проверку на то что решено (индикатором являлся размер 1 блока)
5) проверяю на ошибки (в возможных вариантах клетки отсутствуют варианты, это единственный способ проверки мне тогда пришел в голову)
6) если в 3 этапе была совершена хотя бы 1 запись то возвращался к 3 этапу, в противном случае я искал клетку с минимально возможным количеством вариантов. (Самый желанный вариант это клетка с 2 возможными значениями) Копировал всё данные и в копию подставлял возможный вариант и отправлял копированные данные на 3 этап и так далее пока не решится или не обнаружится ошибка.
В принципе мой алгоритм справлялся с судоку размером 25х25, но с 36х36 уже слишком долго выполняется.
Сейчас у меня есть пара мыслей как можно оптимизировать алгоритм, но если честно просто лень
Да, алгоритм построен так, что бессмысленно запускать его на всем массиве свободных точек - мы просто получим кучу пересечений. Достаточно ограничиться лишь небольшим количеством точек и их сегментами, главное - чтобы ими и их сегментами в итоге можно было покрыть все поле. По идее этого достаточно, чтобы получить все куски возможных решений, а дальше пробовать собирать их в одно.
Еще не до конца вник в ваше решение, но смотрится интересно. Спасибо, что поделились) Может, и для себя что-то подчерпну.
25 на 25 - впечатляет, на самом деле)
Да, алгоритм построен так, что бессмысленно запускать его на всем массиве свободных точек - мы просто получим кучу пересечений. Достаточно ограничиться лишь небольшим количеством точек и их сегментами, главное - чтобы ими и их сегментами в итоге можно было покрыть все поле. По идее этого достаточно, чтобы получить все куски возможных решений, а дальше пробовать собирать их в одно.
Еще не до конца вник в ваше решение, но смотрится интересно. Спасибо, что поделились) Может, и для себя что-то подчерпну.
25 на 25 - впечатляет, на самом деле) Мое почтение!
К слову: а за сколько (примерно) ваш алгоритм справлялся с 25 на 25? И с 36 на 36 сколько зависал?
Вряд ли смогу точно сказать, но по-моему меньше 5 секунд для 25х25. А для 36х36 я просто ждал около минуты ничего не происходило, ну и выключал программу
Ок, спасибо. Будет с чем сравнить)
А на "эвересте", кстати, не пробовали?
В каком смысле на Эвересте?
П.С. я для тестов алгоритма брал из интернета самые сложные варианты судоку.
Самое сложное классическое судоку в мире от одного финского математика)
Лично в этом убедился, немного с ним поработав.
А многомерные обобщения судоку не пробовали?
Пока еще нет) Сперва бы с этим закончить.
Мне пришло в голову, что интересно было бы рассмотреть эту игру с математической, а не с алгоритмической точки зрения. Но сам я вряд ли найду время.
Далек от математики, к сожалению( Хотя было бы интересно. Но игру анализируют и с точки зрения математики, да.
https://en.m.wikipedia.org/wiki/Mathematics_of_Sudoku
Вообще - меня, кажется, начали посещать довольно удачные мысли буквально вчера после серии провальных попыток, и что-то из этого даже для многомерного судоку можно было бы использовать. Но пока для этого рановато.
Советую глянуть вот этот солвер - https://www.sudokuwiki.org/sudoku.htm
Существует ряд техник для решения судоку, включая jellyfish/swordfish, да и базовые x-wing/y-wing/раскраска парных цифр.
Что можно сказать на данный момент?
Почти все, что есть тут - не более чем предпосылки хороших (как мне пока кажется) идей, вместе не дающие нормальных перспектив к решению.
Самое ценное для меня, что тут есть - подбор опорных точек; формирование мапы потенциалов; валидация; на самом деле не такая уж и дурная структура намберсиквенс, которую просто следует серьезно пересмотреть и развить; работающий вкупе с ней алгоритм формирования вариантов. Далее - соотнесение получаемых вариантов сабсегментов и группировка в батчи - это уже "Остапа понесло". Получаемая мусорная куча почти неразгребаема не то что на гигантах - а в большинстве попыток даже на Эвересте) Да еще и содержала детские ошибки вроде перепутанных аргументов в конструкторе.
К счастью, сейчас меня посетила неплохо смотрящаяся идея. Попробую ее реализовать, подглядывая в мусорные наработки.
Судоку: моя попытка в новый алгоритм решения. Часть 1 (надеюсь)…