我编写了一个基于 JavaScript 的网站，可以输入、编辑和解决Nonograms。您可能知道，求解非图是一个 NP 完全问题。
我的第一次尝试是纯（单线程）JavaScript。但是在更大的 nonograms 上，Chrome 显示了它的 BSOD 并在几分钟后终止了 JS 脚本。下一次尝试是使用Web Workers。我拆分了求解算法，以便每个工作人员获得一行/列来求解并返回结果。这是一个改进，它能够解决中等大小的非图。但是，有时浏览器会在一段时间后杀死显示 BSOD 的 JS VM，而且网站并没有像我预期的那样真正响应，因为这就是 Web Workers 的用途，不是吗？
只是为了“好玩”，我将求解算法移植到 Python 并使用 ajax 请求调用 Python 脚本而不是 Web Workers。有趣的是，它甚至比 JavaScript 还要慢，但经过一段时间的计算，请求返回了 500 Internal Server Error。我相信这是由于 CGI 脚本的最大执行时间在 PHP afaik 上为 30 秒。
CGI 的想法并不是最好的，因为当多个用户想要解决一个 nonogram 时，服务器运行在 100% 的 CPU 上，所以我可能坚持使用客户端计算。
所以问题是，进行此计算的最佳方法是什么（对于较大的非图可能需要 10 分钟）？我认为只要网站保持响应并且浏览器不终止执行任务，执行时间就不是问题。
同时，我也在尝试优化递归算法......
谢谢！