Javascript で塗り分け問題を解いてみる (3)

前回は効率性を重視するあまりメンテナンス性がおろそかになってしまった。
メンテナンス性を良くするために、解き方はもとの総当たりに戻すとして、一旦命題を整理してみる。

今回の命題を言葉で書くと
「タイル1～5までの5枚のタイルがある」
「それぞれのタイルには赤、青、緑、黄のどれかの色が塗られる」
「"条件"に合致するタイルの色の組み合わせは何か」
のということになる。

これをそのままコードで書くとこのように書ける。

        var Colors = ['red', 'blue', 'green', 'yellow'];

        var tile1 = { candidates: Colors, selected: undefined };
        var tile2 = { candidates: Colors, selected: undefined };
        var tile3 = { candidates: Colors, selected: undefined };
        var tile4 = { candidates: Colors, selected: undefined };
        var tile5 = { candidates: Colors, selected: undefined };

        var Conditions = [
            function() { return tile1.selected != tile2.selected; },
            function() { return tile1.selected != tile3.selected; },
            function() { return tile1.selected != tile4.selected; },
            function() { return tile1.selected != tile5.selected; },
            function() { return tile2.selected != tile3.selected; },
            function() { return tile3.selected != tile5.selected; },
            function() { return tile4.selected != tile5.selected; },
            function() { return tile4.selected != tile2.selected; }
        ];

        var Question = [tile1, tile2, tile3, tile4, tile5];

命題をコードで書けるのなら、それをそのまま解けば良い。

        function solve(question, conditions, iter) {
            if(iter === undefined) iter = 0;
            else if(iter >= question.length) {
                if(conditions.every(function(condition) { return condition(); })) {
                    return [question.map(function(tile) { return tile.selected; })];
                }
                return [];
            }
            var answer = [];
            question[iter].candidates.forEach(function(item) {
                question[iter].selected = item;
                answer = answer.concat(solve(question, conditions, iter+1));
            });
            return answer;
        }

        var Answer = solve(Question, Conditions);

さらっと無茶なことをやっているようにも見えるが、実際は question で与えられた tile1 ～ tile5 に対して再起を使って candidate の全ての組み合わせを総当たりで試しているだけ。

こうしてしまえば、タイルの数が増えようが、条件が変わろうが容易に対応できる。