ここまで、数独解法の手順をコードとして記述してきました。作成したプログラムに例題を解かせてみたところ、初期状態で確定したマス目が24個だったのが29個と、5個のマス目を新たに確定させることができました。この29個の確定マス目を初期状態として、同じ手順を繰り返すことで、また新たにマス目を確定させることができるはずです。ここでは、「マス目の確定が出なくるまで手順を繰り返す」ように、コードに手を加えてみます。

ここまで書いたコードには、初期値の設定ミスをチェックするための記述もありました。マス目の確定値の重複をチェックする記述です。出題の誤りにより、マス目が重複する場合もあるかも知れません。マス目の確定時に確定値の重複をチェックする処理も追加します。

江戸のダイナミズム―古代と近代の架け橋

数独パズルを解く。
<?php
// 数独パズルを解く。
$dt = '  41   8 '
    . ' 1   9 3 '
    . '6  3 7  5'
    . '1 6   3  '
    . '    5   7'
    . '     42  '
    . '   5 36  '
    . ' 7      2'
    . '4     8  ';

// 同一の要素を許さない区画の定義
$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();
for($n = 0; $n < 81; $n++)
{
    $c = substr($dt, $n, 1);
    if($c == ' ')
        $grid[$n] = '123456789';
    elseif(($dup_ix = DupIndex($n, $c)) != -1)
    {
        $xy1 = Coord($dup_ix);
        $xy2 = Coord($n);
        echo "$xy1=$xy2=$c: 初期値に重複\n";
        exit;
    }
    else
        $grid[$n] = $c;
}

try
{
    Reduce();
}
catch(Exception $e)
{
    $msg = $e->getMessage();
    echo " $msg\n\n";
}

// 全てのマス目の状態を表示する。
PrintGridState();
exit;

function PrintGridState()
{
    global $grid;

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

        $cw[$col] = $max;
    }

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

    for($n = 0; $n < count($grid); $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($p, $num, $tested = -1)
{
    // ある位置($p)のマス目が属する区画に$numがあれば、
    // $numを持つマス目の添字を返す。
    global $grid, $region_set, $rel_regions;

    foreach($rel_regions[$p] as $ix)
    {
        if($tested >= 0 && $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()
{
    global $grid, $region_set;

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

    do
    {
        $reduced = false;

        ++$lp;
        echo " [$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);
                        echo "f$xy=$str";

                        if(($dup_ix = DupIndex($f, $str)) != -1)
                        {
                            $xy = Coord($dup_ix);
                            throw new Exception("Duplicate $xy");
                        }

                        $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);
                echo "g$xy=$n";

                if(($dup_ix = DupIndex($p, $n, $ix)) != -1)
                {
                    $xy = Coord($dup_ix);
                    throw new Exception("Duplicate $xy");
                }

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

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

    echo "\n\n";
}
?>

確定値を導き出すコードを、Reduceという名前を付けた関数としました。Reduce関数中の処理についてですが、確定値の重複があった場合、'throw new Exception("Duplicate $xy");'というコードで、Exceptionオブジェクトを生成して、それをthrowしています。投げられたオブジェクトは、Reduce関数を呼び出している箇所に書かれている'try{Reduce();}catch(Exception $e){…}'のcatch文にて受け取られます。つまり、ループのネストの深いところで起きた例外条件を認知するや否や、処理の制御を一気に特定箇所に移動させることができます。PHP5で可能になった便利な記述です。

重複チェックについては、マス目に確定値を設定する前に重複を確認するようにしました。そのため、手順２を記述した部分において、候補値の文字列から確定値を取り除いた文字列を、いきなりマス目に戻していたのを改めました。

手順４を記述した部分において、確定値の重複をチェックする関数DupIndex に３番目の引数が追加されています。区画内のマス目の候補値を走査して一つしか現れない数字を確定値とするわけですから、当該区画は重複チェックの対象から外せるわけです。つまり、この区画を示す添字を３番目の引数として渡すことで、不要なチェックをしないようにしています。他の呼び出し箇所では前の記述のままで、３番目の引数は記述されていません。DupIndex 関数の定義を見ると、３番目の引数の記述を '…, $tested = -1)'としています。引数 $tested を省略して呼び出した場合、-1 を設定して呼び出したのと同じ扱いになるので、従来通りの動作をさせることができます。

実行結果を下に記します。解答が出ています。８回目の繰り返しで、すべてのマス目が確定したことが判ります。手順２で確定した場合 f(x,y)=* 、手順３で確定した場合 g(x,y)=* というように、途中経過を表示しています。順調に確定値が見つかっていく様子が分かります。

数独パズルを解く。
 [1] ...................g(1,6)=5.g(3,8)=2..g(6,5)=3..g(9,2)=6..g(9,9)
=3.
 [2] ..g(3,7)=1.............g(8,7)=5.......g(5,6)=1.....
 [3] ..g(3,5)=4......g(9,3)=5......f(9,6)=2f(4,6)=8g(8,6)=6....g(2,1)
=5.......g(8,4)=4..
 [4] ............g(2,4)=8.....g(6,9)=8......g(6,8)=1....
 [5] .....g(6,2)=5g(6,4)=6...........f(8,8)=9f(9,8)=7f(7,8)=4g(4,8)=5
g(5,8)=6.g(7,9)=1..........
 [6] ......g(7,5)=7..f(9,4)=9g(9,5)=1...g(8,3)=1.f(5,4)=2g(4,4)=7.f(8
,5)=8g(4,5)=9...........g(8,1)=3...
 [7] ...f(4,9)=4f(4,2)=2.......g(5,2)=4.g(5,3)=3......f(2,9)=6g(1,9)=
9.g(1,2)=3..f(1,7)=7g(2,7)=4.g(5,1)=8..f(5,7)=9....
 [8] f(1,1)=2g(1,5)=6.f(2,5)=2g(2,3)=7........f(7,1)=9f(6,1)=7..f(6,3
)=9f(3,3)=8g(7,3)=2.......f(3,2)=9......f(7,2)=8...
 [9] ...........................

1 234 165 789
2 517 829 436
3 698 347 125
4 126 798 354
5 843 251 967
6 759 634 218
7 982 573 641
8 371 486 592
9 465 912 873

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