N-Queen

n-queen プログラム (2005/7/5; KCH対象特別授業参考資料)

<title>n-queen</title>
<script type="text/javascript">
<!--
var n     = 4,      // 盤面のサイズ
    dfs   = true,   // 縦型探索かどうか
    cut   = true,   // 枝刈りをするかどうか (n=8 なら false にしない方が良い)
    all   = false,  // 全解を探索するかどうか
    count = 0;      // 探索した盤面を数える変数

var seq = [[]];     // 盤面の列 (初期値: () のみのリスト)

function appendToSeq(lst) {     // seq に (盤面のリスト) lst を追加
    seq = lst.concat(seq);      // 左端に追加
}

function getFromSeq() {         // seq から (盤面を) 1つ取り出す
    if (dfs) return seq.shift();// 左端から
    else return seq.pop();      // 右端から
}

function isSolution(stat) {     // 盤面 stat が解かどうか
    return stat.length==n && isValid(stat);
}

function children(stat) {       // 盤面 stat の次の盤面のリスト
    var r = [];
    if (stat.length >= n) return r;
    for (var i=1; i<=n; i++) r.push([i].concat(stat));
    return r;
}

for (;;) {
    if (seq.length==0) break;   // seq が空なら終了
    var x = getFromSeq();       // seq から1つ取り出して x に入れる
    count++;                    // count を1増やす
    if (isSolution(x)) {        // x が解なら表示して終了または続行
        document.writeln('(' + x.join(',') + ')<br>');
        if (!all) break;
        else continue;
    }
    // x が妥当なら，その次の盤面のリストを seq に追加
    if (isValid(x) || !cut) appendToSeq(children(x));
}
document.writeln('Total: ' + count + '<br>');

// -->
</script>

当日のPowerPointのファイル