昔こんなオモチャがありましたよね。3×3の四角がオセロの様にひっくり返せて、全てが同じ色になったらクリアって奴です。

このゲームなんですが、スタート時の裏表がランダムだとして、n×nの場合、何パターン初期配置があるでしょうか?
また、このゲームをクリアするための最小手を算出するにはどうすればいいでしょうか?
(式でお答えください。下記はどんなゲームか想像しやすいよう、イメージ図です)
■■■→■■□→□□□
■■■→■□□→□□□
□□■→□□□→□□□

回答の条件
  • 1人3回まで
  • 登録:2007/11/03 19:56:06
  • 終了:2007/11/04 00:34:31

回答(2件)

id:mkoma No.1

mkoma回答回数6ベストアンサー獲得回数02007/11/03 20:46:20

ポイント35pt

そのおもちゃを知らないので、ひっくり返すルールがわからないのですが、初期配置は2の(n×n)乗ですね。例の場合は2の9乗で512通りです。

id:black_comedy

びっくり!そんなにパターンがあったんですね!

えっと、ひっくり返るルールはひっくり返す場所の縦横も一緒にひっくり返ります。壁があっても、そこは反対側が裏返る事はありません。

2007/11/03 20:54:04
id:znz No.2

znz回答回数193ベストアンサー獲得回数252007/11/03 23:36:36

ポイント50pt

イメージ図のひっくり返り方から想像して、5×5ならライツアウトだと思うのですが、連立方程式で解けるようです。

http://www.algopro.co.jp/sflguide/sfl_g2/T-2.html

http://www.ic-net.or.jp/home/takaken/nt/light/light2.html

ライツアウトであっているのなら、

http://www.algopro.co.jp/sflguide/sfl_g2/rule2.html

のライツアウト解法の基本原理の説明でわかるように、解答がそのまま最短手順になります。

id:black_comedy

すばらしい!私が探していた答えが全部載っていました。ありがとうございます!

ライツアウトって言うんですね……

2007/11/04 00:33:47
  • id:sokyo
    black_comedyさん、
    左右対称のカタチになった場合や、回転させて同じカタチになる場合はどういう風にカウントするのでしょう?
    もし「左右対称なら同じじゃん」と解釈するなら、それを除外しないといけないですね…υ
  • id:ttamo
    一番の回答に補足。

    以下の四つを同一とみなすと、

    ■□|□■|□□|□□
    □□|□□|■□|□■

    (((2^(n^2))-2)/4)+2
    になるんじゃないかなー、と思います。
    (「^」は累乗の記号)

    nが与えられたときの最大手数は、
    ゴールから一手前、二手前をしらみつぶしにしていって
    全反転まで出せばいいのかな?

    nがじゅうぶん大きければ(n^2)/5ですかね。(^^;


  • id:ttamo
    あ、そっか、点対称だけじゃなくて線対称もあるのか。
    じゃあ、もっと面倒な式になりますね。

  • id:black_comedy
    >sokyoさん
    盤を回転させたりして同じ形、というのは無しでお願いします。

    >ttamoさん
    >以下の四つを同一とみなすと、
    これは同一にみなさない方向でお願いします。
    >nが与えられたときの最大手数
    そのランダムな模様から答えまでの最小手数の算出方法です。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません