<< 2024 年 3 月 >>
25
26
27
28
29
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6


 トップ > プログラミング > Sudoku  ナンバープレイスを課題にしたプログラム作りです。

 1 2 3 4 5 6 7 8 9 10 11 12 13 
2010/08/29 15:31
11. マス目の数字を仮に定める(2)

追加した二つの関数のうち、まず GetCandidates に注目します。呼び出されるのは、Reduce を呼び出した後に確定したマス目の数がすべてのマス目の数に足りない場合です。$grid と 0 と $fixed_count を引数として渡しています。$grid は現在のマス目の状態です。0 はマス目の先頭位置を示し、この位置からまだ確定していないマス目を探すために使います。$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);
    }
}

GetCandidates は、単純な関数です。まず、第1引数 $grid の状態を PrintGridState を使って表示します。次に、第2引数 $ix のマス目位置から未確定のマス目を順次探し、未確定のマス目が見つかると TestCandidate を呼び出します。TestCandidate には、引数として $grid、$ix、そして候補値の文字位置を渡しています。

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);
}

TestCandidate も単純な関数です。受け取った引数 $grid、$ix、$p により、$grid[$ix]のマス目の候補値の中から$p位置の数字を仮の確定値として$grid[$ix]に設定します。そして Reduce を呼出し、確定したマス目の数がすべてのマス目の数に足りない場合に GetCandidates を呼び出しています。先の呼出し箇所と同様の記述です。

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";
    }
}

ここで、これらの関数について再帰的な呼出しをしていることに気付かれたでしょうか。GetCandidates → TestCandidate → GetCandidates と、呼び出された関数 TestCandidate が 自身を呼び出した関数 GetCandidates を呼び出しています。これを説明する前に、関数 Reduce の引数について説明します。

関数 Reduce を呼び出すときに、引数として $grid と $fixed_count を渡しています。上の二つの関数 GetCandidates、TestCandidate でも同じ引数を渡して呼び出していますが、関数の定義部分の記述が異なっています。'function Reduce(&$grid, &$fixed_count)'と、引数の$grid と $fixed_count の記述の前に'&'が付けられています。


虚数の情緒―中学生からの全方位独学法
function Reduce(&$grid, &$fixed_count)
{
    global $region_set;
    static $called = 0;
    $called++;

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

引数名の前に付けられた'&'の意味は、「関数内で引数変数の値が変更されたとき、関数呼び出し側の引数変数も変更される」ということです。つまり、関数の呼び出し元と呼び出し先で同じ領域を使っていることになります。Reduce 内では $grid の値が塗り替えられますが、Reduce 呼び出し元の $grid の値も変更されることになるわけです。Reduce の呼び出し後、すべてのマス目が確定していれば PrintGridState で全マス目の状態を表示させています。それは、Reduce によって変更されたマス目の状態を表示させているわけです。すべてのマス目が確定していなければ GetCandidates を呼び出していますが、これも Reduce によって変更されたマス目を引数 $grid で渡しているわけです。

ところが GetCandidates では引数を'&'を付けないで $grid として受け取っていますので、GetCandidates を呼び出している箇所の $grid は元の状態のままです。呼び出し先の関数内でマス目の確定値を設定しても、呼び出し元には影響がないわけですから、仮の確定値ということになります。結局、再帰的呼出しはマス目に仮の確定値を設定して、それも一つのマス目だけではなく幾重にも設定して、試行錯誤するために行った記述でした。

関数の引数の渡し方については、参照渡し(call by reference)と値渡し(call by value)の違いを認識する必要がありますが、上のコードを読み取ることができれば大丈夫です。

Reduce 内にある'static $called = 0;'の記述ですが、static を宣言することで、関数ブロックが呼び出されたときに変数領域が確保されるのではなく、プログラム起動時に領域が確保され、初期値が設定されることになります。Reduce が呼び出される回数を数えるための変数です。関数外で変数を宣言して、関数内で global 宣言するのと同じですが、関数外で参照することのない変数なのでこのような記述にしました。


(Sudoku) 2010/08/29 15:31

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