数字並べ２(平方数)

今回は、１から N までの連続した整数を、隣り合った整数の和が平方数になるように並べます。下の例は、最初が１から 15 までを１列に並べたものです。１から 15 までを並べたものでは、最初の数字 8 と最後の数字 9 の和は平方数になっていません。N の値を大きくすることで、最初の数字と最後の数字の和が平方数になるものが得られます。長方形で示してあるのが、１から 32 までを並べたものです。

プログラム

use strict;
my $n = 15;
my @sq = map { $_ ** 2 } 2 .. int(sqrt($n + ($n - 1)));
my %otonari; my $start = 1;

foreach my $i (1 .. $n) {
  foreach my $sq (@sq) {
    next if $sq - $i < 1;
    next if $sq - $i == $i;
    last if $sq - $i > $n;
    push @{$otonari{$i}}, $sq - $i;
  }
}

foreach (sort { $a <=> $b } keys %otonari) {
  $start = $_ if @{$otonari{$_}} < @{$otonari{$start}};
}

if ($n <= 14) {
  exit;
} elsif (@{$otonari{$start}} == 1) {
  search("$start:${$otonari{$start}}[0]");
} else {
  print "ring only:\n";
  search("${$otonari{$start}}[0]:$start:${$otonari{$start}}[1]");
}

sub search {
  my $part = shift;
  my ($i) = $part =~ /\b(\d+)$/;
  foreach my $j (@{$otonari{$i}}) {
    next if $part =~ /\b$j\b/;
    my $work = $part . ':' . $j;
    if ($work =~ tr/:// == $n - 1) {
      if (@{$otonari{$start}} == 1) {
        $work =~ s/:/ /g;
        print "$work\n";
      } else {
        $work =~ /^(\d+).*\b(\d+)$/;
        if (sqrt($1 + $2) !~ /\./) {
          $work =~ s/^(.*):(1:.*)$/$2:$1/;
          my @work = map { $_ <= 9 ? ' ' . $_ : $_ } split /:/, $work;
          my ($line, $blank);
          if ($n % 2) {
            $line = join(' ', @work[0 .. ((($n - 8) + 1) / 2 - 1)]);
            @work = @work[(($n - 8) + 1) / 2 .. $#work];
          } else {
            $line = join(' ', @work[0 .. (($n - 8) / 2 - 1)]);
            @work = @work[($n - 8) / 2 .. $#work];
          }
          print "  $line\n";
          $blank = ' ' x length($line);
          print "$work[$#work]$blank$work[0]\n";
          @work = @work[1 .. ($#work -1)];
          print "$work[$#work]$blank$work[0]\n";
          @work = @work[1 .. ($#work -1)];
          print "$work[$#work]$blank$work[0]\n";
          @work = @work[1 .. ($#work -1)];
          print "$work[$#work]$blank$work[0]\n";
          @work = reverse @work[1 .. ($#work -1)];
          if ($n % 2) { print "   @work\n\n"; }
          else        { print "  @work\n\n"; }
        }
      }
    } else {
      search($work);
    }
  }
}

プログラムの説明

パズルの中には、データの量が膨大になってパソコンでなければ解答を得られないものと、紙と鉛筆を使って手作業で解けるものがあります。今回の１から N までを１列に並べるパズルは、N の値が小さいときには、手作業でも十分に解くことができます。ここで、１から 15 までを手作業で並べてみましょう。たた単に、数字の並び替えの試行錯誤で解くのは大変です。次のような「お隣さんリスト」を作成します。

お隣さんリストは、各数字の隣りに置くことのできる数字のリストです。このお隣さんリストの威力は絶大で、これを使って簡単に並べることができます。リストの 8 と 9 に注目してください。8 と 9 の隣りに置ける数字は、１つしかありません。ということは、途中には置けずに端に置く必要があることを意味します。先頭に 8 (または 9) を置いて、リストを見ながら並べます。

どうですか、簡単でしょう。ほどんど選択肢もなく、並べることができました。絶大な威力のある (お隣さんリスト改名) 隣接リストは、プログラムでも使わない手はありません。次は、隣接リストを表示するプログラムと、N が 14, 15, 30, 31 のときの出力です。

use strict;
my $n = 15;
my @sq = map { $_ ** 2 } 2 .. int(sqrt($n + ($n - 1)));
my %otonari;

foreach my $i (1 .. $n) {
  foreach my $sq (@sq) {
    next if $sq - $i < 1;
    next if $sq - $i == $i;
    last if $sq - $i > $n;
    push @{$otonari{$i}}, $sq - $i;
  }
}

foreach (sort { $a <=> $b } keys %otonari) {
  print "$_ => [", join(', ', @{$otonari{$_}}), "]\n";
}

隣接リストを分析すると、いろいろなことが分かります。１列に並べることのできる N の最小値は、15 になります。では、なぜ N が 14 以下では、並べることができないのでしょうか。14 の隣接リストを見てみると、接続対象数１(隣りに置ける数字が１つ) の数字が 8, 9, 10 と３つあります。端は２つしかないため、並べることは不可能となります。N が 13 以下も同様です。接続対象数１の数字が２つ以下であることが、１列に並べるための１つの必要条件になります。しかし、この必要条件を満たしていても、必ずしも並べることができるわけではありません。 N が 15, 16, 17 では並べることができますが、(18 は接続対象数１の数字が３つ) 19, 20, 21, 22 では並べることができません。次の 23 では並べることができ、24 では並べることができなく、25 からは調べた限りではずっと並べることができます。

次は、リング状に並べることを考えます。リング状に並べるためには、どの数字の両側にも数字を置かなければならないので、接続対象数１の数字がないことが必要です。N が 30 以下では、すべて１つ以上の接続対象数１の数字があり、リング状に並べることができません。N が 31 になって初めて接続対象数１の数字がなくなり、リング状に並べるための１つの要件を備えたことになります。実際には、N が 31 では並べることができなく、32 からは並べることができます。

プログラムの最初で、この隣接リストを作成します。隣接リストを作成したら、このリストを利用して数字並べを行います。その前に隣接リストを解析して、探索を開始するための数字を決定します。そして、その数字を変数 $start に入れておきます。

$start には、接続対象数の最小の数字のうちの、最も小さな数字が入ります。上の表で N が 15 のときには接続対象数１の 8, 9 のうちの 8 が、N が 31 のときには接続対象数２の 16, 17, 18, 25, 26, 27, 28, 29, 30, 31 のうちの 16 が $start に入ることになります。探索を開始する数字 $start が決まったら、数字並べを探索するサブルーチン search を呼び出します。search に渡す引数は、接続対象数１の場合には「$start と $start に接続できる数字」を、接続対象数２の場合には「$start の両側に接続できる数字」をコロンで結んだものとなります。

search サブルーチンは、リング表示のコードが少し長いだけで、構造はそれほど複雑ではありません。以下が search サブルーチンの構造になります。

search サブルーチンは、探索途中の文字列 (数字とコロンを連結したもの) を受け取ります。そして、文字列の末尾の数字に繋げることのできる数字を隣接リストから取得して、コロンを間に挟んで繋げます。連結した文字列がまだ探索途中である場合は、さらに search を再帰呼び出しします。

探索が成功した場合は、$start の数字の接続対象数を調べます。接続対象数が１のときは、ライン表示になります。ライン表示は、コロンをスペースに置き換えて、そのまま出力します。接続対象数が１でない (２である) ときには、ライン表示は行わずにリング表示のみを行います。そのために、先頭と末尾の数字の和が平方数になっていることを確認します。