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

修正1 7/9
http://blog-imgs-36.fc2.com/a/m/a/amamiyaprog/SudokuGenerator2.txt

修正2 7/10

# 数独自動生成 SudokuGenerator Generator
# 引数 なし ()
# 戻り値 数独自動生成 (@SudokuGenerator)
sub SUDOKUGENERATOR{
my @SudokuGenerator = ();
my @Move = ();
my @CheckBlock = ();
my @CheckNumber = ();
my $Number = 0;
my $GetNumber = 0;
my $Column = 0;
my $Row = 0;
my $BlockPosition = 0;
my $IsBack = 0;
my $IsDelete = 0;
my $Count = 81;

# 初期化 Initialization
&InitializationSolver(\@Move, \@CheckBlock, \@SudokuGenerator);

# 数独の解答生成
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], \@SudokuGenerator) 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] . $SudokuGenerator[$Column][$Row];
# 使用した数字を削除
$SudokuGenerator[$Column][$Row] = 0;
# フラグ
$IsBack = 1;

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

# 初期化 Initialization
for(my $i = 8; $i >= 0; $i--){
# ブロック内で使用可能な数字
$CheckBlock[$i] = "123456789";
}

# (0, 0) から (8, 8) ランダム移動ルート Move
@Move = &RandomMove(\@SudokuGenerator);
$Count = @Move - 1;

for(my $i = $Count; $i >= 0; $i--){
# 縦 横 ブロックの番号
$Column = $Move[$i][0];
$Row = $Move[$i][1];
$BlockPosition = $Move[$i][2];
# 数字
$Number = $SudokuGenerator[$Column][$Row];

# 選択した行・列を中心に数字列(1-9)が揃っているか調べる
$IsDelete = &IsDeleteLevel1($Column, $Row, \@SudokuGenerator);

if($IsDelete == 0){
# 選択した行・列以外のブロックを埋められるか
$IsDelete = &IsDeleteLevel2($Column, $Row, \@SudokuGenerator);
}
if($IsDelete == 0){
# ブロック内と選択した行・列の数字で数字列(1-9)が揃っているか調べる Is Delete Level3
$IsDelete = &IsDeleteLevel3($Column, $Row, $CheckBlock[$BlockPosition], \@SudokuGenerator);
}
if($IsDelete == 0){
# 選択した行・列の数字を取り除いても解けるか調べる Is Delete Level4
$IsDelete = &IsDeleteLevel4($Column, $Row, \@SudokuGenerator);
}

if($IsDelete == 1){
# 数字を取り除く
$SudokuGenerator[$Column][$Row] = 0;
# 数字を一つ削除 Delete Number
&DeleteNumber($Number, \$CheckBlock[$BlockPosition]);
}
}

return @SudokuGenerator;
}

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

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

return $GetNumber;
}

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

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

# 乱数列を作成 Rand Number
# 引数 値 (\$Number)
# 戻り値 なし ()
sub RandNumber{
my ($Number) = @_;
my $RandNumber = "";

for(my $i = length($$Number); $i > 0; $i--){
$RandNumber = $RandNumber . &GetNumber($Number, $i);
}

# 乱数列を作成 Rand Number
$$Number = $RandNumber;
}

# ブロック内で使用可能な数字列を取り出す Check Block
# 引数数独 (\@Sudoku)
# 戻り値 使用可能な数字列 ($CheckBlock)
sub CheckBlock{
my ($Sudoku) = @_;
my @CheckBlock = ();
my $Column = 0;
my $Row = 0;
my $BlockColumn = 0;
my $BlockRow = 0;
my $Number = "";
my $Count = 9;

for(my $i = 0; $i < $Count; $i++){
# 初期化
$Column = int($i / 3) * 3;
$Row = ($i % 3) * 3;
$Number = "123456789";

for(my $j = 0; $j < $Count; $j++){
# 初期化
$BlockColumn = $Column + int($j / 3);
$BlockRow = $Row + ($j % 3);
# 数字を一つ削除 Delete Number
&DeleteNumber($$Sudoku[$BlockColumn][$BlockRow], \$Number);
}

$CheckBlock[$i] = $Number;
}

return @CheckBlock;
}

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

return $BlockPosition;
}

# 選択した行・列で使用可能な数字列 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;
}

# 選択した数字をブロック内・行・列から削除 Delete 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]);
}
}

# 初期化 Initialization
# 引数 移動 ブロック 数独解法 (\@Move, \@CheckBlock, \@Sudoku)
# 戻り値 なし ()
sub InitializationSolver{
my ($Move, $CheckBlock, $Sudoku) = @_;
my $Number = "123456789";
my $Position = 0;
my $Count = 9;

for(my $i = 0; $i < $Count; $i++){
for(my $j = 0; $j < $Count; $j++){
$$Sudoku[$i][$j] = 0;

# 移動する [0] 縦 [1] 横 [2] ブロックの番号
$$Move[$Position][0] = $i;
$$Move[$Position][1] = $j;
$$Move[$Position][2] = &BlockPosition($i, $j);

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

# 乱数列を作成 Rand Number
&RandNumber(\$Number);

# ブロック内(3 * 3)で使用できる数字列 Check Block
$$CheckBlock[$i] = $Number;
}
}

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

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

# 縦
for(my $i = $Column - ($Column % 3) - 1; $i >= 0; $i--){
# 数字を一つ削除 Delete Number
&DeleteNumber($$Sudoku[$i][$Row], \$CheckNumber);
}

# 横
for(my $i = $Row - ($Row % 3) - 1; $i >= 0; $i--){
# 数字を一つ削除 Delete Number
&DeleteNumber($$Sudoku[$Column][$i], \$CheckNumber);
}

return $CheckNumber;
}

# (0, 0) から (8, 8) ランダム移動ルート Move
# 引数 数独問題 ($Sudoku)
# 戻り値 ランダム移動ルート (@RandomMove)
sub RandomMove{
my ($Sudoku) = @_;
my @RandomMove = ();
my $Number = "012345678";
my $GetColumn = 0;
my $Position = 0;
my $RandomPosition = 0;
my $Count = 9;

for(my $i = 0; $i < $Count; $i++){
# 乱数列を作成 Rand Number
&RandNumber(\$Number);
# 数字を一つ取り出す Get Number
$GetColumn = &GetNumber(\$Number);

for(my $j = 0; $j < $Count; $j++){
# すでに数字が取り除かれているなら
next if($$Sudoku[$GetColumn][$j] == 0);

# 移動する [0] 縦 [1] 横 [2] ブロックの番号
$RandomMove[$Position][0] = $GetColumn;
$RandomMove[$Position][1] = $j;
$RandomMove[$Position][2] = &BlockPosition($GetColumn, $j);

# ランダム移動ルート
$RandomPosition = int(rand($Position + 1));

# 移動ルートの変更
($RandomMove[$Position][0], $RandomMove[$RandomPosition][0]) = ($RandomMove[$RandomPosition][0], $RandomMove[$Position][0]);
($RandomMove[$Position][1], $RandomMove[$RandomPosition][1]) = ($RandomMove[$RandomPosition][1], $RandomMove[$Position][1]);
($RandomMove[$Position][2], $RandomMove[$RandomPosition][2]) = ($RandomMove[$RandomPosition][2], $RandomMove[$Position][2]);

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

return @RandomMove;
}

# 選択した行・列を中心に数字列(1-9)が揃っているか調べる Is Delete Level1
# 引数 縦 横 数独 ($Column, $Row, \@Sudoku)
# 戻り値 フラグ ($IsDelete)
sub IsDeleteLevel1{
my ($Column, $Row, $Sudoku) = @_;
my $IsDelete = 0;
my $CheckNumber = "123456789";
my $Position = 0;
my $Count = 9;

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

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

# 数字列(1-9)が揃うなら
$IsDelete = 1 if($CheckNumber eq "");

return $IsDelete;
}

# 選択した行・列以外のブロックを埋められるか Is Delete Level2
# 引数 縦 横 数独 ($Column, $Row, \@Sudoku)
# 戻り値 フラグ ($IsDelete)
sub IsDeleteLevel2{
my ($Column, $Row, $Sudoku) = @_;
my $IsDelete = 0;
my $BlockColumn = $Column - ($Column % 3);
my $BlockRow = $Row - ($Row % 3);
my $BlCol = 0;
my $BlRow = 0;
my $Position = 0;
my $Count = 9;

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

# 0以外 選択した行・列
if(($$Sudoku[$BlCol][$BlRow] != 0) || ($$Sudoku[$BlCol][$BlRow] == $$Sudoku[$Column][$Row])){
$IsDelete = 1;
next;
}

for(my $j = 0; $j < $Count; $j++){
# 縦
if(($j != $Column) && ($$Sudoku[$j][$BlRow] == $$Sudoku[$Column][$Row])){
$IsDelete = 1;

last;
}
# 横
if(($j != $Row) && ($$Sudoku[$BlCol][$j] == $$Sudoku[$Column][$Row])){
$IsDelete = 1;

last;
}
}

# 埋められないなら
last if($IsDelete == 0);
}

return $IsDelete;
}

# ブロック内と選択した行・列の数字で数字列(1-9)が揃っているか調べる Is Delete Level3
# 引数 縦 横 数字 ブロック内にある数字 数独 ($Column, $Row, $CheckBlock[$BlockPosition], \@Sudoku)
# 戻り値 フラグ ($IsDelete)
sub IsDeleteLevel3{
my ($Column, $Row, $CheckBlock, $Sudoku) = @_;
my $IsDelete = 0;
my $CheckNumber = "123456789";
my $Position = 0;
my $Count = 9;

# ブロック内に残っている数字を取り除く
for(my $i = length($CheckBlock) - 1; $i >= 0; $i--){
substr($CheckNumber, index($CheckNumber, substr($CheckBlock, $i, 1)), 1) = "";
}

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

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

# 数字列(1-9)が揃うなら
$IsDelete = 1 if($CheckNumber eq "");

return $IsDelete;
}

# 選択した行・列の数字を取り除いても解けるか調べる Is Delete Level4
# 引数 縦 横 数字 数独 ($Column, $Row, \@Sudoku)
# 戻り値 フラグ ($IsDelete)
sub IsDeleteLevel4{
my ($Column, $Row, $Sudoku) = @_;
my @HintNumber = ();
my $Temp = 0;
my $Count = 9;
my $IsFailure = 0;
my $IsDelete = 0;

# 数字を取り除取り除く
$Temp = $$Sudoku[$Column][$Row];
$$Sudoku[$Column][$Row] = 0;
@HintNumber = &HintNumber($Sudoku);
$$Sudoku[$Column][$Row] = $Temp;

while($IsFailure == 0){
# 初期化
$IsFailure = 1;

for(my $i = 0; $i < $Count; $i++){
for(my $j = 0; $j < $Count; $j++){
if(length($HintNumber[$i][$j]) == 1){
# ブロック内・行・列から数字を取り除く
&DeleteHintNumber($i, $j, \@HintNumber);

# フラグ
$IsFailure = 0;
}
}
}

# 取り除いた数字が確定するなら
if($HintNumber[$Column][$Row] eq ""){
$IsFailure = 0;

last;
}
}

# 数独が解けるなら
$IsDelete = 1 if($IsFailure == 0);

return $IsDelete;
}




# 注意
# 必ずしも理詰めで解ける問題が生成されるとは限りません
# 自動生成なので解の一意性は保証されていません

use warnings;
use strict;

my $Count = 9;
my @SudokuProblem = &SUDOKUGENERATOR();
for(my $i = 0; $i < $Count; $i++){
print "\n" if(($i % 3) == 0);
for(my $j = 0; $j < $Count; $j++){
print " " if(($j % 3) == 0);
print "$SudokuProblem[$i][$j] ";
}
print "\n";
}


参考URL
perlで数独解法 (Sudoku Solver: SUDOKUSOLVER): perl:一寸先は闇

一言
ヒント数30以下がまったく出てくれない
次は、サイト内で出来るようにJavaScriptに挑戦してみよ
自分で解いてみたら問題が簡単すぎた
一意性を保証された問題の作り方が分からない

修正1
数字の取り除き方を正規表現に変えた

修正2
ヒント数を25前後まで減らせたけど、やたら重い
オンライン コンパイラ/インタプリタ
テクニカル分析
プロフィール

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

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

検索フォーム


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

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