４x４魔方陣

今回は、４x４魔方陣に挑戦します。４x４魔方陣には、数字の配置数が 20,922,789,888,000 (16!) 通りもあり、解が 7040 (重複解を除くと 880) あります。数字の配置１つ１つについてチェックしていたのでは、日が暮れてしまいます (日が暮れても終わらない!!)。ここで、解の１つを見てみましょう。

４x４魔方陣は、横・縦・斜めの４つの数字の和が 34 になりますが、他にも４隅 (図の赤で示した部分) と中央 (図の青で示した部分) も数字の和が 34 になります。横・縦・斜めの１列だけを配置しただけでは、解に至るには遠そうですが、４隅または中央に配置すれば何とかなりそうです。今回のプログラムは、先に４隅だけを配置して、解を求めました。早速ですが、プログラムを見て下さい。

プログラム

use strict;
my @order = ('0:15', '3:12', '0:3', '12:15', '0:12', '3:15');
my %between;

foreach my $i (1 .. 15) {
  foreach my $j ($i + 1 .. 16) {
    push @{$between{34 - $i - $j}}, $i . ':' . $j, $j . ':' . $i;
  }
}

foreach my $i (1 .. 7) {
  foreach my $j (($i + 1) .. 10) {
    last if $i + $j * 3 + 3 > 34;
    foreach my $k (($j + 1) .. 15) {
      last if $i + $j + $k * 2 + 1 > 34;
      next if $i + $j + $k + 16 < 34;
      my @corner_1 = ($i, $j, $k, 34 - $i - $j - $k);
      my @corner_2 = @corner_1[0, 1, 3, 2];
      my @corner_3 = @corner_1[0, 2, 3, 1];
      foreach (\@corner_1, \@corner_2, \@corner_3) {
        my @board = split(//, 'u' x 16);    # 何の意味もない。好みの問題
        @board[0, 3, 12, 15] = @$_;
        search(0, @board);
      }
    }
  }
}

sub search {
  my $no = shift;
  my @board = @_;
  my ($i, $j) = split /:/, $order[$no];
  my $k = ($j - $i) / 3;
  foreach (@{$between{$board[$i] + $board[$j]}}) {
    next if join(':', $_, @board) =~ /\b(\d+)\b.*\b\1\b/;
    my @work = @board;
    @work[$i + $k, $j - $k] = split /:/;
    if ($no == 3) {
      next if $work[1] + $work[5] + $work[9] + $work[13] != 34;
    }
    if ($no == 5) {
      next if $work[4] + $work[5] + $work[6] + $work[7] != 34;
      printf "%3d %3d %3d %3d\n", @work[0, 1, 2, 3];
      printf "%3d %3d %3d %3d\n", @work[4, 5, 6, 7];
      printf "%3d %3d %3d %3d\n", @work[8, 9, 10, 11];
      printf "%3d %3d %3d %3d\n\n", @work[12, 13, 14, 15];
    } else {
      search($no + 1, @work);
    }
  }
}

プログラムの説明

今回のプログラムでは、重複解を除いた 880 の解を表示するように作りました (一応は)。盤面には、平坦な配列 @board を使います。盤面のマス目の番号は、左上が 0、右下が 15 になります。そして、組合せを生成するループを使って、合計値が 34 になった数字を４隅に配置します。以下に、盤面と配置された様子を示します。

パズルでは、重複解の扱いがやっかいです。上の例で、４つの数字の４隅への配置は 24 (4!) 通りあります。今回のプログラムでも、少し改造して 24 通り探索するようにすれば、7040 の解が得られます。今回のプログラムでは、１つの組合せ (数字順に並んでいる) から３つのパターンを生成しています。組合せの最初の数字を左上に固定して、残りの３つの数字を右下に入れています。これで探索すると、880 の解が得られます (たぶん大丈夫と思っているが、自信はない)。

４隅に数字が配置されたので、その４隅の数字を利用して間の２つに数字を配置していきます。そのために、あらかじめ２つの変数 @order と %between を用意しておきます。@order には、２隅の番号のペアのリストを格納しておきます。%between は、キーに隅の数字２つの合計値を、値に間に入れることのできる数字のペアのリストを格納しておきます。そして、２つの変数を利用して間に数字を入れていきます。それでは、実際のコードを見てみましょう。

まず最初に、これから処理する盤面の番号 $i と $j を取得します。次に $i と $j の間のマス目の番号を取得するために、$k を設定しておきます。(再帰呼び出しではない) 初回の search 呼び出しでは、$i に 0 が、$j に 15 が、$k に 3 がセットされます。マス目 0 と 15 の間の２つのマス目の番号は、$i + $k と $j - $k で取得することができます。そして、マス目 $i と $j の数字を加算して、その合計値をキーとして間に入れる数字のリストを取得します。上の図の例では、%between のキー "5" のリストを取得することになります。%between のキー "5" のエントリーは、次のようになっています。

foreach の List 部に上のリストが入ります。すでに @board に配置されている数字の場合は、正規表現を使ってスキップします。上の図の例では、@board の要素に 16 がありますので、最初の２つはスキップされます。次の "14:15" は、@board に使われていないので、マス目５に 14 が、マス目 10 に 15 がセットされます。そして、マス目６と９に数字をセットするために search が再帰呼び出しされます。盤面が埋まるか失敗するまでで、これが繰り返えされます。

プログラムを実行すると、高速 (それほどでもなく、待たせない程度) に 880 の解が表示されます。