オセロ                             戻る

 お正月のTV特番を見ていたら、次のようなパズルが出題されていた。

    5×5のオセロ盤があり、25個の駒がすべて裏返っている。
    (TVでは、3×3であった。)

    1枚の駒の表裏を変えると、その駒の縦・横の全ての駒も一
   斉に表裏を変えるものとする。
    (オセロでは、斜めも変わるが、このパズルでは考えないこと
     にする。)

    25個の駒を全て表にするには、最低何手必要であろうか?



 実際に、Flash で、駒を裏返して遊んでみよう!

  Flash 版は、こちら    HTML 版は、こちら  をクリックしてください。

 セキュリティ保護のため、コンピュータにアクセスできるアクティブ コンテンツが表示されないように、
Internet Explorer で制限していると、HTML版、Flash版ともに見られません。ブロックされている
コンテンツを許可してください。(すみません、自己の責任でお願いします。)




























(答) 5手あれば十分。次のようにやればよい。

     →   →   →   → 

 奇数×奇数のオセロ盤では、常にこのような手順で裏返すことが可能であるが、
偶数×偶数のオセロ盤では、果たして、このようなパズルは成立するのであろうか?

(追記) 偶数×偶数のオセロ盤でも、このようなパズルは成立する。
   たとえば、2×2のオセロ盤の場合、4手あれば十分である。

       →   →   → 

   各マス目毎に(上記では、行列(amn)と考えて、a11→a12→a21→a22 の順に)駒を
  裏返せばよい。実は、順番は任意でよい。大切な所は、全てのマス目において1回だ
  け操作を行うということである。

   4×4のオセロ盤の場合、16手あれば十分である。
  その方法は、2×2のオセロ盤の場合と同様である。
  簡単な試算から、この16手が最短手数であると確信している。(証明は、未だ!)

   一般に、n が偶数のとき、n×n のオセロ盤の場合、n2手あれば十分である。
  もちろん、n が奇数のとき、n×n のオセロ盤の場合、n手あれば十分である。


 攻略法さんが、上記で示された一般解を考察されました。(平成22年12月16日付け)

Nが奇数の場合

 「同じ行(または列)すべてを1回ずつ(順番は任意)」で裏返すと、それに伴なう列(または
行)では、1回のみ裏返る。他の列(または行)は裏返らない。

 また、その数はいくつ在ってもよい。

      j列
  ×× ×●× × ┐
  ×× ×●× × │←いくつ在ってもよい
      :    :
  ×× ×●× × ┘
i行 ●●…●●●…●
  ×× ×●× × ┐
      :    :
  ×× ×●× × │←いくつ在ってもよい
  ×× ×●× × ┘


 ※ 1(n)×N(またはN×1(n))と記す。1(n)の意味は「束ねる」とする。

 したがって、列(または行)に対して、1回ずつの裏返しによるN手が必要となる。順番は任
意でよい。このとき、N手は奇数なので、その1行(または1列)もすべて裏返っている。

 したがって、N手となる。

Nが偶数の場合

1(n)×N(またはN×1(n))に分割すると、N通りの領域ができる。

   1  2  3     N
 1┌─┬─┬─┬ … ┬─┐
  └─┴─┴─┴ … ┴─┘
 2┌─┬─┬─┬ … ┬─┐
  └─┴─┴─┴ … ┴─┘
      :
 N┌─┬─┬─┬ … ┬─┐
  └─┴─┴─┴ … ┴─┘


 ある領域で、奇数の場合の操作を行うと、この領域を除いてすべて裏返っている。(1回目)

 ※操作は、この場合「この領域は、そのまま。他は、裏返る」を意味する。

次に別の領域で、同操作を行うと、先の領域とこの領域のみが裏返る。(2回目)

 ※この領域は、1回目で裏返っている→裏返ったまま
 ※先の領域は、1回目で元のまま→裏返る
 ※他の領域は、1回目で裏返っている→元に戻る

同様に

次に別の領域で、同操作を行うと、先の2つの領域とこの領域を除いて裏返る。(3回目)

次に別の領域で、同操作を行うと、先の3つの領域とこの領域のみ裏返る。(4回目)

これを続けると

 (2k−1)回目で、先の(2k−2)個の領域とこの領域を除いて裏返る。
 2k回目で、先の(2k−1)個の領域とこの領域のみ裏返る。

また、領域を選択する順番は任意でよい。

各領域を1回ずつ選択すると、N回目ですべて領域は選択されて、このときすべて裏返って
いる。したがって、N2手となる。

M行N列の場合

・M、Nのどちらか1つが奇数なら、それが仮にMなら、M手。

 手順. 1≦k≦Nなる列kを1つ選び、その列すべてを1回ずつ選択する(順番は任意)

・共に奇数なら、Min(M,N)手。 手順 同上

・共に偶数なら、M・N手。 手順 すべてのマスを1回ずつ選択する(順番は任意)