漸く解法手順2の記述に辿りつきました。手順2は、「区画内に数字の確定したマス目があるとき、確定した数字は、区画内の他のマス目の候補から外す」でした。
まずは、区画ごとに数字の確定したマス目を探します。各区画は配列 $region_set の要素を取り出すことで得られます。取り出した要素も配列であり、マス目の位置を表す添字の集合となっています。その添字$eを取り出して $grid[$e]とすることで、そのマス目の候補値を参照できます。候補値が一つの数字からなる文字列、つまり長さが1の文字列なら、数字の確定したマス目だということになります。コードは次のとおりです。
foreach($region_set as $region) { foreach($region as $e) { if(strlen($grid[$e]) == 1) { // ここに処理を記述 } } // foreach($region as $e) echo '.'; } // foreach($region_set as $region)
区画内に確定した数字を見つけたら、次の処理として、区画内の他のマス目の候補からその数字を取り除く作業を行ないます。文字を取り除くために、str_replace 関数を用います。確定した数字を長さ0の文字列''に置き換えます。コードは次のとおりです。
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) } // foreach($region_set as $region)
手順2の記述は簡単でした。結果的に手順3も記述したことになります。手順3は「候補の数が一つだけになったマス目があれば、そのマス目に入る数字が確定する」でした。上のコードでは候補値を列記した文字列から確定値を取り除いていきますので、1文字になった時点で、そのマス目に入る数字が確定したことになります。上のコードをプログラム本体に組み込んで実行させてみましょう。組み込む位置は、PrintGridState();の直前です。実行結果は次のとおりです。
数独パズルを解く。 1 (23579)(2359)4 1(26)(256) (79)8(69) 2 (2578)1(2578) (2468)(2468)9 (47)3(46) 3 6(289)(289) 3(248)7 (149)(1249)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)(136789)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(23569)(12359) (2679)(12679)(126) 8(1579)(139)
マス目の列が揃っていないので読みにくいのが難点です。列を揃えるように、PrintGridState 関数にコードをを書き足します。
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; } } }
改めて実行結果を記します。読みやすくなりました。確定値を持つマス目は増えませんでしたが、候補値の文字列が短くなったのが判ります。
1 (23579)(2359) 4 1 (26) (256) (79) 8 (69) 2 (2578) 1 (2578) (2468)(2468) 9 (47) 3 (46) 3 6 (289) (289) 3 (248) 7 (149) (1249)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)(136789)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 (23569)(12359) (2679)(12679) (126) 8 (1579)(139)