JavaScript で Sudoku を解いてみる (3)

前回までで、問題と条件が記述できたので、後は例によって解けば良い。

今回はモナドを利用したおかげで条件の記述がそのまま条件をチェックするコードになるので、ソルバは非常にシンプルに書ける。

        function solve(question, conditions, iter) {
            var result;
            if(iter === undefined) iter = 0;
            else if(iter >= question.length) return;
            var answer = [];
            question[iter].selectEach(function() {
                result = conditions();
                if(result === undefined)
                    answer = answer.concat(solve(question, conditions, iter+1));
                else if(result === true) {
                    answer.push(question.map(function(tile) { return tile.get(); }));
                }
            });
            return answer;
        }

        var Question = Cells.reduce(function(prev, row) {
            return prev.concat(row);
        }, []);

        var Answer = solve(Question, Condition);

ここまでシンプルに書けると、もはやソルバは要らないんじゃないかと思えてきて、問題に吸収させて、問題生成時に問題に対応するソルバを生成するようにもしてみた。

        function Question(items) {
            this.Solve = items.reduce(function(prev, item) {
                return function(condition) {
                    var answer = [];
                    item.selectEach(function() {
                        result = condition();
                        if(result === undefined)
                            answer = answer.concat(prev(condition));
                        else if(result === true) {
                            answer.push(items.map(function(tile) { return tile.get(); }));
                        }
                    });
                    return answer;
                }
            }, function() { return []; });
        }

        var Answer = (new Question(Cells.reduce(function(prev, row) {
            return prev.concat(row);
        }))).Solve(Condition);

実際に解いてみると、簡単な問題なら一瞬で解けるが、難易度が上がると試行回数が跳ね上がってむちゃくちゃ時間がかかるようになる。
この辺はスクリプトの限界なのか、それとも工夫すればもっと速くなるのか。。。