となりオセロ

今回は、「となりオセロ」の解法プログラムを取り上げます。「となりオセロ」のルールは、１人で遊べるようにオセロを元に私が考えてみました。パズルとしても多少は面白いところがあると思いますので、解法プログラムを理解するためにも遊んでみてください。「となりオセロ」のルールは、次のようなものです。

「となりオセロ」パズルは、左上に黒石が１つ置かれた盤面でスタートします。スタート図では、左上の黒石の周囲の３ヶ所のみ石を置くことができます。石の少ない間は石を置く毎に、石を置ける場所は増えていきます。すべての石を置き終わったときに、すべて黒石であれば完成ということになります。(なお、パズルを改良 (?) して白石も混じった完成図も採用していますが、ここではすべてが黒石になる完成図のみを扱います。)

全手順探索

「となりオセロ」のルールはちょっとした思いつきですが、何はともあれ正解がないことにはパズルが成立しないことになります。また、正解がある場合にも、どの程度の正解率があるのか知りたいところです。そこで、まずは最初に、総当たりの全手順探索のプログラムを作って調べてみました。

 1:  use strict;
 2:  my (%round, %board, $all, $black); my $start = "11"; my $n = 3;
 3:
 4:  foreach my $i (1 .. $n) {      # %round の作成
 5:    foreach my $j (1 .. $n) {
 6:      my @round = ();
 7:      foreach my $k (($i > 1 && $i < $n) ? ($i - 1, $i, $i + 1) : $i == 1 ? ($i, $i + 1) : ($i - 1, $i)) {
 8:        foreach my $l (($j > 1 && $j < $n) ? ($j - 1, $j, $j + 1) : $j == 1 ? ($j, $j + 1) : ($j - 1, $j)) {
 9:          next if $k == $i and $l == $j;    # 自分自身のマス目を除外
10:          push @round, $k . $l;
11:        }
12:      }
13:      $round{"$i$j"} = [@round];
14:    }
15:  }
16:
17:  foreach my $i (1 .. $n) {      # 石のない状態で %board を作成
18:    foreach my $j (1 .. $n) {
19:      my $key = $i . $j;
20:      $board{$key} = [0];
21:      my $k = ($i > 1 && $i < $n) ? 2 : 1;
22:      my $l = ($j > 1 && $j < $n) ? 2 : 1;
23:      push @{$board{$key}}, $k + $l;
24:      push @{$board{$key}}, scalar(@{$round{$key}});
25:    }
26:  }
27:
28:  $board{$start}->[0] = 1;       # 11 に石を置く
29:  foreach my $pos (@{$round{$start}}) {
30:    --$board{$pos}->[2];
31:    if ("$pos$start" =~ /(.).\1/) {
32:      --$board{$pos}->[1];
33:    }
34:  }
35:
36:  search();
37:
38:  sub search {
39:    my @next_pos = grep { !$board{$_}->[0] and $board{$_}->[2] < @{$round{$_}} } keys %board;
40:    foreach my $pos (@next_pos) {
41:      $board{$pos}->[0] = 1;    # 石を置く
42:      foreach my $round (@{$round{$pos}}) {
43:        --$board{$round}->[2];
44:        if ("$pos$round" =~ /(.).\1/) {
45:          --$board{$round}->[1];
46:          $board{$round}->[0] = 3 - $board{$round}->[0] if $board{$round}->[0];
47:        }
48:      }
49:
50:      if (@next_pos == 1) {     # 盤面が埋まった
51:        ++$all;
52:        ++$black unless grep { $board{$_}->[0] == 2 } keys %board;
53:      } else {                  # 次の石を置くための再帰呼び出し
54:        search();
55:      }
56:
57:      $board{$pos}->[0] = 0;    # 石を取り除く
58:      foreach my $round (@{$round{$pos}}) {
59:        ++$board{$round}->[2];
60:        if ("$pos$round" =~ /(.).\1/) {
61:          ++$board{$round}->[1];
62:          $board{$round}->[0] = 3 - $board{$round}->[0] if $board{$round}->[0];
63:        }
64:      }
65:    }
66:  }
67:
68:  print "all: $all,  black: $black\n";

Line 4 ～ 15: 周囲のマス目の数を保持する %round を作成する: %round のキーはマス目番号で、値は無名配列の中に収めた周囲のマス目番号で 11 => [12, 21, 22] のようなデータ構造なります。%round はプログラム中に変化することなく、問い合わせに応じて周囲のマス目数 (スカラーコンテキスト) や周囲のマス目のリスト (リストコンテキスト) を返したりします。
Line 17 ～ 26: %board を作成 (本文中で詳述)
Line 28 ～ 34: 11 に石を置いてスタート図を作る (本文中で詳述)
Line 36: search() サブルーチンを呼び出す
Line 39: 石を置けるマス目を検出する: 石を置けるのは、当然ですが石を置いていない (!$board{$pos}->[0]) ことと、周囲に石が置いてあること ($board{$pos}->[2] < @{$round{$pos}}) の２つが条件になります。この２つの条件を満たすマス目を検出して、配列 @next_pos に格納します。
Line 41 ～ 48 (57 ～ 64): 該当のマス目に石を置く (除去する): この２つのコードは、隣接するタテとヨコのマス目に置かれている石を反転する以外は Line 28 ～ 34 のコードと同じです。石が置かれているとその値は１または 2 になっているので、3 からその値を引くと石が反転されたことになります。
Line 50 ～ 55: 再帰呼び出しの停止と再帰呼び出し: 盤面が石で埋まったら、$all をインクリメントして全手順数の数え上げて、黒のみの石で埋まったときの $black のインクリメントで正解手順数の数え上げをします。盤面が石で埋まっていない場合は、次の石を置くために search() を再帰呼び出しを行います。
Line 68: 結果を報告する

プログラムの最初の方で、「となりオセロ」の盤面を作成します。盤面には２桁の番号を付け、左上がマス目が 11 になります (下図、4 x 4 盤面)。盤面データは、ハッシュ %board で管理します。%board のキーがマス目の番号を表し、値には無名配列の中に３つのデータが格納されます。３つのデータはそれぞれ、マス目の石の状態、隣接するタテとヨコの空きマス目の数、隣接する周囲の空きマス目の数、となります。冒頭での盤面の作成は石のない状態で作成するので、%board の初期データは下図の右側のようになります。

無名配列の最初の「マス目の石の状態」は、0 が石が置かれていないことを意味し、１が黒石であることを意味し、2 が白石であることを意味しています。石が置かれていない 0 の状態では、タテまたはヨコに石が置かれても変化しません。石は黒石として置かれるので、そこで始めて１になります。その後は、タテまたはヨコに石が置かれると１と 2 の間で値がトグル (１の場合は 2 に、2 の場合は１になること) します。

２番目の「隣接するタテとヨコのの空きマス目の数」は、隣接するタテまたはヨコに石が置かれたときに減らされます。逆の言い方をすると、マス目に石を置いたときは、隣接するタテとヨコのデータを更新することになります。３番目の「隣接する周囲の空きマス目の数」は２番目のデータとほぼ同様で、タテとヨコに石を置いたときだけでなく斜めに隣接するマス目に置かれたときもデータを更新される点が異なります。

「となりオセロ」パズルは、11 のマス目に石を置いた状態からスタートします。11 に石を置くと %board は、初期値から太字で示したデータが変更されます。

２つ目からの石は、search() サブルーチンを呼び出して置いて行きます。２つ目の石は、石が置いてなくかつ周囲に石の置いてある 12, 21, 23 の内の１つに置くことになります。仮に 12 に石を置いたとすると %board のデータは、次のように変更されます。

再帰呼び出し型の search() サブルーチンで次々に石を置いていくと、総当たりの全手順探索ができます。盤面にすべて石が置かれたときに、全手順数と盤面がすべて黒石になる正解手順数を数えていきます。ちなみに、盤面がすべて黒石になったときの %board のデータは、１番目がすべて１に、２番目と３番目がすべて 0 になります (下図)。なお、白石がある場合は、１番目のデータが 2 になるので簡単に判別できます。

全手順探索プログラムを私のパソコン (PentiumM 1.8GHz, 2GB RAM) で実行した結果は、次のようになりました。3 x 3 盤面は短時間で実行できることは分かっていましたが、4 x 4 盤面はどのくらい時間がかかるのか分かりませんでした。そこで、あらかじめ盤面に 4, 5 個の石を置いておいて、どのくらい時間がかかるか見て全体の時間を推測しました。結果的に、約１カ月かかって実行を終了しました。

正解率は、3 x 3 盤面では 3.29%、4 x 4 盤面では 0.03% となりました。この正解率では、ランダムにただ石を置いて行くだけでは正解できないことを示しています。多少なりとも考える要素があるということで、パズルとして楽しめるものと思います。

正解手順探索

正解手順探索のプログラムは、前節の全手順探索プログラムが出発点になります。全手順探索プログラムから、不正解の手順を除外します。また、正解手順にも対称解や手順前後解もたくさんあります。そのような解も、除外していきます。

  1  use strict;
  2  my (%round, %board, %hist, $black); my $start = "11"; my $n = 4;
  3
  4  foreach my $i (1 .. $n) {
  5    foreach my $j (1 .. $n) {
  6      my @round = ();
  7      foreach my $k (($i > 1 && $i < $n) ? ($i - 1, $i, $i + 1) : $i == 1 ? ($i, $i + 1) : ($i - 1, $i)) {
  8        foreach my $l (($j > 1 && $j < $n) ? ($j - 1, $j, $j + 1) : $j == 1 ? ($j, $j + 1) : ($j - 1, $j)) {
  9          next if $k == $i and $l == $j;
 10          push @round, $k . $l;
 11        }
 12      }
 13      $round{"$i$j"} = [@round];
 14    }
 15  }
 16
 17  foreach my $i (1 .. $n) {
 18    foreach my $j (1 .. $n) {
 19      my $key = $i . $j;
 20      $board{$key} = [0];
 21      my $k = ($i > 1 && $i < $n) ? 2 : 1;
 22      my $l = ($j > 1 && $j < $n) ? 2 : 1;
 23      push @{$board{$key}}, $k + $l;
 24      push @{$board{$key}}, scalar(@{$round{$key}});
 25    }
 26  }
 27
 28  $board{$start}->[0] = 1;
 29  foreach my $pos (@{$round{$start}}) {
 30    --$board{$pos}->[2];
 31    if ("$pos$start" =~ /(.).\1/) {
 32      --$board{$pos}->[1];
 33    }
 34  }
 35
 36  search([11, join('', map { $board{$_}->[0] } sort keys %board)]);
 37
 38  sub search {
 39    my $ref = shift;
 40    my @next_pos = grep { !$board{$_}->[0] and $board{$_}->[2] < @{$round{$_}}
 41                          and $board{$_}->[1] % 2 == 0 and $board{$_}->[1] } keys %board;
 42    my @stone = grep { $board{$_}->[0] } keys %board;
 43
 44    my $diag = 1;    # 対角線対称マス目の除外
 45    foreach my $pos (@stone) {
 46      my $d_pos = reverse $pos;
 47      next if $pos == $d_pos;
 48      if ($board{$pos}->[0] != $board{$d_pos}->[0]) { $diag = 0; last; }
 49    }
 50    if ($diag) {
 51      @next_pos = grep { substr($_, 0, 1) <= substr($_, 1, 1) } @next_pos;
 52    }
 53
 54    if (@stone >= $n) {    # 逆対角線対称マス目のの除外
 55      my $gaid = 1;
 56      foreach my $pos (@stone) {
 57        my $g_pos = ($n + 1 - substr($pos, 1, 1)) . ($n + 1 - substr($pos, 0, 1));
 58        next if $pos == $g_pos;
 59        if ($board{$pos}->[0] != $board{$g_pos}->[0]) { $gaid = 0; last; }
 60      }
 61      if ($gaid) {
 62        @next_pos = grep { substr($_, 0, 1) + substr($_, 1, 1) <= $n + 1 } @next_pos;
 63      }
 64    }
 65
 66    foreach my $pos (@next_pos) {
 67      $board{$pos}->[0] = 1;
 68      foreach my $round (@{$round{$pos}}) {
 69        --$board{$round}->[2];
 70        if ("$pos$round" =~ /(.).\1/) {
 71          --$board{$round}->[1];
 72          $board{$round}->[0] = 3 - $board{$round}->[0] if $board{$round}->[0];
 73        }
 74      }
 75
 76      my $patt = join '', map { $board{$_}->[0] } sort keys %board;
 77      my $stone = @stone + 1;
 78      unless (grep /$patt/, @{$hist{$stone}}) {
 79        push @{$hist{$stone}}, $patt;
 80        if (grep { !$board{$_}->[0] and $board{$_}->[1] } keys %board) {
 81          search([$pos, $patt, $ref]);
 82        } else {
 83          display([$pos, $patt, $ref]);
 84          ++$black;
 85        }
 86      }
 87
 88      $board{$pos}->[0] = 0;
 89      foreach my $round (@{$round{$pos}}) {
 90        ++$board{$round}->[2];
 91        if ("$pos$round" =~ /(.).\1/) {
 92          ++$board{$round}->[1];
 93          $board{$round}->[0] = 3 - $board{$round}->[0] if $board{$round}->[0];
 94        }
 95      }
 96    }
 97  }
 98
 99  sub display {    # 正解手順の表示
100    my $tmp_ref = shift;
101    my @work;
102    while ($tmp_ref) {
103      my ($pos, $board);
104      ($pos, $board, $tmp_ref) = @$tmp_ref;
105      unshift @work, [sprintf("%-${n}s", $pos), $board =~ /.{$n}/g];
106    }
107
108    my @line;
109    foreach my $i (0 .. $n) {
110      push @line, join("  ", map { $_->[$i] } @work);
111    }
112    print "$_\n" foreach @line;
113    print "\n";
114  }
115
116  print "black: $black\n";

全手順探索プログラムで解説した部分は省略して、正解手順探索プログラムで追加した部分を主に解説します。

Line 36, 81: search サブルーチンを呼び出す

全手順探索プログラムでは引数を渡しませんでしたが、正解手順探索プログラムでは無名配列に格納したデータを渡します。search サブルーチンの起動時には置き石マス目番号と盤面の石の配置の２つのデータですが、再帰呼び出しでは末尾に直前の手数の置き石のデータを格納した無名配列のリファレンスが追加されます。

スタート図:        ['11', '1000000000000000']
２つ目の置き石時:  ['12', '2100000000000000', 上の配列のリファレンス]
３つ目の置き石時:  ['13', '2210000000000000', 上の配列のリファレンス]
.....

上のデータ構造は、正解手順を表示するために使います。正解手順が得られたときに、リファレンスをスタート図まで辿ると正解手順を表示するためのデータを取得できます。

Line 44 ～ 52: 対角線対称マス目を除外 (本文で詳述)

Line 54 ～ 64: 逆対角線対称マス目を除外 (本文で詳述)

Line 101 ～ 106: スタート図から完成図までの盤面を収集する

while ループが終了すると、スタータ図から完成図までの盤面が @work 配列に収集されます。@work の各要素は、無名配列に入れられた盤面です。無名配列のデータは、スタート図を例にすると ['11 ', '1000', '0000', '0000', '0000'] のようになっています。無名配列の各要素はそれぞれ、置いた石のマス目番号、盤面の１列目、２列目、３列目、４列目となり、連続した行に表示すると見やすい盤面となります。

Line 108 ～ 112: 正解手順表示用の各行を作成し表示する

正解手順の表示では、見やすいようにスタート図から完成図までを１列に並べます。@work の無名配列から同じ添字の要素を抽出して、スペース２つで繋いで各行を作成し配列 @line に格納します。 @line は、foreach ループを使って出力します。文書の末尾に載せている 3 x 3 と 4 x 4 盤面の正解手順は、このコードによって出力したものです。

正解手順探索のプログラムは、前節の全手順探索のプログラムに１つ１つコードを追加しながら作っています。プログラムの説明は、4 x 4 盤面を使って行っていきます。4 x 4 盤面の次のデータが出発点となり、その遷移を見ていくことにします。

以上説明してきたほかに正解手順探索では、正解手順を表示するコードを追加しています。正解手順が得られたら、その都度 display サブルーチンを呼び出しています。最初の行に置いた石のマス目番号を表示し、次の行からは盤面の石の配置を表示しています。3 x 3 盤面では、次の２つの正解手順が表示されます。

3 x 3 盤面の手順は、最初に 12 に置くか 22 に置くかの選択肢があるだけで、その後の手順は１つの手順に集約されることになります。２つのうちの最初の正解手順の３手目以降を、詳細に見てみることにしましょう。

最初の手順は、３手目以降に複数の選択肢がない絶対的な手順になります。２つ目の正解手順は、３手目に 13 か 33 に置くことになりどちらに置いたとしても、その後２つの石を置くと完成図以外には到達しません。手順前後が成立するだけで、解としては１つになります。3 x 3 盤面での正解手順が２つであるのは、妥当なものとして受け入れることができるものと思います。4 x 4 盤面では、次の 10 の正解手順が表示されます。