Comments 28
Вместо unknown лучше бы стоило использовать спец значение undefined.
Вот ещё забавная решалка на JS: blgo.ru/games/sudoku/ не всё решает, правда.
Сделайте страницу с демкой, если можете.
Сегодня не обещаю, сейчас реализовано только решение судоку, возможность создания и редактирования отсутствует как класс.
Вот, сделал на скорую руку: bit.ly/testSudoku
Сорри за говнокод, но потестить можно.
Сорри за говнокод, но потестить можно.
По хорошему, следовало бы добавить ситуации «некоторые K цифр могут встретиться только в K клетках столбца/строки/блока — тогда в этих клетках могут всетретиться только эти цифры, а остальные не могут». При K=1 это дает «скрытого одиночку», а при K=F-1, где F — число неразгаданных клеток блока, — «одиночку». Но, к сожалению, даже этот прием не позволяет решить все. Без перебора не обойтись :(
По второй ссылке, приведенной в конце статьи, есть еще несколько методов решения судоку, но их реализация раздула бы код и уменьшила его наглядность. Хотя при желании все их можно реализовать ;)
Да, наверное. Но разве один метод (поиск скрытого блока — перебором всех подмножеств) по сравнению с двумя — это «раздутый код»?
Каждый небазовый метод дает эффект только на ограниченном множестве ситуаций. Использованные «Одиночка» и «Скрытый одиночка» универсальны и решают задачи простого и среднего уровней.
Более сложные алгоритмы известны и подробно описаны, поэтому их кодинг не доставит удовольствия создания чего-то нового.
Более сложные алгоритмы известны и подробно описаны, поэтому их кодинг не доставит удовольствия создания чего-то нового.
А Вы что, читаете описание алгоритмов??? Тогда, конечно, никакого удовольствия… А если не читать, то всегда есть шанс, что получится что-то новое.
Как там Ньютон говорил? «Если я видел дальше других, то потому, что стоял на плечах гигантов». Всегда полезно знать, до чего додумались коллеги по цеху. Это может натолкнуть и на новые идеи, которые могли бы быть пропущены в попытках решения давно преодоленных задач.
Изобретение велосипедов весело и интересно, и даже полезно для самообразования. Показанные алгоритмы я восстановил просто вспоминая, как я решал судоку, но потом решил посмотреть, что же народ напридумывал. И оказалось, что мои «изобретения» даже имя имеют!!! И есть множество других способов решения головоломки, для формализации которых потребуется много задачек перерешать.
Изобретение велосипедов весело и интересно, и даже полезно для самообразования. Показанные алгоритмы я восстановил просто вспоминая, как я решал судоку, но потом решил посмотреть, что же народ напридумывал. И оказалось, что мои «изобретения» даже имя имеют!!! И есть множество других способов решения головоломки, для формализации которых потребуется много задачек перерешать.
>Поиски решения заканчиваются, если после перебора всех нерешенных ячеек ни для одной из них не удалось найти решение или не было изменено количество кандидатов
На этом этапе хорошо было бы не заканчивать поиск, а начинать применять поиск с возвратом.
На этом этапе хорошо было бы не заканчивать поиск, а начинать применять поиск с возвратом.
А что вы подразумеваете под «поиском с возвратом»?
Поиск с возвратом.
Применительно к данной задаче:
Когда не осталось явных решений, в каждой ячейке стоит 2 и более вариантов, и «скрытых одиночек» тоже не получается найти, то берётся одна из ячеек, в неё наугад ставится один из возможных вариантов, после чего «заседание продолжается» по приведённым в топике алгоритмам. Если на каком-то этапе приходим к противоречию, то нужно вернуться на шаг выбора варианта и попробовать следующий.
Применительно к данной задаче:
Когда не осталось явных решений, в каждой ячейке стоит 2 и более вариантов, и «скрытых одиночек» тоже не получается найти, то берётся одна из ячеек, в неё наугад ставится один из возможных вариантов, после чего «заседание продолжается» по приведённым в топике алгоритмам. Если на каком-то этапе приходим к противоречию, то нужно вернуться на шаг выбора варианта и попробовать следующий.
Я думал над этим. Даже пробовал ручной просчет на нерешаемой задаче (в архиве этот вариант помечен как unsolved). Но получалось слишком много уровней ветвлений, т.е. пришлось бы делать многоуровневое сохранение состояний и возможностью отката на каждое из них.
Как-то некрасиво это смотрится… не элегантно… Учитывая, что остались еще в запасе нереализованные непрямые алгоритмы.
Как-то некрасиво это смотрится… не элегантно… Учитывая, что остались еще в запасе нереализованные непрямые алгоритмы.
>Но получалось слишком много уровней ветвлений, т.е. пришлось бы делать многоуровневое сохранение состояний и возможностью отката на каждое из них.
Откатываться нужно не на каждое, а только на предыдущее. И не нужно нигде вручную ветвиться — рекурсия всё сделает за вас. Всё, что вам нужно — «клонировать» текущее состояние, после чего подставить один из возможных вариантов и вызывать вашу основную функцию solve() на этой матрице.
Функция завершилась успешно? Всё, вот оно, решение. Завершилась неудачей? Пробуем следующий вариант и снова вызываем.
Если подобная «неопределённость» возникнет ещё раз, то она будет разрешена аналогичным образом без какого-либо дополнительного вмешательства.
Уж не знаю, каковы у вас критерии «элегантности», но при той реализации, как её вижу я, понадобится добавить строк 20, не больше.
Откатываться нужно не на каждое, а только на предыдущее. И не нужно нигде вручную ветвиться — рекурсия всё сделает за вас. Всё, что вам нужно — «клонировать» текущее состояние, после чего подставить один из возможных вариантов и вызывать вашу основную функцию solve() на этой матрице.
Функция завершилась успешно? Всё, вот оно, решение. Завершилась неудачей? Пробуем следующий вариант и снова вызываем.
Если подобная «неопределённость» возникнет ещё раз, то она будет разрешена аналогичным образом без какого-либо дополнительного вмешательства.
Уж не знаю, каковы у вас критерии «элегантности», но при той реализации, как её вижу я, понадобится добавить строк 20, не больше.
> Всё, что вам нужно — «клонировать» текущее состояние, после чего подставить
> один из возможных вариантов и вызывать вашу основную функцию solve() на этой матрице.
> Функция завершилась успешно? Всё, вот оно, решение. Завершилась неудачей? Пробуем
> следующий вариант и снова вызываем.
Не совсем так. Предположим, алгоритм застопорился в бессилии. Находим ячейку с двумя кандидатами. Выбираем первого, прогоняем solve() — решение не найдено. Выбираем второго, и снова решения нет. Переходим ко второму уровню. Берем первого кандидата и снова гоним алгоритм до точки, среди пустых- ячеек снова ищем ячейку с минимальным количеством кандидатов и начинаем их перебирать. И так далее. в ручном режиме я прошел три уровня и так и не добился полного решения. Да все это можно завернуть в рекурсию и гонять ее по всему дереву предположений в надежде найти решение. В худшем случае решение будет мало отличаться от полного перебора.
> Уж не знаю, каковы у вас критерии «элегантности»
Одним из критериев элегантности я считаю вычислительную сложность алгоритма и полный перебор ну никак этому критерию не соответствует.
> один из возможных вариантов и вызывать вашу основную функцию solve() на этой матрице.
> Функция завершилась успешно? Всё, вот оно, решение. Завершилась неудачей? Пробуем
> следующий вариант и снова вызываем.
Не совсем так. Предположим, алгоритм застопорился в бессилии. Находим ячейку с двумя кандидатами. Выбираем первого, прогоняем solve() — решение не найдено. Выбираем второго, и снова решения нет. Переходим ко второму уровню. Берем первого кандидата и снова гоним алгоритм до точки, среди пустых- ячеек снова ищем ячейку с минимальным количеством кандидатов и начинаем их перебирать. И так далее. в ручном режиме я прошел три уровня и так и не добился полного решения. Да все это можно завернуть в рекурсию и гонять ее по всему дереву предположений в надежде найти решение. В худшем случае решение будет мало отличаться от полного перебора.
> Уж не знаю, каковы у вас критерии «элегантности»
Одним из критериев элегантности я считаю вычислительную сложность алгоритма и полный перебор ну никак этому критерию не соответствует.
>Предположим, алгоритм застопорился в бессилии. Находим ячейку с двумя кандидатами. Выбираем первого, прогоняем solve() — решение не найдено. Выбираем второго, и снова решения нет.
«Решения нет» — это «найдено противоречие» или «снова застопорились»?
Если первое — тогда всё, решения действительно нет. Если второе — то алгоритм сделает следующее предположение рекурсивно, никуда «руками» идти не нужно.
>Да все это можно завернуть в рекурсию и гонять ее по всему дереву предположений в надежде найти решение. В худшем случае решение будет мало отличаться от полного перебора.
Ну, не скажите. После каждого рекурсивного вызова снова гоняются поиски одиночек и скрытых одиночек, что значительно сокращает количество вариантов перебора, так что даже на повышенных уровнях сложности рекурсия не заберётся дальше 2-3-5 уровней. Это я вам говорю как человек, который несколько месяцев подряд развлекался судоку ежевечерне при укладывании дочки спать :)
>Одним из критериев элегантности я считаю вычислительную сложность алгоритма и полный перебор ну никак этому критерию не соответствует.
Как я уже сказал выше, о полном переборе речи не идёт. На реальных задачах будет не больше полудесятка рекурсивных вызовов. Ну а синтетику, разумеется, можно подогнать какую угодно :)
В общем, моё дело предложить, а решать уже вам.
«Решения нет» — это «найдено противоречие» или «снова застопорились»?
Если первое — тогда всё, решения действительно нет. Если второе — то алгоритм сделает следующее предположение рекурсивно, никуда «руками» идти не нужно.
>Да все это можно завернуть в рекурсию и гонять ее по всему дереву предположений в надежде найти решение. В худшем случае решение будет мало отличаться от полного перебора.
Ну, не скажите. После каждого рекурсивного вызова снова гоняются поиски одиночек и скрытых одиночек, что значительно сокращает количество вариантов перебора, так что даже на повышенных уровнях сложности рекурсия не заберётся дальше 2-3-5 уровней. Это я вам говорю как человек, который несколько месяцев подряд развлекался судоку ежевечерне при укладывании дочки спать :)
>Одним из критериев элегантности я считаю вычислительную сложность алгоритма и полный перебор ну никак этому критерию не соответствует.
Как я уже сказал выше, о полном переборе речи не идёт. На реальных задачах будет не больше полудесятка рекурсивных вызовов. Ну а синтетику, разумеется, можно подогнать какую угодно :)
В общем, моё дело предложить, а решать уже вам.
На пустом поле перебор с возвратом (после поиска открытых и скрытых блоков любого размера) потребовал 47 развилок. Точнее, «перебором с возвратом» ее назвать трудно — первая же ветка дала ответ. На первой попавшейся «головоломке для гениев» было достаточно одной развилки.
Сам перебор (с поиском оптимальной клетки — где меньше всего возможностей) занял 20 строк, а вся программа меньше 100 (на C#).
Сам перебор (с поиском оптимальной клетки — где меньше всего возможностей) занял 20 строк, а вся программа меньше 100 (на C#).
Спасибо, ч.т.д.
Даже с количеством строк не ошибся :)
Даже с количеством строк не ошибся :)
Реализовал обратный поиск. У меня на него ушло 99 строк с комментариями :). Код выложен здесь.
Прикрутил к другой демке: bit.ly/testSudokuBacktracking
Именно такая логика была у меня, когда делал AISudokusolver.com. У Кнута есть алгоритм «Dancing Links», реализацию которого для решения судоку не сложно найти. Скорость решения составляет тысячи решений судоку на не самом лучшем компьютере.
Лучше назвать этот метод так, как он всегда назывался, а именно поиск в глубину )
Вам надо бы познакомиться с битовыми масками.
Тогда не было бы трехмерных массивов, функции lessRowSuggest и т.п. стали бы гораздо короче,
а arrayDiff записалась бы в ОДНУ операцию!
Можете сравнить с моим решением на Java.
Тогда не было бы трехмерных массивов, функции lessRowSuggest и т.п. стали бы гораздо короче,
а arrayDiff записалась бы в ОДНУ операцию!
Можете сравнить с моим решением на Java.
Когда хотело подружиться с питоном, взялся написать решатель какуро. Там похожие алгоритмы, но почему-то не все какуро решались, но интерес у меня уже пропал и я забросил это дело.
Вот что вышло:
pastebin.com/DmNBg7pp
Вот что вышло:
pastebin.com/DmNBg7pp
Sign up to leave a comment.
Решаем судоку на JavaScript