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);

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

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

前回の続きで、塗り分けの時にモナド的に書きたいなと言っていたところを、無い知恵を絞ってモナドもどきを作ってみた。

        var Result = {
            False: {
                bind: function() {
                    return this;
                },
                get: function() {
                    return false;
                }
            },
            True: {
                bind: function(f) {
                    return f();
                },
                get: function() {
                    return true;
                }
            },
            Undefined: {
                bind: function(f) {
                    var result = f();
                    if(result.get() === false) {
                        return result;
                    }
                    return Result.Undefined;
                },
                get: function() {
                    return undefined;
                }
            }
        }

これを使うと、「与えられた要素が全て互いに異なる」という条件はこう書ける。
モナドを使いつつも、あまり関数型っぽくない書き方だが、実行効率を踏まえつつハイブリッドなやり方と言うことで

        function AllNotEqual() {
            return allNotEqual(arguments, arguments.length-2);
        }
        function allNotEqual(items, iter) {
            var result = (function(j) {
                var callee = arguments.callee;
                if(j <= iter + 1) return NotEqual(items[iter], items[j]);
                return NotEqual(items[iter], items[j]).bind(function() { return callee(j-1); });
            })(items.length - 1);
            if(iter <= 0) {
                return result;
            }
            return result.bind(function() { return allNotEqual(items, iter-1); });
        }
        function NotEqual(x, y) {
            var tmp_x = x.get(), tmp_y = y.get();
            if(tmp_x === undefined || tmp_y === undefined)
                return Result.Undefined;
            if(tmp_x != tmp_y)
                return Result.True;
            return Result.False;
        }

Sudoku の条件である、「各行、各列、各3x3のブロックで同じ数字を使わない」は、関数型言語の勉強の時に作った do 記法もどきを利用してこう書ける。
ちとながいが、よく見れば単にルールをべた書きしただけの記述。

        var MonaDo = function(fs) {
            var monado = function(funcs) {
                if(funcs.length > 1) {
                    var inner = monado(funcs.slice(1));
                    return function(a) {
                        return funcs[0](a).bind(inner);
                    }
                }
                return funcs[0];
            }
            return monado(fs)();
        }

        function RowNotEqual(cells, row) {
            return AllNotEqual.apply(this, cells[row]);
        }
        function ColNotEqual(cells, col) {
            return AllNotEqual.apply(this, cells.map(function(row) {
                return row[col];
            }));
        }
        function BlkNotEqual(cells, row, col) {
            return AllNotEqual(
                cells[row][col],  cells[row][col+1],  cells[row][col+2],
                cells[row+1][col],cells[row+1][col+1],cells[row+1][col+2],
                cells[row+2][col],cells[row+2][col+1],cells[row+2][col+2]);
        }
        var Condition = function() {
            return MonaDo([
                function() {return RowNotEqual(Cells, 0); },
                function() {return RowNotEqual(Cells, 1); },
                function() {return RowNotEqual(Cells, 2); },
                function() {return RowNotEqual(Cells, 3); },
                function() {return RowNotEqual(Cells, 4); },
                function() {return RowNotEqual(Cells, 5); },
                function() {return RowNotEqual(Cells, 6); },
                function() {return RowNotEqual(Cells, 7); },
                function() {return RowNotEqual(Cells, 8); },
                function() {return ColNotEqual(Cells, 0); },
                function() {return ColNotEqual(Cells, 1); },
                function() {return ColNotEqual(Cells, 2); },
                function() {return ColNotEqual(Cells, 3); },
                function() {return ColNotEqual(Cells, 4); },
                function() {return ColNotEqual(Cells, 5); },
                function() {return ColNotEqual(Cells, 6); },
                function() {return ColNotEqual(Cells, 7); },
                function() {return ColNotEqual(Cells, 8); },
                function() {return BlkNotEqual(Cells, 0, 0); },
                function() {return BlkNotEqual(Cells, 0, 3); },
                function() {return BlkNotEqual(Cells, 0, 6); },
                function() {return BlkNotEqual(Cells, 3, 0); },
                function() {return BlkNotEqual(Cells, 3, 3); },
                function() {return BlkNotEqual(Cells, 3, 6); },
                function() {return BlkNotEqual(Cells, 6, 0); },
                function() {return BlkNotEqual(Cells, 6, 3); },
                function() {return BlkNotEqual(Cells, 6, 6); }
            ]).get()
        };

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

こないだ塗り分け問題を解く JavaScript を書いてみたが、同じ原理で Sudoku も解けるんじゃないかと思ってコードを改良しつつやってみた。

Sudoku の場合は初期状態で値が決まっているセルと決まっていないセルがあるので、これを表現するために、Obvious と Ambiguous という二つのクラスを作成した。

        function Ambiguous(candidates) {
            this.candidates = candidates;
            this.selected = undefined;
        }
        Ambiguous.prototype = {
            get: function() {
                return this.selected;
            },
            selectEach: function(callback) {
                this.candidates.forEach(function(item) {
                    this.selected = item;
                    callback();
                }.bind(this));
                this.selected = undefined;
            },
        }
        function Obvious(value) {
            this.value = value;
        }
        Obvious.prototype = {
            get: function() {
                return this.value;
            },
            selectEach: function(callback) {
                callback();
            }
        }

長くなるのでヘルパーを使いつつ、どっかから探してきた Sudoku の問題を表現するとこうなる。

        var Nine = [1, 2, 3, 4, 5, 6, 7, 8, 9];
        function createRow(args) {
            return args.map(function(item) {
                if(Array.isArray(item)) return new Ambiguous(item);
                return new Obvious(item);
            });
        }
        var Cells = [
            createRow([Nine, Nine,    8, Nine,    9, Nine, Nine, Nine, Nine]),
            createRow([   9, Nine, Nine, Nine,    3, Nine, Nine, Nine,    1]),
            createRow([   6,    2, Nine, Nine,    4,    7, Nine,    8, Nine]),
            createRow([Nine, Nine,    7, Nine, Nine, Nine,    1,    9, Nine]),
            createRow([   1,    3, Nine,    4,    7, Nine,    2,    5,    8]),
            createRow([   5, Nine, Nine,    8,    2, Nine,    3,    6, Nine]),
            createRow([   3,    6,    1,    7, Nine,    4,    8,    2, Nine]),
            createRow([Nine,    5,    2,    9,    1, Nine,    4,    7,    6]),
            createRow([Nine,    9,    4,    6, Nine, Nine,    5, Nine,    3])
        ];

インデントは気にしない

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

前回で総当たり方式についてコードを一般化出来たところで、今度はこれに枝刈りを導入して動作の効率化を図る。

枝刈りというのは、要は全てのタイルの色を設定した後で全ての条件に合致するかを判断するのではなく、1枚ずつタイルの色を設定しながら、現時点で条件を満たさないことが判明したらその先の試行をやめて違う組み合わせを試すというものになる。

そのためには、それぞれの条件に対して判断に必要なタイルを明記する必要がある。

        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 = [
            { require: [tile1, tile2], func: function() { return tile1.selected != tile2.selected; } },
            { require: [tile1, tile3], func: function() { return tile1.selected != tile3.selected; } },
            { require: [tile1, tile4], func: function() { return tile1.selected != tile4.selected; } },
            { require: [tile1, tile5], func: function() { return tile1.selected != tile5.selected; } },
            { require: [tile2, tile3], func: function() { return tile2.selected != tile3.selected; } },
            { require: [tile3, tile5], func: function() { return tile3.selected != tile5.selected; } },
            { require: [tile4, tile5], func: function() { return tile4.selected != tile5.selected; } },
            { require: [tile4, tile2], func: function() { return tile4.selected != tile2.selected; } }
        ];

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

各条件を判定するときには、require で示されたタイルの色が設定されているかをチェックして、設定されていない場合は undefined を返すようにする。

        function checkOne(question, cond) {
            var i;
            for(i = 0; i < cond.require.length; i++) {
                if(cond.require[i].selected === undefined) {
                    return undefined;
                }
            }
            return cond.func();
        }

あとは、
複数の条件のうち、一つでも条件を満たさない場合はその先の試行は行わない。
全ての条件を満たせばそれが回答の一つになる。
それ以外(undefinedが混じる場合)は次のタイルの色を設定してもう一度条件を確認する。
というのを行っていけばよい。

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

        function check(question, conditions) {
            var i,
                tmp,
                result = true;
            for(i = 0; i < conditions.length; i++) {
                tmp = checkOne(question, conditions[i]);
                if(tmp === false) return false;
                else if(tmp === undefined) result = undefined;
            }
            return result;
        }

こうすれば、メンテナンス性を維持しつつも、枝刈りにより高速に処理が出来る。

check や checkOne の戻り値をチェックして処理内容を変えるところなんかは、関数型言語で勉強したモナド的なやり方を導入するともう少しスマートに書けそうな気がするのだが、一からモナドを設計するのは自分の脳みそじゃ無理そうだ。

塗り分け問題を JavaScript で書いてみた結論としては、

　　prologで良いじゃん

の一言に尽きる。

というか、prolog 向きの問題だと言うことはハナからわかっていたが、JavaScript で書いたらもう少しオブジェクト指向的なアプローチが出来るかなと思って色々試行錯誤してみたのたが、結局は一般化しようとしたら prolog っぽい書き方をするのが一番良いよねということになってしまった。
強いて言えば、require と selected をもう少しスマートに表現できるようにしたかったなぁ。

まあ、こんなことは先人たちがさんざん試してるので今更なんだろうが、勉強には良いよね。

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 の全ての組み合わせを総当たりで試しているだけ。

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

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

前回の続き。

さすがに総当たりだと単純すぎるので、いわゆる枝刈りして余計な試行を削っていく。

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

colors.forEach(function(tile1) {
    colors.forEach(function(tile2) {
        if(tile1 != tile2) {
            colors.forEach(function(tile3) {
                if(tile1 != tile3 && tile2 != tile3) {
                    colors.forEach(function(tile4) {
                        if(tile1 != tile4 && tile3 != tile4) {
                            colors.forEach(function(tile5) {
                                if(tile1 != tile5 && tile4 != tile5 && tile2 != tile5) {
                                    document.write(tile1+', '
                                        +tile2+', '
                                        +tile3+', '
                                        +tile4+', '
                                        +tile5+'<br>');
                                }
                            });
                        }
                    });
                }
            });
        }
    });
});

たしかにこれで速くはなるのだが、いかんせんメンテナンス性がすこぶる悪い。
タイルを一枚増やしたり、条件を変更しようとするとあっちゃこっちゃ変えなくちゃならない。

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

以前なんかで見かけて、暇があったら勉強がてら JavaScript で書いてみようと思っていたプログラム。
いわゆる塗り分け問題で、細かいところは覚えていないが、とりあえず適当に下のような5枚のタイルを同じ色が隣接しないように赤青黄緑の4色で塗り分ける問題を解いてみる。

まずは何も考えずに愚直に書くとこうなる

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

var i, j, k, l, m;
var tile1, tile2, tile3, tile4, tile5;
for(i = 0; i < colors.length; i++) {
    tile1 = colors[i];
    for(j = 0; j < colors.length; j++) {
        tile2 = colors[j];
        for(k = 0; k < colors.length; k++) {
            tile3 = colors[k];
            for(l = 0; l < colors.length; l++) {
                tile4 = colors[l];
                for(m = 0; m < colors.length; m++) {
                    tile5 = colors[m];
                    if(tile1 != tile2
                       && tile1 != tile3
                       && tile1 != tile4
                       && tile1 != tile5
                       && tile2 != tile3
                       && tile3 != tile5
                       && tile5 != tile4
                       && tile4 != tile2) {
                        document.write(tile1+', '
                                       +tile2+', '
                                       +tile3+', '
                                       +tile4+', '
                                       +tile5+'<br>');
                    }
                }
            }
        }
    }
}

これでも解けることは解けるが、タイル数(N)が増えると試行回数が4(色数)のN乗で増えていくので、こんなんを大学の専攻のレポートで提出したら確実に赤点食らうだろう。

蛇足だが、forEachを使うと若干シンプルに書ける。

var colors = ['red', 'blue', 'green', 'yellow'];
var begin = Date.now();
colors.forEach(function(tile1) {
    colors.forEach(function(tile2) {
        colors.forEach(function(tile3) {
            colors.forEach(function(tile4) {
                colors.forEach(function(tile5) {
                    if(tile1 != tile2
                       && tile1 != tile3
                       && tile1 != tile4
                       && tile1 != tile5
                       && tile2 != tile3
                       && tile3 != tile5
                       && tile5 != tile4
                       && tile4 != tile2) {
                        document.write(tile1+', '
                                       +tile2+', '
                                       +tile3+', '
                                       +tile4+', '
                                       +tile5+'<br>');
                    }
                });
            });
        });
    });
});

もっとも、シンプルに書けるだけで中身は変わらないので、まともにしようと思ったら工夫が必要になる。