８クィーン

今回は、パズルの定番である "８クィーン" を取り上げます。 チェスのクィーンは、将棋の飛車と角行を併せた駒で、縦・横・斜めに動くことができます。 ８クィーンは、８x８の盤面に８個のクィーンを互いの利き筋に入らないように配置する問題です。 次は、解の１つです。

プログラム

use strict;
my $n = 8;
my @b_elms = grep /^[1-$n][1-$n]$/, 11 .. ($n . $n);
my @mirror = map { (split //)[0] . (($n + 1) - (split //)[1]) } @b_elms;
my @rot_90 = map { (($n + 1) - (split //)[1]) . (split //)[0] } @b_elms;
my ($count, %q_beam, @result);

foreach my $elm (@b_elms) {
  my($i, $j) = split //, $elm;
  my $p = $i + $j; my $m = $i - $j;
  @{$q_beam{$elm}} = grep { /^$i/ or /$j$/ or (split //)[0] + (split //)[1] == $p
                            or (split //)[0] - (split //)[1] == $m }
                     grep { ! /$elm/ } @b_elms;
}

my @boards = ([ 1, { map { $_ => 'Q' } @b_elms } ]);

while (@boards) {
  my $ref = shift(@boards);
  my $line = $ref->[0];
  my %board = %{$ref->[1]};
  my @places = grep { /^$line/ && $board{$_} eq 'Q' } @b_elms;
  OUT: foreach my $place (@places) {
    my %work = %board;
    @work{@{$q_beam{$place}}} = split //, '.' x @{$q_beam{$place}};
    if ($line == $n) {
      my %mirror; @mirror{@mirror} = @work{@b_elms};
      foreach (\%work, \%mirror) {
        my %tmp = %$_;
        foreach (1, 2, 3, 4) {
          my $chk = join '', map { $tmp{$_} } @b_elms;
          last OUT if grep /$chk/, @result;
          @tmp{@rot_90} = @tmp{@b_elms};
        }
      }
      foreach (sort keys %work) {
        print "$work{$_} "  if $_ !~ /$n$/;
        print "$work{$_}\n" if $_ =~ /$n$/;
      }
      print "\n";
      push @result, join '', map { $work{$_} } @b_elms;
      $count++;
    } else {
      push @boards, [$line + 1, \%work];
    }
  }
}

print "解の数: $count\n";

プログラムの解説

今回のプログラムは、"８クィーン" という標題になっていますが、 ４x４から９x９の盤面に対応しています。盤面の大きさは $n で指定することができますので、値を変えて表示させて見て下さい。

盤面のマス目の番号は、左上が 11、右下が 88 のように付けます。@b_elms は、マス目の番号を保持する配列です。 まずは、クィーンの利き筋を取得する方法から説明しましょう。 下の図は、クィーンを盤面の "34" に配置した例です。

縦と横のマス目の番号を取得するのは、簡単です。 縦の列は１の位の同じ数字のマス目を、横の列は 10 の位の同じ数字のマス目を選択します。 斜めの利き筋は、右下がりの列と左下がりの列の２種類あります。12, 23, 34, 45, 56, 67, 78 の右下がりの列の場合は、10 の位から１の位を引くと同じ数値になります。16, 25, 34, 43, 52, 61 の左下がりの列の場合は、10 の位と１の位を足すと同じ数値になります。 この２つの値は、列ごとに異なることは図を見れば分かります。 この斜めの列の性質を利用して、引いた値の同じマス目の番号と、足した値の同じマス目の番号を選択します。 この部分のプログラムを、再掲してみましょう。

foreach my $elm (@b_elms) {
  my($i, $j) = split //, $elm;
  my $p = $i + $j; my $m = $i - $j;
  @{$q_beam{$elm}} = grep { /^$i/ or /$j$/ or (split //)[0] + (split //)[1] == $p
                            or (split //)[0] - (split //)[1] == $m }
                     grep { ! /$elm/ } @b_elms;
}

この foreach ループが終了すると、ハッシュ %q_beam が作成されます。キーはマス目の番号で、値が利き筋のリストになります。ところで foreach ループの中で、grep や map を使う場合には注意が必要です。foreach の制御変数を使わずに、grep { ! /$els/ } @b_elms の代わりに grep { ! /$_/ } @b_elms と書いたとすると、生成されたハッシュ %q_beam の値のリストはすべて空になってしまいます。以前に痛い目にあったので、参考までに。

ハッシュ %q_beam が作成できたので、盤面にクィーンを配置していきます。 まず初期盤面としてハッシュを用意し、すべてのマス目に Q (クィーン) を配置しておきます。そして while ループを使用して、盤面の１行目 (横の列) から順に Q を配置していきます。Q を配置したら、その利き筋にあるマス目のすべてを Q から . (ピリオド) に変更します。. に変更されたマス目は、次の Q を配置することはできません。そのようにして２行目、３行目 ... ７行目、８行目まですべて配置できれば成功です。while ループの条件式には、配列 @boards を入れておきます。@boards は、配置途中の盤面をすべて格納しておく配列です。while ループの中では、その @boards から配置途中の盤面を取り出して次の行の Q を配置します。次は、その部分のプログラムです。

my @boards = ([ 1, { map { $_ => 'Q' } @b_elms } ]);

while (@boards) {
  my $ref = shift(@boards);
  my $line = $ref->[0];
  my %board = %{$ref->[1]};
  my @places = grep { /^$line/ && $board{$_} eq 'Q' } @b_elms;
  OUT: foreach my $place (@places) {
    my %work = %board;
    @work{@{$q_beam{$place}}} = split //, '.' x @{$q_beam{$place}};
    ...

    push @boards, [$line + 1, \%work];

@boards の要素は配列のリファレンスで、その配列には次に Q を配置する行番号と盤面のハッシュリファレンスが入っています。while の実行中に @boards の要素の数は増減して、すべての盤面の処理が終わると空になります。 (今回のプログラムの場合、@boards の要素として配列のリファレンスは必須ではありません。while の中で２つずつ取り出せば、同じように動作します。使った理由は、while の最初の行の shift を pop に変えてもそのまま動き、$n が 9, 8 のときにスムーズに出力が得られることです。)

最後に、重複解の排除について説明します。今回のプログラムでは、 重複解の排除は事後チェックによって行っています。重複解には、鏡像解と回転解があります。 鏡像解と 90 度回転解は、盤面の値を以下のように交換することで得ることができます。

鏡像解              90度回転解
11 --> 18           11 --> 81
12 --> 17           12 --> 71
...                 ...

17 --> 12           17 --> 21
18 --> 11           18 --> 11
...                 ...

81 --> 88           81 --> 88
82 --> 87           82 --> 78
...                 ...

87 --> 82           87 --> 28
88 --> 81           88 --> 18

プログラムの最初に定義してある @mirror と @rot_90 は、重複解チェック用の配列です。@mirror は鏡像解生成用で、@rot_90 は回転解生成用です。 鏡像解と 90 度回転解は、次のコードで生成します。

@hash{@mirror} = @hash{@b_elms}
@hash{@rot_90} = @hash{@b_elms}

回転解には、90 度回転解の他に 180 ど回転解と 270 度回転解がありますが、それには 90 度回転解をさらに 90 度ずつ回転することで得ることができます。 これで重複解が７つ生成できましたので、それまでの解を保存してある配列 @result の解と比較して、すでに同じ解がある場合には排除します。

(2005/05/10)

TopPage