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

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