Sudoku DLX Solver - очень быстрый решатель судоку

Написал решатель судоку Sudoku DLX Solver и опубликовал его на гитхабе https://github.com/RoyalXXX/sudoku_dlx
Там есть и код и очень подробное описание на английском. Тут лишь я коротко напишу о проекте.

Алгоритмов решения судоку множество, самые банальные выложены на разных сайтах, например, https://www.geeksforgeeks.org/cpp/sudoku-in-cpp/ Тем не менее, я хотел, чтобы мой решатель был очень быстрым и решал быстро даже самые сложные судоку (как например, тот, который приведен в описании моего проекта на гитхабе) и чтобы он находил не только одно решение, а все решения или столько решений, сколько укажу.

Немного о моем Sudoku DLX Solver:

1. используется самый быстрый в этой области алгоритм танцующих ссылок (DLX) Дональда Кнута. Быстрее этого алгоритма ничего не найдете для решения судоку. Если и найдете код, который будет быстрее моего, то наверное там будет тот же алгоритм, но просто будет реализована многопоточность или будет написан специально под инструкции современных процессоров, либо может использоваться стековая память.

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

Короче, поскольку я не нашел нормальный решатель на С++, то я приложил много усилий, чтобы перевести увиденное на нормальный С++. Мой Sudoku DLX Solver состоит из двух файлов: *.h и *.cpp, как я традиционно люблю делать. Старался писать все согласно философии С++, без сишкодерства.
Размер судоку можно задать на рантайме, использовал кучу, умные указатели, проверки, исключения, реализовал класс с инкапсуляцией. Во время написания постоянно проверял скорость, память. Скажу, что разница в производительности между моим "безопасным" решателем на векторах и стековыми реализациями почти мизерная из-за правильного резервирования памяти.

3. решатель работает не только для 9x9, но также для судоку любых размеров, 4, 16, 25 и т.д. Причем, можно найти не только одно решение, а можно получить прям все. Для функции поиска всего лишь нужно указать лимит поиска. Но обычно ищут либо одно решение (т.е. выставляют лимит на 1) или два судоку (чтобы убедиться, что судоку корректное и имеет только одно решение). Обычно последнее используется в алгоритмах для генерации судоку, чтобы убедиться, что сгенерированное судоку имеет только одно решение. Поиск второго и последующих решений обычно осуществляется очень быстро, поэтому без проблем можно выставить большие лимиты для поиска.

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

4

Сообщение от Royal_X мне просто лень тестировать судоку alexu_007, а он спрашивал время. Но учитывая, что ты тестировал и его судоку, и мое, то я указал время моего судоку (которое мне было известно), чтобы он приблизительно понимал насколько сабж быстрый. А так для тебя ничо.

Ну ладно...

0

alexu_007, мой проект выложен на гитхабе, так что можешь сам проверять, экспериментировать, даже внедрять в свою программу. Хотя, не думаю, что для твоей программы тебе нужна прям высокая скорость.
Сила сабжа еще в том, что если у судоку множество решений (т.е. когда это корявое судоку), то решатель думает больше всего для первого решения, а все последующие решения находит за мизерное количество времени, например, со скоростью 5-20 µs на одно решение.

***

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

0

Сообщение от Royal_X имеет только одно решение)

Да ладно. Как вам такое? Ну и вариант Verevkinа еще третий до кучи:

Миниатюры

 

0

Сообщение от alexu_007 Да ладно. Как вам такое?

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

alexu_007, и если тебе интересно, то у судоку, которое у тебя получилось при неправильном вводе, 3359 решений и все они находятся у меня за 10 мс.

0

Предложенное Royal_X судоку решается чисто аналитически, без необходимости пользоваться перебором, когда аналитика заходит в тупик. Предложенное мной "самое сложное..." аналитически не находит ни одной цифры (может конечно мой "анализ" несколько туповат...) и сразу приходится пользоваться подбором. Вот эта нижняя циферка на моей программе показывает, сколько раз программе приходится лазить в подбор, до полного решения задачи. О сложности алгоритма я сужу по ней. Время, к сожалению, у меня не замеряется, т.к. результат появляется на экране быстро (почти сразу, доли секунды).

Вот сложность по моей методике моего судоку, сложность судоку Royal_X см. выше:

Миниатюры

 

0

Сообщение от alexu_007 сложность судоку Royal_X см. выше

так ты же решил вообще не то судоку

0

Сообщение от Royal_X ты неправильно ввел данные. Обрати внимание на нижний правый блок. 7 и 3 должны быть рядом, а у тебя между ними пустая ячейка. и да, там точно одно решение

Прошу прощения, точно одно решение. Ну и 10 мс за 3359 решений тоже впечатляет...

0

Сообщение от alexu_007 Ну и 10 мс за 3359 решений тоже впечатляет...

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

Сообщение от alexu_007 впечатляет...

впечатляет там то, что я написал на векторах и все равно оно очень быстрое. Но если писать небезопасный код на стеке в целях спортивного программирования, то оно будет работать еще быстрее. Мне показалось, что оно того не стоит. Лучше пусть будет нормальный код. Я изначально стековую память использовал, но потом увидел, что переход на векторы незначительно влияет на производительность, поэтому решил лучше с векторами, чтобы еще и в рантайме размер задавать.
Недостатки стековой памяти я указал в Sudoku DLX Solver - очень быстрый решатель судоку

0

Очередной шикарный проект от вас

Интересно, на высоте вашего большого опыта реализации популярных логических игр, появились ли у вас идеи о своей собственной, уникальной игре?

0

Сообщение от Noname2331 появились ли у вас идеи о своей собственной игре

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

0

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

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

1

Noname2331, спасибо за добрые слова. Но вместо того, чтобы ждать, лучше сами начните что-то разрабатывать. Писать программы, даже мелкие, это лучший способ изучения языка.

1

Сообщение от Royal_X Noname2331, спасибо за добрые слова. Но вместо того, чтобы ждать, лучше сами начните что-то разрабатывать. Писать программы, даже мелкие, это лучший способ изучения языка.

Я уже искушенный. После основной работы со всякими кибернетисами и прочей коммерческой шизой быстрее бегу домой, чтобы продолжить работу над своим эмулятором процессора на JS (упрощенный 6502, "дальше упрощать некуда"). Но вот поглядываю на с.

0