Cマガ電脳クラブ(第008回) ネイバーズ

問題

ガラスの円盤に縦4×横4、合計16個のまるいクボミがあり、
その底にはどこも赤、黄、青、白、黒のどれかの色で縫ってある(Fig.1)。

周囲のトレンチには、色つきのビー玉が16個 (赤3個、青3個、黄3個、黒3個、白4個) 入っている。
すべてのビー玉を1個ずつクボミに置けば完成なのだが、置き方に以下の制約がある。
 1：玉と同じ色のクボミには置けない。
 2：玉と同じ色のクボミのトナリには置けない。この場合、45度方向のトナリも含まれる。
 3：ビー玉を置いたら、以降そのクボミの色は置かれた玉の色に変わる。

つまりあるクボミに、ある色のビー玉がいま置けなくても
「周囲にほかのビー玉が置かれて、その場所の色が変われば」置けるようになる順序が問題なのである。
最終的な盤の配色が同じでも、それに至る道筋は何通りもあるだろう。

しかし今回は仕上げの配色だけを問題にする。仕上げの配色には何通りあるか。
それぞれの仕上がり図と、それに至る道筋を1通りだけ例として添えていただきたい。

Fig.1
青  黒  白  黄
黄  赤  青  黒
白  黒  白  黄
赤  青  赤  青

ソース

<?php error_reporting(E_ALL);

define('UB', 4 - 1 );

class JyoutaiDef
{
    public $BanArr;
    public $AlreadyHaitiArr;
    public $RestList;
    public $BanLog;
    public $OpeLog;
}

$WillPush = new JyoutaiDef();

$wkBan = [['青','黒','白','黄'],
          ['黄','赤','青','黒'],
          ['白','黒','白','黄'],
          ['赤','青','赤','青']];
//X座標とY座標を変換してセット
$WillPush->BanArr = array();
for ($X = 0; $X <= UB; $X++) {
    for ($Y = 0; $Y <= UB; $Y++) {
        $WillPush->BanArr[$X][$Y] = $wkBan[$Y][$X];
    }
}

$WillPush->AlreadyHaitiArr = CreateBoolArr();

$WillPush->RestList = array();
for($I = 1; $I <= 3 ; $I++) $WillPush->RestList[] = '赤';
for($I = 1; $I <= 3 ; $I++) $WillPush->RestList[] = '青';
for($I = 1; $I <= 3 ; $I++) $WillPush->RestList[] = '黄';
for($I = 1; $I <= 3 ; $I++) $WillPush->RestList[] = '黒';
for($I = 1; $I <= 4 ; $I++) $WillPush->RestList[] = '白';

$WillPush->BanLog = array();
$WillPush->OpeLog = array();

$Stk = new SplStack();
$Stk->push($WillPush);

$AnswerBanList = array();
$AnswerCnt = 0;

$VisitedSet = array();

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

    if (count($Popped->RestList) == 0) {
        $AnswerBanList[] = $Popped->BanArr;
        printf('解%dを発見しました' . PHP_EOL , ++$AnswerCnt);

        for ($I = 0; $I <= count($Popped->BanLog) - 1; $I++) {
            printf('%d手目は %s' . PHP_EOL , $I + 1 , $Popped->OpeLog[$I]);
            PrintBan($Popped->BanLog[$I]);
        }
        continue;
    }

    foreach(array_unique($Popped->RestList) as $HaitiColor){
        for ($X = 0; $X <= UB; $X++) {
            for ($Y = 0; $Y <= UB; $Y++) {
                if ($Popped->AlreadyHaitiArr[$X][$Y]) continue;

                if (CanHaiti($X, $Y, $Popped->BanArr, $HaitiColor) == false) continue;

                $WillPush = new JyoutaiDef();

                $WillPush->BanArr = $Popped->BanArr;
                $WillPush->BanArr[$X][$Y] = $HaitiColor;

                $WillPush->AlreadyHaitiArr = $Popped->AlreadyHaitiArr;
                $WillPush->AlreadyHaitiArr[$X][$Y] = true;

                $WillPush->RestList = $Popped->RestList;
                $ind = array_search($HaitiColor,$WillPush->RestList);
                unset($WillPush->RestList[$ind]);

                $WillPush->BanLog = $Popped->BanLog;
                $WillPush->BanLog[] = $WillPush->BanArr;

                $WillPush->OpeLog = $Popped->OpeLog;
                $WillPush->OpeLog[] = sprintf('[%d,%d]に%sを配置。%s'
                                              ,$X, $Y, $HaitiColor, DeriveRestLog($WillPush->RestList));

                $Hash = GetHash($WillPush->BanArr, $WillPush->AlreadyHaitiArr);
                if(in_array($Hash,$VisitedSet) == false){
                    $VisitedSet[] = $Hash;
                    $Stk->Push($WillPush);
                }
            }
        }
    }
}

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

function CanHaiti($pX , $pY , array $pBanArr , $pHaitiColor)
{
    for ($X = 0; $X <= UB; $X++) {
        for ($Y = 0; $Y <= UB; $Y++) {
            if (abs($pX - $X) > 1 || abs($pY - $Y) > 1) continue;
            if ($pBanArr[$X][$Y] == $pHaitiColor) return false;
        }
    }
    return true;
}

function DeriveRestLog( array $pRestList)
{
    $WillReturn = '残りは';
    $WillReturn .= sprintf('赤%d,', count(array_keys($pRestList , '赤')));
    $WillReturn .= sprintf('青%d,', count(array_keys($pRestList , '青')));
    $WillReturn .= sprintf('黄%d,', count(array_keys($pRestList , '黄')));
    $WillReturn .= sprintf('黒%d,', count(array_keys($pRestList , '黒')));
    $WillReturn .= sprintf('白%d,', count(array_keys($pRestList , '白')));
    return $WillReturn;
}

function GetHash( array $pBanArr , array $pAlreadyHaitiArr )
{
    $WillReturn = '';
    for ($X = 0; $X <= UB; $X++) {
        for ($Y = 0; $Y <= UB; $Y++) {
            $WillReturn .= $pBanArr[$X][$Y];
            $WillReturn .= ($pAlreadyHaitiArr[$X][$Y] ? '0' : '1');
        }
    }
    return $WillReturn;
}

function PrintBan( array $pBanArr)
{
    for ($Y = 0; $Y <= UB; $Y++) {
        for ($X = 0; $X <= UB; $X++) {
            echo $pBanArr[$X][$Y];
        }
        echo PHP_EOL;
    }
    echo PHP_EOL;
}

実行結果

解1を発見しました
1手目は [0,0]に白を配置。残りは赤3,青3,黄3,黒3,白3,
白黒白黄
黄赤青黒
白黒白黄
赤青赤青

2手目は [0,1]に青を配置。残りは赤3,青2,黄3,黒3,白3,
白黒白黄
青赤青黒
白黒白黄
赤青赤青

3手目は [1,2]に黄を配置。残りは赤3,青2,黄2,黒3,白3,
白黒白黄
青赤青黒
白黄白黄
赤青赤青

4手目は [2,3]に黒を配置。残りは赤3,青2,黄2,黒2,白3,
白黒白黄
青赤青黒
白黄白黄
赤青黒青

5手目は [0,3]に黒を配置。残りは赤3,青2,黄2,黒1,白3,
白黒白黄
青赤青黒
白黄白黄
黒青黒青

6手目は [1,0]に黄を配置。残りは赤3,青2,黄1,黒1,白3,
白黄白黄
青赤青黒
白黄白黄
黒青黒青

7手目は [1,1]に黒を配置。残りは赤3,青2,黄1,黒0,白3,
白黄白黄
青黒青黒
白黄白黄
黒青黒青

8手目は [2,2]に赤を配置。残りは赤2,青2,黄1,黒0,白3,
白黄白黄
青黒青黒
白黄赤黄
黒青黒青

9手目は [3,3]に白を配置。残りは赤2,青2,黄1,黒0,白2,
白黄白黄
青黒青黒
白黄赤黄
黒青黒白

10手目は [2,0]に赤を配置。残りは赤1,青2,黄1,黒0,白2,
白黄赤黄
青黒青黒
白黄赤黄
黒青黒白

11手目は [2,1]に白を配置。残りは赤1,青2,黄1,黒0,白1,
白黄赤黄
青黒白黒
白黄赤黄
黒青黒白

12手目は [3,2]に青を配置。残りは赤1,青1,黄1,黒0,白1,
白黄赤黄
青黒白黒
白黄赤青
黒青黒白

13手目は [3,0]に青を配置。残りは赤1,青0,黄1,黒0,白1,
白黄赤青
青黒白黒
白黄赤青
黒青黒白

14手目は [3,1]に黄を配置。残りは赤1,青0,黄0,黒0,白1,
白黄赤青
青黒白黄
白黄赤青
黒青黒白

15手目は [0,2]に赤を配置。残りは赤0,青0,黄0,黒0,白1,
白黄赤青
青黒白黄
赤黄赤青
黒青黒白

16手目は [1,3]に白を配置。残りは赤0,青0,黄0,黒0,白0,
白黄赤青
青黒白黄
赤黄赤青
黒白黒白

解説

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

C#で解いたもの