Я написал веб-сайт на основе JavaScript, который может вводить, редактировать и решать нонограммы. Как вы, возможно, знаете, решение кроссворда — это NP-полная задача.
Моей первой попыткой был чистый (однопоточный) JavaScript. Но на больших нонограммах Chrome показывал свой BSOD и убивал JS-скрипт через несколько минут. Следующей попыткой было использование Web Workers. Я разделяю алгоритм решения так, чтобы каждый работник получал одну строку/столбец для решения и возвращал результат. Это было улучшением, и он мог решать нонограммы среднего размера. Но, тем не менее, иногда браузер убивал виртуальную машину JS, показывающую BSOD через некоторое время, плюс веб-сайт не совсем отвечал, как я ожидал, поскольку для этого созданы веб-воркеры, не так ли?
Просто для «забавы» я перенес алгоритм решения на Python и использовал ajax-запросы, вызывающие скрипт Python вместо Web Workers. Интересно, что он был даже медленнее, чем JavaScript, но после некоторого времени вычислений запрос возвращал 500 Internal Server Error. Я считаю, что это связано с максимальным временем выполнения CGI-скрипта, которое на PHP составляет 30 секунд.
Идея CGI была не лучшей, потому что, когда несколько пользователей хотят решить нонограмму, сервер работает на 100% ЦП, поэтому я, вероятно, придерживаюсь вычислений на стороне клиента.
Итак, вопрос в том, как лучше всего выполнить это вычисление (которое может занять около 10 минут для больших нонограмм)? Я думаю, что время выполнения не является проблемой, пока веб-сайт остается в ответе и пока браузер не убивает задачи выполнения.
Тем временем я также пытаюсь оптимизировать рекурсивный алгоритм....
Спасибо!