nlothik (nlothik) wrote,
nlothik
nlothik

Лыжи не едут (математическо-программистское)

В свободное от работы рабочее время решил немного порисовать всякое алгоритмическое. В частности, программу для решения задачек "Судоку". Чтобы мозги не ржавели.

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

А вот проверить правильность работы программы пока не получилось =)

Запускаю. Уже 30 минут комп работает как бешеный, а решения нет. Я-то думал, что у Судоку 9! + 8! + .. + 2! + 1 ~ 400 000 решений. А потом гляжу в педивикию и вижу, что у Судоку на самом деле 6.67×1021 решений (круто я лоханулся, на 16 порядков!). Вернее, для задачки с 17+ подсказками решение-то одно, но выбирать его приходится из 6.67×1021 вариантов. В секунду моя програмка на Питоне перебирает около 2 000 вариантов, следовательно, осталось ещё примерно 105 миллиардов лет :))))

При этом вроде как брутфорсным поиском по графу задача, если верить Педивикии, решается. Интересно, не то ли я мало ждал, не то программа у меня кривая, не то инструмент надо немного другой брать -- голый Си, например.
Tags: непонять, программирование
Subscribe

  • К психозу дня

    Столлман, конечно, мудак с большими прибабахами. Но он сделал для бесплатно-GNU-того ПО больше, чем все его критики, вместе взятые. Где бы они…

  • Началось

    В Кентукки рассматривается законопроект, который бы сделал незаконным оскорбление полицейских. С довольно расплывчатой формулировкой: незаконными…

  • Про метрическую систему

    Кодекс США от 1975 года, глава 15, параграф 205b: Декларация о политике Соединённых Штатов: (1) определить метрическую систему измерения как…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 2 comments