<< 2024 年 10 月 >>
29
30
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


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

 1 2 3 4 5 6 7 8 9 10 11 12 13 
2010/08/17 15:52
7. 数独解法手順4の記述

「あるマス目の候補が複数あっても、複数の数字のどれかが区画内の他のマス目の候補にない場合は、そのマス目に入る数字が確定する。」これが解法手順4です。早速、コード化してみましょう。

区画内の各マス目の候補を走査して、ただ一度しか現れない数字を探します。出現頻度を数えても良いのですが、必要な情報は一度現れるか否か、そして現れた場合のマス目の位置です。そのため、最初に現れた場合に位置情報を記憶し、二度目に現れた場合は位置情報として有り得ない値 -1を記憶するようにします。最初に現れたかどうかの判断は、記憶域の有無を確認することで可能です。これらを現れた数字をキー値とする配列に記憶します。

$appearance = array();
foreach($region 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)
        $grid[$p] = $n;
} // foreach($appearance as $n=>$p)

走査が終了したら、位置情報として妥当な値を持つ要素のみを、確定値として配列から取り出せば良いわけです。走査時点で既に確定値を持つマス目も、確定値として配列に格納されていることを考慮する必要があります。


すごいぞ折り紙―折り紙の発想で幾何を楽しむ

上のコードを手順2を著したコードに組み込みます。

foreach($region_set as $region)
{
    foreach($region as $e)
    {
        if(strlen($grid[$e]) != 1)
            continue;

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

    $appearance = array();
    foreach($region 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)
            $grid[$p] = $n;
    } // foreach($appearance as $n=>$p)
} // foreach($region_set as $region)

実行結果は次のとおりです。確定値が5個増えていることが読み取れます。

数独パズルを解く。
1 (23579)(2359) 4       1     (26)    5      (79)  8     (69)  
2 (2578) 1      (2578)  (2468)(2468)  9      (47)  3     (46)  
3 6      (289)  (289)   3     (248)   7      (149) 2     5     
4 1      (24589)6       (2789)(2789)  (28)   3     (459) (489) 
5 (2389) (23489)(2389)  (2689)5       (1268) (149) (1469)7     
6 (35789)(3589) (35789) (6789)3       4      2     (1569)(1689)
7 (289)  (289)  (1289)  5     (124789)3      6     (1479)(149) 
8 (3589) 7      (13589) (4689)(14689) (168)  (1459)(1459)2     
9 4      6      (12359) (2679)(12679) (126)  8     (1579)3     

(Sudoku) 2010/08/17 15:52

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