про алгоритмы
2024-May-16, Thursday 18:14![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
ypqкогда есть 5 "лишних" минут, я беру сборник сканвордов. а там иногда вставляют странички с судоку. простые я решаю сразу, но там бывают всякие усложненные. 16*16, например, или чтоб ещё по диагоналям цифры не повторялись. или ещё что. нет, они все решаемы, конечно, но не за 5 минут. начнешь, потом прервешься, потом приходится с начала соображать.
так что я эти листочки вырывал и копил. и уже накопилась целая стопка. думаю: а напишу-ка я программу? заодно освежу навыки. начал с Ruby, я им как-то чаще пользовался раньше. полез искать - в чем нынче модно программировать? чтоб редактор и отладка. нашел, что а лучше-то не Ruby, а Python. попробовал Jupyter Notebook - класс! там прям можно с окнами работать. ну и раз уж полез в интернет, нашел пример программы-решалки судоку. как раз для окон tkinter. но оно для 9*9. ну и ладно. переделал для 9*9+диагонали. передалал для 9*9+9 клеток. переделал под 9*9+9+9 клеток. прекрасно!
потом стал переделывать под 16*16. тут пошли проблемы - поля 2-значные. ладно, переделал под символы. от 1-9, плюс от a до g. запустил - тишина. ну тоже понятно: то ли перебирать 9*9, то ли 16*16!
когда гуглил алгоритм, попадалась мне программка на Ruby - DLX-sudoku-solver. я на ней не остановился, потому что Python, Jupyter, tkinter... и ещё нагуглился сайт с разными алгоритмами. супер! решает 9*9 разными способами. причем, можно следить за процессом. и там есть этот DLX. и вживую понятно, что он уделывает все остальные алгоритмы.
стало интересно. полез читать корифеев.
снова нашел ссылку на решалку на Ruby. разобрался. переделал под 16*16. итого: подсунул судоку 16*16, и чуть ли не мгновенно получил ответ. для сравнения, в другом окне была запущена программа на Python, которую я запустил примерно утром... на то же самое судоку 16*16. и там результат выскочил примерно на 5 минут позже. в смысле: я её запустил, потом читал Кнута, потом переделывал-отлаживал алгоритм на Ruby, да ещё обедал, да ещё другими делами занимался.
итого: разница часов 8!
на примере было 9*9 не так наглядно.
остались хитрые судоку где в центре 9*9, которое угловыми блоками объединено с ещё 4 9*9. но я пока не придумал как это привести к виду DLX.
9*9+диагонали, 9*9+9 клеток и 9*9+9+9 клеток - легко.
так что я эти листочки вырывал и копил. и уже накопилась целая стопка. думаю: а напишу-ка я программу? заодно освежу навыки. начал с Ruby, я им как-то чаще пользовался раньше. полез искать - в чем нынче модно программировать? чтоб редактор и отладка. нашел, что а лучше-то не Ruby, а Python. попробовал Jupyter Notebook - класс! там прям можно с окнами работать. ну и раз уж полез в интернет, нашел пример программы-решалки судоку. как раз для окон tkinter. но оно для 9*9. ну и ладно. переделал для 9*9+диагонали. передалал для 9*9+9 клеток. переделал под 9*9+9+9 клеток. прекрасно!
потом стал переделывать под 16*16. тут пошли проблемы - поля 2-значные. ладно, переделал под символы. от 1-9, плюс от a до g. запустил - тишина. ну тоже понятно: то ли перебирать 9*9, то ли 16*16!
когда гуглил алгоритм, попадалась мне программка на Ruby - DLX-sudoku-solver. я на ней не остановился, потому что Python, Jupyter, tkinter... и ещё нагуглился сайт с разными алгоритмами. супер! решает 9*9 разными способами. причем, можно следить за процессом. и там есть этот DLX. и вживую понятно, что он уделывает все остальные алгоритмы.
стало интересно. полез читать корифеев.
снова нашел ссылку на решалку на Ruby. разобрался. переделал под 16*16. итого: подсунул судоку 16*16, и чуть ли не мгновенно получил ответ. для сравнения, в другом окне была запущена программа на Python, которую я запустил примерно утром... на то же самое судоку 16*16. и там результат выскочил примерно на 5 минут позже. в смысле: я её запустил, потом читал Кнута, потом переделывал-отлаживал алгоритм на Ruby, да ещё обедал, да ещё другими делами занимался.
итого: разница часов 8!
на примере было 9*9 не так наглядно.
остались хитрые судоку где в центре 9*9, которое угловыми блоками объединено с ещё 4 9*9. но я пока не придумал как это привести к виду DLX.
9*9+диагонали, 9*9+9 клеток и 9*9+9+9 клеток - легко.
(no subject)
Date: 2024-05-16 14:21 (UTC)Нормально. Jupyter удобная вещь, если в продакшен не надо.