2010/08/12 20:34
5. マス目に初期値を与える
手順２の記述にかかる前に、もう一つやっておくことがあります。手順１では、各マス目に候補となる数字の組を設定しました。例題にあるように、数字が確定しているマス目がいくつかあります。これも含めて、初期状態を設定してやる必要があります。
マス目の候補値は'123456789'という文字列として、81個の要素を持つ配列に持たせました。確定値も、例えば'1'という、１文字だけの文字列として、同じ配列に持たせることができます。ただ、配列の要素ごとに確定値を設定する記述は面倒なので、次のようにします。
// 例題をそのまま転記
$dt = ' 41 8 '
. ' 1 9 3 '
. '6 3 7 5'
. '1 6 3 '
. ' 5 7'
. ' 42 '
. ' 5 36 '
. ' 7 2'
. '4 8 ';
// 9x9のマス目に候補値を設定する。
$grid = array();
for($n = 0; $n < 81; $n++)
{
$c = substr($dt, $n, 1);
if($c == ' ')
$grid[$n] = '123456789';
else
$grid[$n] = $c;
}
９文字ずつの文字列を９行書き、それらを連結させて81文字の文字列としています。確定値のないマス目は空白にしており、配列の81個の要素に、一対一に対応しています。substr 関数を使い、一文字ずつ配列の各要素に格納していきます。空白の場合には、候補となる文字列'123456789'を格納しています。
初期値の与え方は単純ですが、転記するに際し間違えることもあります。せめて、区画内に重複した数字がないかどうかのチェックをできるようにしておきましょう。まず、区画の定義が必要になります。区画は行、列、3×3 のブロック、それぞれ九つずつの計27個でした。これも配列を使って表現します。27個の要素を持つ配列です。個々の要素には、9個のマス目の位置情報を、これまた配列で持たせます。マス目の位置情報とは、配列$grid の添字のことです。
// 同一の要素を許さない区画の定義
$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
|
|
|
|||||||||||||||||||||||||||
|
|
|
|||||||||||||||||||||||||||
|
|
|
例えば、添字32の位置のマス目に確定値を設定する場合、このマス目が属する三つの区画で重複を調べる必要があります。右図で赤字で添字を記した区画です。$region_set で 27の区画を定義しましたが、$region_set[3]、$region_set[14]、$region_set[22]が対象の区画になります。指定されたマス目が属する区画がすぐに分かるよな仕組みを、次のコードで作っておきます。
// 各マス目が属する区画を導きだす。
$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; // $n を要素として追加
else
$rel_regions[$ix] = array($n); // $n は配列の一つめの要素
}
}
print_r($rel_regions);
'foreach($region_set[$n] as $ix)'は、$region_set[$n]の配列の各要素を$ix に設定してループを回してくれます。'for($i = 0; $i < count($region_set[$n]); $i++){$ix = $region_set[$n][$i];' と同義です。以下は、'print_r($rel_regions);' の出力です。$rel_regions がどのように設定されているか、確認できます。
Array
(
[0] => Array
(
[0] => 0
[1] => 9
[2] => 18
)
[1] => Array
(
[0] => 0
[1] => 10
[2] => 18
)
～
[80] => Array
(
[0] => 8
[1] => 17
[2] => 26
)
)
初期値の重複をチェックする機能を付け加えたコードは次のとおりです。二つの関数DupIndex とCoord が追加されました。ともに引数を持ち、関数値がかえされます。
// 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;
}
function DupIndex($p, $num)
{
// ある位置($p)のマス目が属する区画に$num があれば、
// $numを持つマス目の添字を返す。
global $grid, $region_set, $rel_regions;
foreach($rel_regions[$p] as $ix)
{
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)";
}
DupIndexは、マス目の位置とチェック対象となる数字を、引数として受け取ります。マス目の属する区画内に同じ数字があれば、その数字を持つマス目の位置が返されます。数字の重複が無ければ、-1 が返されます。Coord は、マス目の位置を表す0 から始まる添字を、（行、列）の座標値に変換して返します。どの位置のマス目に重複があったかを分かりやすく示すためです。
最初の重複が見つかった時点で、プログラムの実行をexitで終了させています。すべての重複を調べて提示するほうが親切なのかも知れませんが、例外処理を簡潔に留めおくことで、プログラムの全体構造が分かりやすく保てます。
漸く、手順２へ進むための準備が整いました。以下に、ここまでのコードと実行結果を記します。
数独パズルを解く。
<?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;
}
// 全てのマス目の状態を表示する。
PrintGridState();
exit;
function PrintGridState()
{
// 全てのマス目の状態を表示する。
global $grid;
$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(++$col == 9)
{
echo "\n";
$col = 0;
$blk = 0;
}
elseif(++$blk == 3)
{
echo ' ';
$blk = 0;
}
}
}
function DupIndex($p, $num)
{
// ある位置($p)のマス目が属する区画に$numがあれば、
// $numを持つマス目の添字を返す。
global $grid, $region_set, $rel_regions;
foreach($rel_regions[$p] as $ix)
{
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)";
}
?>
実行結果
数独パズルを解く。 1 (123456789)(123456789)4 1(123456789)(123456789) (123456789)8(123456789) 2 (123456789)1(123456789) (123456789)(123456789)9 (123456789)3(123456789) 3 6(123456789)(123456789) 3(123456789)7 (123456789)(123456789)5 4 1(123456789)6 (123456789)(123456789)(123456789) 3(123456789)(123456789) 5 (123456789)(123456789)(123456789) (123456789)5(123456789) (123456789)(123456789)7 6 (123456789)(123456789)(123456789) (123456789)(123456789)4 2(123456789)(123456789) 7 (123456789)(123456789)(123456789) 5(123456789)3 6(123456789)(123456789) 8 (123456789)7(123456789) (123456789)(123456789)(123456789) (123456789)(123456789)2 9 4(123456789)(123456789) (123456789)(123456789)(123456789) 8(123456789)(123456789)
(Sudoku)
2010/08/12 20:34
コメント