FC2ブログ
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
最初
http://blog-imgs-36.fc2.com/a/m/a/amamiyaprog/SudokuSolver1.txt

修正1 7/11

# 数独解法 Sudoku Solver
# 引数 問題 (\@Problem)
# 戻り値 答え (@SudokuSolver)
sub SUDOKUSOLVER{
my ($Problem) = @_;
my @SudokuSolver = @$Problem;
my @Move = ();
my @CheckBlock = ();
my @CheckNumber = ();
my $GetNumber = 0;
my $Column = 0;
my $Row = 0;
my $BlockPosition = 0;
my $IsBack = 0;
my $Count = 0;

# 重複の確認 Check Repetition
&CheckRepetition(\@Problem);

# 数字を確定できる個所を埋める Sudoku Decision
&SudokuDecision(\@SudokuSolver);

# (0, 0) から (8, 8) 移動ルート Move
@Move = &Move(\@SudokuSolver);
$Count = @Move;

# ブロック内(3 * 3)で使用できる数字列 Check Block
@CheckBlock = &CheckBlock(\@SudokuSolver);

for(my $i = 0; $i < $Count; $i++){
# 縦 横 ブロックの番号
$Column = $Move[$i][0];
$Row = $Move[$i][1];
$BlockPosition = $Move[$i][2];

# 使用可能な数字列を取り出す Check Number
$CheckNumber[$i] = &CheckNumber($Column, $Row, $CheckBlock[$BlockPosition], \@SudokuSolver) if($IsBack == 0);
# 数字を一つ取り出す Get Number
$GetNumber = &GetNumber(\$CheckNumber[$i]);
# フラグ
$IsBack = 0;

if($GetNumber eq ""){
# 一つ後ろ
$i--;

# 失敗
if($i == -1){
print "Failure";
exit();
}

# 縦 横 ブロックの番号
$Column = $Move[$i][0];
$Row = $Move[$i][1];
$BlockPosition = $Move[$i][2];
# 使用した数字を戻す
$CheckBlock[$BlockPosition] = $CheckBlock[$BlockPosition] . $SudokuSolver[$Column][$Row];
# 使用した数字を削除
$SudokuSolver[$Column][$Row] = 0;
# フラグ
$IsBack = 1;

# forの$i++があるので
$i--;
}else {
# 数独解法 Sudoku SudokuSolver
$SudokuSolver[$Column][$Row] = $GetNumber;
# 数字を一つ削除 Delete Number
&DeleteNumber($SudokuSolver[$Column][$Row], \$CheckBlock[$BlockPosition])
}
}

return @SudokuSolver;
}

# 数字を一つ取り出す Get Number
# 引数 値 (\$Number)
# 戻り値 数字 ($GetNumber)
sub GetNumber{
my ($Number) = @_;
my $GetNumber = substr($$Number, 0, 1);

# 使用した値を削除
substr($$Number, 0, 1) = "";

return $GetNumber;
}

# 数字を一つ削除 Delete Number
# 引数 削除する数字 数字列 ($DeleteNumber, \$CheckNumber)
# 戻り値 なし ()
sub DeleteNumber{
my ($DeleteNumber, $CheckNumber) = @_;

# 数字を一つ削除
$$CheckNumber =~ s/$DeleteNumber//;
}

# ブロック内(3 * 3)で使用できる数字列 Check Block
# 引数 数独 (\@Sudoku)
# 戻り値 使用できる数字列 ($CheckBlock)
sub CheckBlock{
my ($Sudoku) = @_;
my @CheckBlock = ();
my $Number = 0;
my $Column = 0;
my $Row = 0;
my $BeginColumn = 0;
my $EndColumn = 0;
my $BeginRow = 0;
my $EndRow = 0;
my $Position = 0;

for(my $i = 0; $i < 9; $i++){
$Column = $i;
$Row = ($i % 3) * 3;

# 初期化
$Number = "123456789";
$BeginColumn = $Column - ($Column % 3);
$EndColumn = $BeginColumn + 3;
$BeginRow = $Row - ($Row % 3);
$EndRow = $BeginRow + 3;

for(my $j = $BeginColumn; $j < $EndColumn; $j++){
for(my $k = $BeginRow; $k < $EndRow; $k++){
# 数字を一つ削除 Delete Number
&DeleteNumber($$Sudoku[$j][$k], \$Number);
}
}

$CheckBlock[$i] = $Number;
}

return @CheckBlock;
}

# 使用可能な数字列を取り出す Check Number
# 引数 縦 横 数字 数独 ($Column, $Row, $Number, \@Sudoku)
# 戻り値 使用可能な数字列 ($CheckNumber)
sub CheckNumber{
my ($Column, $Row, $CheckBlock, $Sudoku) = @_;
my $CheckNumber = $CheckBlock;
my $Position = 0;

# 空白
if($CheckNumber eq ""){
return $CheckNumber;
}

for(my $i = 0; $i < 9; $i++){
# 縦
if($i != $Column){
# 数字を一つ削除 Delete Number
&DeleteNumber($$Sudoku[$i][$Row], \$CheckNumber);
}

# 横
if($i != $Row){
# 数字を一つ削除 Delete Number
&DeleteNumber($$Sudoku[$Column][$i], \$CheckNumber);
}
}

return $CheckNumber;
}

# 重複の確認 Check Repetition
# 引数 数独 (\@Sudoku)
# 戻り値 なし ()
sub CheckRepetition{
my ($Sudoku) = @_;
my $NumberColumn = 0;
my $NumberRow = 0;
my $NumberBlock = 0;
my $BlockColumn = 0;
my $BlockRow = 0;
my $BlcCol = 0;
my $BlcRow = 0;
my $PositionColumn = 0;
my $PositionRow = 0;
my $PositionBlock = 0;

for(my $i = 0; $i < 9; $i++){
# 初期化
$NumberColumn = "123456789";
$NumberRow = "123456789";
$NumberBlock = "123456789";
$BlockColumn = int($i / 3) * 3;
$BlockRow = ($i % 3) * 3;

for(my $j = 0; $j < 9; $j++){
# 初期化
$BlcCol = $BlockColumn + int($j / 3);
$BlcRow = $BlockRow + ($j % 3);

$PositionColumn = index($NumberColumn, $$Sudoku[$j][$i]);
$PositionRow = index($NumberRow, $$Sudoku[$i][$j]);
$PositionBlock = index($NumberBlock, $$Sudoku[$BlcCol][$BlcRow]);

if((($PositionColumn == -1) && ($$Sudoku[$j][$i] != 0)) ||
(($PositionRow == -1) && ($$Sudoku[$i][$j] != 0)) ||
(($PositionBlock == -1) && ($$Sudoku[$BlcCol][$BlcRow] != 0))){
print "Repetition";
exit();
}else {
# 数字を一つ削除 Delete Number
&DeleteNumber($$Sudoku[$j][$i], \$NumberColumn);
&DeleteNumber($$Sudoku[$i][$j], \$NumberRow);
&DeleteNumber($$Sudoku[$BlcCol][$BlcRow], \$NumberBlock);
}
}
}

return ;
}

# (0, 0) から (8, 8) 移動ルート Move
# 引数 数独 (\@Sudoku)
# 戻り値 移動ルート (@Move)
sub Move{
my ($Sudoku) = @_;
my @Move = ();
my $Position = 0;

for(my $i = 0; $i < 9; $i++){
for(my $j = 0; $j < 9; $j++){
if($$Sudoku[$i][$j] == 0){
# 移動する [0] 縦 [1] 横 [2] ブロックの番号
$Move[$Position][0] = $i;
$Move[$Position][1] = $j;
$Move[$Position][2] = &BlockPosition($i, $j);

# 配列の位置
$Position++;
}
}
}

return @Move;
}

# ブロックの番号 Block Position
# 引数 縦 横 ($Column, $Row)
# 戻り値 ブロックの番号 ($CheckBlock)
sub BlockPosition{
my ($Column, $Row) = @_;
my $BlockPosition = (int($Column / 3) * 3) + int($Row / 3);

return $BlockPosition;
}

# 数字を確定できる個所を埋める Sudoku Decision
# 引数 数独 (\@Sudoku)
# 戻り値 なし ()
sub SudokuDecision{
my ($Sudoku) = @_;
my @HintNumber = ();
my $Count = 9;
my $CountDelete = 1;

# 選択した行・列で使用可能な数字列
@HintNumber = &HintNumber($Sudoku);

while($CountDelete > 0){
# 初期化
$CountDelete = 0;

for(my $i = 0; $i < $Count; $i++){
for(my $j = 0; $j < $Count; $j++){
if(length($HintNumber[$i][$j]) == 1){
# 数字を確定できる個所を埋める Sudoku Decision
$$Sudoku[$i][$j] = $HintNumber[$i][$j];
# ブロック内・行・列から数字を取り除く
&DeleteHintNumber($i, $j, \@HintNumber);

# フラグ
$CountDelete = 1;
}
}
}
}
}

# 選択した行・列で使用可能な数字列 Hint Number
# 引数数独 (\@Sudoku)
# 戻り値 使用可能な数字列 (@HintNumber)
sub HintNumber{
my ($Sudoku) = @_;
my @HintNumber = ();
my @CheckBlock = &CheckBlock($Sudoku);
my $Number = "";
my $Count = 9;

for(my $i = 0; $i < $Count; $i++){
for(my $j = 0; $j < $Count; $j++){
if($$Sudoku[$i][$j] == 0){
# ブロック内で使用可能な数字列
$Number = $CheckBlock[&BlockPosition($i, $j)];

for(my $k = 0; $k < $Count; $k++){
# 数字を一つ削除 Delete Number
&DeleteNumber($$Sudoku[$i][$k], \$Number);
&DeleteNumber($$Sudoku[$k][$j], \$Number);
}
}else {
$Number = "";
}

# 選択した行・列で使用可能な数字列 Hint Number
$HintNumber[$i][$j] = $Number;
}
}

return @HintNumber;
}

# 選択した数字をブロック内・行・列から削除 Hint Number
# 引数数独 ($Column, $Row, \@HintNumber)
# 戻り値 なし ()
sub DeleteHintNumber{
my ($Column, $Row, $HintNumber) = @_;
my $BlockColumn = $Column - ($Column % 3);
my $BlockRow = $Row - ($Row % 3);
my $BlCol = 0;
my $BlRow = 0;
my $Number = $$HintNumber[$Column][$Row];
my $Count = 9;

for(my $i = 0; $i < $Count; $i++){
# 初期化
$BlCol = $BlockColumn + int($i / 3);
$BlRow = $BlockRow + ($i % 3);

# 数字を一つ削除 Delete Number
&DeleteNumber($Number, \$$HintNumber[$BlCol][$BlRow]);
&DeleteNumber($Number, \$$HintNumber[$i][$Row]);
&DeleteNumber($Number, \$$HintNumber[$Column][$i]);
}
}


参考URL
数独 - Wikipedia
ニコリ公式パズルガイド「数独」 - WEBニコリ
パズル > 数独のおためし問題 [www.nikoli.com]

一言
3 * 3 の縦・横

修正1
数字を確定できる個所から埋めるようにした
オンライン コンパイラ/インタプリタ
テクニカル分析
プロフィール

Author:雨宮
Firefoxを使用しているので気づかなかったけど、IE6でソースコードを上手くコピーできない

5/3
携帯用ならIE6でもソースコードをコピーできる
携帯用

検索フォーム


あわせて読みたいブログパーツ
一寸先は闇 RSS

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。