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

# Nクイーン問題 N Queens Problem
# 引数 N個 ($N)
# 戻り値 解 (@QueensProblem)
sub NQUEENSPROBLEM{
my ($N) = @_;
my @QueensProblem = ();
my @Column = ();
my @Row = ();
my @UnusablePosition = ();
my $PossibleToMove = 0;
my $Position = 0;
my $PosQueen = 0;
$N = int($N);
my $N1 = $N - 1;

# 個数の確認
if($N <= 3){
return 0;
}

# 初期化
for(my $i = $N - 1; $i >= 0; $i--){
for(my $j = $N - 1; $j >= 0; $j--){
$UnusablePosition[$i][$j] = -1;
}
}

for(my $i = 0; $i < $N; $i++){
# 配列の位置 縦 横
$Column[$Position] = 0;
$Row[$Position] = $i;

# 使用できない位置 Unusable Position
&UnusablePosition($N, $Column[$Position], $Row[$Position], \@UnusablePosition);

# 配列の位置
$Position++;

while($Position > 0){
# 移動可能 Possible to Move
$PossibleToMove = &PossibleToMove($N, $Position, \@UnusablePosition);
# 配列の位置 縦 横
$Column[$Position] = $Position;
$Row[$Position] = $PossibleToMove;

if($PossibleToMove != -1){
# 使用できない位置 Unusable Position
&UnusablePosition($N, $Column[$Position], $Row[$Position], \@UnusablePosition);

if($Position == $N1){
# Nクイーン問題 N Queens Problem
for(my $j = 0; $j < $N; $j++){
# バリエーション解
# [0] 縦 [1] 横
$QueensProblem[$PosQueen][$j][0] = $Column[$j];
$QueensProblem[$PosQueen][$j][1] = $Row[$j];
}

# Nクイーン問題 配列の位置
$PosQueen++;
}else {
# 配列の位置
$Position++;
}
}else {
# 配列情報を削除 Delete Position
&DeletePosition($N, $Column[$Position - 1], $Row[$Position - 1], \@UnusablePosition);

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

return @QueensProblem;
}

# 移動可能 Possible to Move
# 引数 N個 縦の位置 位置 ($N, $Position, \@UnusablePosition)
# 戻り値 移動可能な行の位置 ($PossibleToMove)
sub PossibleToMove{
my ($N, $Position, $UnusablePosition) = @_;
my $PossibleToMove = -1;

for(my $i = 0; $i < $N; $i++){
if($$UnusablePosition[$Position][$i] == -1){
$PossibleToMove = $i;

last;
}
}

return $PossibleToMove;
}

# 使用できない位置 Unusable Position
# 引数 N個 縦 横 位置 ($N, $Column, $Row, \@UnusablePosition)
# 戻り値 なし ()
sub UnusablePosition{
my ($N, $Column, $Row, $UnusablePosition) = @_;
my $Col = 0;
my $Ro1 = 0;
my $Ro2 = 0;

# 現在 使用する値
for(my $i = $N - $Column - 1; $i >= 0; $i--){
# 配列の位置 縦 横
$Col = $Column + $i;
$Ro1 = $Row + $i;
$Ro2 = $Row - $i;

# 縦
$$UnusablePosition[$Col][$Row] = $Column if($$UnusablePosition[$Col][$Row] == -1);
# 斜め
$$UnusablePosition[$Col][$Ro1] = $Column if(($Ro1 < $N) && ($$UnusablePosition[$Col][$Ro1] == -1));
$$UnusablePosition[$Col][$Ro2] = $Column if((0 <= $Ro2) && ($$UnusablePosition[$Col][$Ro2] == -1));
}

return ;
}

# 配列情報を削除 Delete Position
# 引数 N個 縦 横 位置 ($N, $Column, $Row, \@UnusablePosition)
# 戻り値 なし ()
sub DeletePosition{
my ($N, $Column, $Row, $UnusablePosition) = @_;
my $Col = 0;
my $Ro1 = 0;
my $Ro2 = 0;

# 一つ前 行を除いた値を削除
for(my $i = $N - $Column - 1; $i > 0; $i--){
# 配列の位置 縦 横
$Col = $Column + $i;
$Ro1 = $Row + $i;
$Ro2 = $Row - $i;

# 縦
$$UnusablePosition[$Col][$Row] = -1 if($$UnusablePosition[$Col][$Row] == $Column);
# 斜め
$$UnusablePosition[$Col][$Ro1] = -1 if(($Ro1 < $N) && ($$UnusablePosition[$Col][$Ro1] == $Column));
$$UnusablePosition[$Col][$Ro2] = -1 if((0 <= $Ro2) && ($$UnusablePosition[$Col][$Ro2] == $Column));
}

$Col = $Column + 1;

# 現在 行を削除
for(my $i = 0; $i < $N; $i++){
# 横
$$UnusablePosition[$Col][$i] = -1 if($$UnusablePosition[$Col][$i] == $Col);
}

return ;
}




use warnings;
use strict;

my $N = 8;
my @QueensProblem = &NQUEENSPROBLEM($N);
my $Count = @QueensProblem;

for(my $i = 0; $i < $Count; $i++){
for(my $j = 0; $j < $N; $j++){
for(my $k = 0; $k < $N; $k++){
if($QueensProblem[$i][$j][1] == $k){
print " Q ";
}else {
print " * ";
}
}
print "\n";
}
print "\n";
}


参考URL
エイト・クイーン - Wikipedia

一言
次は数独を解いてみよう
オンライン コンパイラ/インタプリタ
テクニカル分析
プロフィール

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

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

検索フォーム


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

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