2010/08/26 09:46
10. マス目の数字を仮に定める(1)
難易度の高い問題では、候補値から選んだ数字を仮の確定値として解法を適用することで、解答を探します。プログラムは次のようになります。二つの関数 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"; } } ?>
(Sudoku)
2010/08/26 09:46
コメント