難易度の高い問題では、候補値から選んだ数字を仮の確定値として解法を適用することで、解答を探します。プログラムは次のようになります。二つの関数 GetCandidates、TestCandidate が追加されました。前からあった関数 PrintGridState、DupIndex、Reduce に引数 $grid が追加されました。まずはコードを読んでみてください。

渋沢栄一 近代の創造

数独パズルを解く。
<?php
// 数独パズルを解く。
define('GRIDSIZE', 81);
define('MAXANSWERS', 300);

$dt = '   13 9 2'
    . '7 8    3 '
    . '    6    '
    . '   2 6   '
    . '94       '
    . '3     5  '
    . '  9  1  3'
    . ' 7  8   6'
    . '  6  524 ';

// 同一の要素を許さない区画の定義
$region_set = array(
    array(0, 1, 2, 3, 4, 5, 6, 7, 8),           // 0
    array(9, 10, 11, 12, 13, 14, 15, 16, 17),   // 1
    array(18, 19, 20, 21, 22, 23, 24, 25, 26),  // 2
    array(27, 28, 29, 30, 31, 32, 33, 34, 35),  // 3
    array(36, 37, 38, 39, 40, 41, 42, 43, 44),  // 4
    array(45, 46, 47, 48, 49, 50, 51, 52, 53),  // 5
    array(54, 55, 56, 57, 58, 59, 60, 61, 62),  // 6
    array(63, 64, 65, 66, 67, 68, 69, 70, 71),  // 7
    array(72, 73, 74, 75, 76, 77, 78, 79, 80),  // 8
    array(0, 9, 18, 27, 36, 45, 54, 63, 72),    // 9
    array(1, 10, 19, 28, 37, 46, 55, 64, 73),   // 10
    array(2, 11, 20, 29, 38, 47, 56, 65, 74),   // 11
    array(3, 12, 21, 30, 39, 48, 57, 66, 75),   // 12
    array(4, 13, 22, 31, 40, 49, 58, 67, 76),   // 13
    array(5, 14, 23, 32, 41, 50, 59, 68, 77),   // 14
    array(6, 15, 24, 33, 42, 51, 60, 69, 78),   // 15
    array(7, 16, 25, 34, 43, 52, 61, 70, 79),   // 16
    array(8, 17, 26, 35, 44, 53, 62, 71, 80),   // 17
    array(0, 1, 2, 9, 10, 11, 18, 19, 20),      // 18
    array(3, 4, 5, 12, 13, 14, 21, 22, 23),     // 19
    array(6, 7, 8, 15, 16, 17, 24, 25, 26),     // 20
    array(27, 28, 29, 36, 37, 38, 45, 46, 47),  // 21
    array(30, 31, 32, 39, 40, 41, 48, 49, 50),  // 22
    array(33, 34, 35, 42, 43, 44, 51, 52, 53),  // 23
    array(54, 55, 56, 63, 64, 65, 72, 73, 74),  // 24
    array(57, 58, 59, 66, 67, 68, 75, 76, 77),  // 25
    array(60, 61, 62, 69, 70, 71, 78, 79, 80)); // 26

// 各マス目が属する区画を導き出す。
$rel_regions = array();

for($n = 0; $n < count($region_set); $n++)
{
    foreach($region_set[$n] as $ix)
    {
        if(isset($rel_regions[$ix]))
            $rel_regions[$ix][] = $n;
        else
            $rel_regions[$ix] = array($n);
    }
}

// 9x9のマス目に初期値を設定する。
$grid = array();
$fixed_count = 0;
for($n = 0; $n < GRIDSIZE; $n++)
{
    $c = substr($dt, $n, 1);
    if($c == ' ')
        $grid[$n] = '123456789';
    elseif(($dup_ix = DupIndex($grid, $n, $c)) != -1)
    {
        $xy1 = Coord($dup_ix);
        $xy2 = Coord($n);
        echo "$xy1=$xy2=$c: 初期値に重複\n";
        exit;
    }
    else
    {
        $grid[$n] = $c;
        $fixed_count++;
    }
}

try
{
    Reduce($grid, $fixed_count);
    if($fixed_count < GRIDSIZE)
    {
        $answer_count = 0;
        GetCandidates($grid, 0, $fixed_count);
        echo "解答数 $answer_count\n";
    }
    else
    {
        echo "解答\n";
        PrintGridState($grid);
    }
}
catch(Exception $e)
{
    $msg = $e->getMessage();
    echo " $msg\n\n";
}
exit;

function PrintGridState($grid)
{
    // 列幅を求める。
    $cw = array();
    for($col = 0; $col < 9; $col++)
    {
        $max = 0;
        for($n = $col; $n < GRIDSIZE; $n += 9)
        {
            $w = strlen($grid[$n]);
            if($w > $max)
                $max = $w;
        }

        $cw[$col] = $max;
    }

    // 全てのマス目の状態を表示する。
    $col = 0;
    $row = 0;
    $blk = 0;

    for($n = 0; $n < GRIDSIZE; $n++)
    {
        if($col == 0)
        {
            $row++;
            echo "$row ";
        }

        if(strlen($grid[$n]) == 1)
            echo $grid[$n];
        else
            echo "($grid[$n])";

        if($cw[$col] > 1)
        {
            $len = strlen($grid[$n]);
            if($len == 1)
                $len -= 2;

            echo str_repeat(' ', $cw[$col] - $len);
        }

        if(++$col == 9)
        {
            echo "\n";
            $col = 0;
            $blk = 0;
        }
        elseif(++$blk == 3)
        {
            echo ' ';
            $blk = 0;
        }
    }
}

function DupIndex($grid, $p, $num, $tested = -1)
{
    // ある位置($p)のマス目が属する区画に$numがあれば、
    // $numを持つマス目の添字を返す。
    global $region_set, $rel_regions;

    foreach($rel_regions[$p] as $ix)
    {
        if($ix == $tested)
            continue;

        foreach($region_set[$ix] as $n)
        {
            if(strlen($grid[$n]) == 1 && $grid[$n] == $num)
                return $n;
        }
    }

    return -1;
}

function Coord($n)
{
    $x = intval($n / 9) + 1;
    $y = $n % 9 + 1;
    return "($x,$y)";
}

function Reduce(&$grid, &$fixed_count)
{
    global $region_set;
    static $called = 0;
    $called++;

    // 各マス目の候補を消去する。
    $lp = 0;

    do
    {
        $reduced = false;

        ++$lp;
        echo "[$called-$lp]";

        for($ix = 0; $ix < count($region_set); $ix++)
        {
            foreach($region_set[$ix] as $e)
            {
                if(strlen($grid[$e]) != 1)
                    continue;

                // 確定値を持つマス目と同一区画のマス目について、
                // 確定値と同一の候補を取り除く。
                foreach($region_set[$ix] as $f)
                {
                    if(strlen($grid[$f]) == 1)
                        continue;

                    $str = str_replace($grid[$e], '', $grid[$f]);
                    if(strlen($str) == 1)
                    {
                        $xy = Coord($f);
                        $fixed_count++;
                        echo "f$fixed_count$xy=$str";

                        if(($dup_ix = DupIndex($grid, $f, $str)) != -1)
                            throw new Exception('Duplicate '
                                                . Coord($dup_ix));

                        $reduced = true;
                    }

                    $grid[$f] = $str;
                }
            } // foreach($region_set[$ix] as $e)

            $appearance = array();
            foreach($region_set[$ix] as $e)
            {
                // 候補値の出現が区域内で一回限りかどうかを調べる。
                for($n = 0; $n < strlen($grid[$e]); $n++)
                {
                    $d = substr($grid[$e], $n, 1);
                    $appearance[$d] = isset($appearance[$d]) ? -1 : $e;
                }
            }

            foreach($appearance as $n=>$p)
            {
                if($p == -1 || strlen($grid[$p]) == 1)
                    continue;

                $xy = Coord($p);
                $fixed_count++;
                echo "g$fixed_count$xy=$n";

                if(($dup_ix = DupIndex($grid, $p, $n, $ix)) != -1)
                    throw new Exception('Duplicate ' . Coord($dup_ix));

                $grid[$p] = $n;
                $reduced = true;
            } // foreach($appearance as $n=>$p)

            echo '.';
        } // for($ix = 0; $ix < count($region_set); $ix++)

        echo "\n";
    } while($reduced && $fixed_count < GRIDSIZE);

    echo "\n";
}

function GetCandidates($grid, $ix, $fixed_count)
{
    global $answer_count;

    PrintGridState($grid);
    echo "\n";

    for(; $ix < GRIDSIZE && strlen($grid[$ix]) == 1; $ix++);

    for($n = 0;
        $n < strlen($grid[$ix]) && $answer_count < MAXANSWERS;
        $n++)
        TestCandidate($grid, $ix, $n, $fixed_count);
}

function TestCandidate($grid, $ix, $p, $fixed_count)
{
    global $answer_count;

    $candidate = substr($grid[$ix], $p, 1);
    $xy = Coord($ix);
    $fixed_count++;
    echo "t$fixed_count$xy=$candidate from ($grid[$ix])\n";
    $grid[$ix] = $candidate;
    try
    {
        Reduce($grid, $fixed_count);
        if($fixed_count < GRIDSIZE)
            GetCandidates($grid, $ix, $fixed_count);
        else
        {
            $answer_count++;
            echo "解答$answer_count\n";
            PrintGridState($grid);
            echo "\n";
        }
    }
    catch(Exception $e)
    {
        $msg = $e->getMessage();
        echo " $msg\n\n";
    }
}
?>

名前:
コメント:
投稿キー:	※右の文字列を入力してください。