Q43 隣り合えないカップル

JavaScriptのソース

Solve(3);
Solve(7);

//コンストラクタ
function JyoutaiDef()
{
    this.CurrInd = 0;
    this.BanArr = new Array();
}

function Solve(pN)
{
    const UB = pN * 2 - 1;

    var Stk = new Array();
    var WillPush = new JyoutaiDef();
    WillPush.CurrInd = 1;
    WillPush.BanArr = new Array(UB + 1).fill(0);
    WillPush.BanArr[0] = 1; //最初だけ位置を固定
    Stk.push(WillPush);
   
    var Answer = 0;

    while(Stk.length > 0){
        var Poped = Stk.pop();

        //クリア判定
        if(UB < Poped.CurrInd){
            Answer++;
            //document.write('解を発見 ' , JSON.stringify(Poped.BanArr) , '<br>');
            continue;
        }

        //使用済み数字のSet
        var NumSet = new Array();
        for(var I = Poped.CurrInd - 2 ; 0 <= I ; I -= 2 ){
            NumSet.push(Poped.BanArr[I]);
        }

        for(var I = 1 ; I <= pN ; I++){
            //使用済み数値は不可
            if (NumSet.indexOf(I) >= 0) continue;

            //同じ数字と隣接していたらNG
            if (0 < Poped.CurrInd && Poped.BanArr[Poped.CurrInd - 1] == I) continue;
            if (Poped.CurrInd == UB && Poped.BanArr[0] == I) continue;

            WillPush = new JyoutaiDef();
            WillPush.CurrInd = Poped.CurrInd + 1;
            WillPush.BanArr = Poped.BanArr.concat();
            WillPush.BanArr[Poped.CurrInd] = I;
            Stk.push(WillPush);
        }
    }
    document.write(pN , '人だと、' , Answer , '通り<br>');
}

実行結果

3人だと、2通り
7人だと、416880通り

解説

深さ優先探索で解いてます。