トップページに戻る    次のPHPのサンプルへ    前のPHPのサンプルへ

Cマガ電脳クラブ(第004回) カードの間には

問題

ここに1から7の数字を書いたカードが2枚ずつ、計14枚ある。
そしてこれをFig.1のように1列に並べた。

この図をよく見ると、2枚の「1」の間にはカードが1枚、2枚の「2」の間にはカードが2枚はさまれている。
同様に、「3」の間には3枚、「4」の間には4枚、「5」の間には5枚、「6」の間には6枚、
そして「7」の間には7枚のカードがはさまれている。
では、この14枚を使ってこのような並べ方は何通りできるだろうか。
ただし、左右対称の解は除くこととする。

Fig.1
41716425327635


ソース

<?php error_reporting(E_ALL);
const UB = 13;
$Stk = new SplStack();
$Stk->push(array_fill(0,UB + 1 ,0));

$AnsCnt = 0;
while($Stk->isEmpty() == false){
    $Popped = $Stk->pop();

    $MaxVal = max($Popped);
    if ($MaxVal == 7) {
        printf('Answer%2dは、' , ++$AnsCnt);
        foreach($Popped as $X) echo $X;
        echo PHP_EOL;
        continue;
    }
    $FillVal = $MaxVal + 1;
    for ( $I = 0; $I <= UB ; $I++) {
        //左右対称の解を除外(6と7の間の6.5が対称線)
        if ($FillVal == 1 && $I < (UB - UB % 2) / 2) continue;

        if ($Popped[$I] == 0){
            $SecondPos = $I + $FillVal + 1;

            if($SecondPos <= UB && $Popped[$SecondPos] == 0){
                $WillPush = $Popped;
                $WillPush[$I] = $WillPush[$SecondPos] = $FillVal;
                $Stk->push($WillPush);
            }
        }
    }
}


実行結果

Answer 1は、46357432652171
Answer 2は、53647352462171
Answer 3は、35743625427161
Answer 4は、37463254276151
Answer 5は、73625324765141
Answer 6は、57263254376141
Answer 7は、72452634753161
Answer 8は、62742356437151
Answer 9は、72462354736151
Answer10は、72632453764151
Answer11は、34673245261715
Answer12は、53672352461714
Answer13は、57236253471614
Answer14は、52642753461317
Answer15は、25623745361417
Answer16は、27423564371516
Answer17は、35723625417164
Answer18は、52462754316137
Answer19は、52732653417164
Answer20は、24723645317165
Answer21は、26325734615147
Answer22は、26327435614175
Answer23は、52472654131763
Answer24は、23627345161475
Answer25は、34573641512762
Answer26は、23726351417654


解説

深さ優先探索でカードを並べてます。

C#で解いたもの