ノノグラムを入力、編集、解決できる JavaScript ベースの Web サイトを作成しました。ご存知かもしれませんが、ノノグラムを解くことは NP 完全問題です。
私の最初の試みは、純粋な (シングル スレッド) JavaScript でした。しかし、より大きなノノグラムでは、Chrome は BSOD を表示し、数分後に JS スクリプトを強制終了しました。次の試みはWeb Workersを使用することでした。各ワーカーが 1 つの行/列を取得して解決し、結果を返すように、解決アルゴリズムを分割します。これは改善であり、中サイズのノノグラムを解決することができました。それでも、ブラウザが JS VM を強制終了し、しばらくすると BSOD が表示されることがあります。また、Web ワーカーはそのために作られているため、期待どおりに Web サイトが応答しませんでしたね。
「楽しみ」として、解決アルゴリズムを Python に移植し、Web ワーカーの代わりに Python スクリプトを呼び出す ajax リクエストを使用しました。興味深いことに、JavaScript よりもさらに遅くなりましたが、しばらく計算した後、リクエストは 500 Internal Server Error を返しました。これは、CGI スクリプトの最大実行時間が PHP で 30 秒であるためだと思います。
複数のユーザーがノノグラムを解きたい場合、サーバーは 100% の CPU で実行されるため、CGI のアイデアは最善ではありませんでした。
質問は、この計算を行う最善の方法は何ですか? Web サイトが応答を維持し、ブラウザーが実行タスクを強制終了しない限り、実行時間は問題ではないと思います。
その間、再帰アルゴリズムの最適化も試みています....
ありがとう！