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

Cマガ電脳クラブ(第005回) コインの距離

問題

Fig.1のように、格子の上にコインを4個置く。ひとつの格子間の距離を1とすると
AB=ルート(17)
AC=3*ルート(2)
AD=5
BC=ルート(5)
BD=ルート(10)
CD=1
となり、すべてのコインの中心間の距離が異なっている。

では、Fig.2の格子の上に6個のコインをFig.1と同じ条件で置くには、どのようにしたらよいだろう。

もちろん、コインを重ねてはいけない。
回転や裏返しは別の解とはせずに同じものとみなすとすると、全部で何通りの置き方があるだろうか。

Fig.1               Fig.2
A--+--+--+--+       +--+--+--+--+--+
|  |  |  |  |       |  |  |  |  |  |
+--+--+--+--+       +--+--+--+--+--+
|  |  |  |  |       |  |  |  |  |  |
+--+--+--+--+       +--+--+--+--+--+
|  |  |  |  |       |  |  |  |  |  |
+--+--+--C--D       +--+--+--+--+--+
|  |  |  |  |       |  |  |  |  |  |
+--B--+--+--+       +--+--+--+--+--+
                    |  |  |  |  |  |
                    +--+--+--+--+--+


ソース

<?php error_reporting(E_ALL);

//const Haba = 5;const OKCnt = 4;
const Haba = 6; const OKCnt = 6;

class JyoutaiDef
{
    public $CurrX;
    public $CurrY;
    public $HaitiArr;
    public $HaitiCnt;
    public $KyouriSet;
}

$Stk = new SplStack();

for ($X = 0; $X <= Haba - 1; $X++) {
    for ($Y = 0; $Y <= Haba - 1; $Y++) {
        $WillPush = new JyoutaiDef();
        $WillPush->CurrX = $X;
        $WillPush->CurrY = $Y;
        $WillPush->HaitiArr = CreateBoolArr();
        $WillPush->HaitiArr[$X][$Y] = true;
        $WillPush->HaitiCnt = 1;
        $WillPush->KyouriSet = array();
        $Stk->push($WillPush);
    }
}
$AnswerHaitiList = array();

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

    if ($Popped->HaitiCnt == OKCnt) {
        //if (in_array(17     ,$Popped->KyouriSet) == false) continue;
        //if (in_array( 9 * 2 ,$Popped->KyouriSet) == false) continue;
        //if (in_array(25     ,$Popped->KyouriSet) == false) continue;
        //if (in_array( 5     ,$Popped->KyouriSet) == false) continue;
        //if (in_array(10     ,$Popped->KyouriSet) == false) continue;
        //if (in_array( 1     ,$Popped->KyouriSet) == false) continue;
        $AnswerHaitiList[] = $Popped->HaitiArr;
        continue;
    }

    if (++$Popped->CurrY > Haba - 1) {
        $Popped->CurrX++;
        $Popped->CurrY = 0;
    }

    for ($X = $Popped->CurrX; $X <= Haba - 1; $X++) {
        for ($Y = $Popped->CurrY; $Y <= Haba - 1; $Y++) {
            $WillPush = new JyoutaiDef();
            $WillPush->CurrX = $X;
            $WillPush->CurrY = $Y;
            $WillPush->KyouriSet = $Popped->KyouriSet;
            if(AddCalcKyouri($X , $Y , $Popped->HaitiArr , $WillPush->KyouriSet)){
                $WillPush->HaitiArr = $Popped->HaitiArr;
                $WillPush->HaitiArr[$X][$Y] = true;
                $WillPush->HaitiCnt = $Popped->HaitiCnt + 1;
                $Stk->push($WillPush);
            }
        }
    }
}
RemoveKaitenKai($AnswerHaitiList);
for($I=0;$I<= count($AnswerHaitiList)-1;$I++){
    printf("解%d",$I + 1);
    echo PHP_EOL;
    PrintJyoutai($AnswerHaitiList[$I]);
    echo PHP_EOL;
}

//2次元配列を作って返す
function CreateBoolArr()
{
    $WillReturn = array();
    for ($I = 0; $I <= Haba - 1; $I++) {
        $WillReturn[$I] = array();
        for ($J = 0; $J <= Haba - 1; $J++) {
            $WillReturn[$I][$J] = false;
        }
    }
    return $WillReturn;
}

function AddCalcKyouri($pX , $pY , array $pSetArr , array &$pKyouriSet)
{
    for ($X = 0; $X <= Haba - 1; $X++) {
        for ($Y = 0; $Y <= Haba - 1; $Y++) {
            if($pSetArr[$X][$Y]){
                $CurrKyori = ($X - $pX) * ($X - $pX) + ($Y - $pY) * ($Y - $pY);
                if(in_array($CurrKyori, $pKyouriSet)) return false;
                $pKyouriSet[] = $CurrKyori;
            }
        }
    }
    return true;
}

//回転した解を除外
function RemoveKaitenKai( array &$pAnswerSetList)
{
    define('UB', Haba - 1);

    $IsExist = function($pCurrInd,array &$pAnswerSetList){
        for ($I = 0; $I <= $pCurrInd - 1; $I++) {
            $IsOK1 = $IsOK2 = $IsOK3 = $IsOK4 = false;
            $IsOK5 = $IsOK6 = $IsOK7 = false; //回転1から7

            for ($X = 0; $X <= UB; $X++) {
                for ($Y = 0; $Y <= UB; $Y++) {
                    $CurrVal = $pAnswerSetList[$pCurrInd][$X][$Y];
                    if ($pAnswerSetList[$I][UB - $X][$Y] != $CurrVal) $IsOK1 = true;
                    if ($pAnswerSetList[$I][UB - $X][UB - $Y] != $CurrVal) $IsOK2 = true;
                    if ($pAnswerSetList[$I][$X][UB - $Y] != $CurrVal) $IsOK3 = true;
                    if ($pAnswerSetList[$I][$Y][$X] != $CurrVal) $IsOK4 = true;
                    if ($pAnswerSetList[$I][UB - $Y][$X] != $CurrVal) $IsOK5 = true;
                    if ($pAnswerSetList[$I][UB - $Y][UB - $X] != $CurrVal) $IsOK6 = true;
                    if ($pAnswerSetList[$I][$Y][UB - $X] != $CurrVal) $IsOK7 = true;
                }
            }
            if ($IsOK1 == false || $IsOK2 == false || $IsOK3 == false || $IsOK4 == false
             || $IsOK5 == false || $IsOK6 == false || $IsOK7 == false)
                return true;
        }
        return false;
    };

    for ($I = count($pAnswerSetList) - 1; $I >= 0; $I--) {
        if ($IsExist($I,$pAnswerSetList)) unset($pAnswerSetList[$I]);
    }
    $pAnswerSetList = array_values($pAnswerSetList);
}

//盤面を表示
function PrintJyoutai( array $pHaitiArr)
{
    $wkChar = 'A';

    for ($X = 0; $X <= Haba - 1; $X++) {
        for ($Y = 0; $Y <= Haba - 1; $Y++) {
            if ($pHaitiArr[$X][$Y]) {
                echo $wkChar++;
            }
            else{
                echo '+';
            }
            if($Y < Haba - 1) echo '-';
        }
        echo PHP_EOL;
        if ($X == Haba - 1) return;
        for ($Y = 0; $Y <= Haba - 1; $Y++) {
            if ($Y < Haba - 1) echo '| ';
            else echo '|' . PHP_EOL;
        }
    }
}


実行結果

解1
+-+-+-+-+-A
| | | | | |
B-C-+-+-+-+
| | | | | |
+-+-D-+-+-+
| | | | | |
+-+-+-+-+-E
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-F

解2
A-B-+-+-+-+
| | | | | |
+-+-+-C-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-D
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-E-+-+-F


解説

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

C#で解いたもの