電子書籍ギフト♪ 最大10,000円が当たる!

カラーキューブ数独の解を列挙するプログラムを作成したいのですが.
列挙の仕方と枝刈とを工夫したいです
1つの解を回転することで得られる解は同一とみなしたい.
この意味で重複なく列挙するにはどうしたらよいですか?

教えて!goo グレード

A 回答 (4件)

[1]No.3の写真で観察。


[1-1] セットに含まれているcubeは9個あって、どのcubeも4色で塗り分けられ、その4色の選び方がcube同士で互いに異なっている(ある4色の組み合わせを使っているcubeは1個しかない)。

[1-2] 色は6色あって、どのcubeもそのうちの4色を使っている。6色中4色を選ぶ選び方は 6C2 = 15 通りあるが、そのうちの9通りだけを使っている。つまり「どの色も対等」というわけではない。
 
[1-3] ひとつのcubeには4つの色が使われている。これらの色をA,B,C,Dとする。このひとつのcubeの置き方を変えることによって、頂上面に現れるこれら4色を任意に並べることができる。4色の並べ方は4! = 24通りあり、実際、cubeは置き方によって頂上面が
  A B  A B  A C  A C  A D  A D
  C D  D C  B D  D B  B C  C B

  B A  B A  B C  B C  B D  B D
  C D  D C  A D  D A  A C  C A

  C B  C B  C A  C A  C D  C D
  A D  D A  B D  D B  B A  A B

  D B  D B  D C  D C  D A  D A
  C A  A C  B A  A B  B C  C B
となる24通りの相異なる置き方ができる。

[1-4] 6色中どの2色を使わないかに注目してcubeを区別することにしよう。色に記号を
  1 緑、2 橙、3 白 
  a 赤、b 青、c 黄
と対応させることにする。そして、各cubeにどの色が使われていないか、を並べてみると、
  (1,a), (1,b), (1,c)
  (2,a), (2,b), (2,c)
  (3,a), (3,b), (3,c)
の9個のcubeがあることがわかる。どのcubeも{1,2,3}の中の1色と、(a,b,c}の中の1色が使われていない。「使わない色の組み合わせ」は3×3=9通りあり、これら9通りのcubeが実際にセットに含まれている。
 つまり、色は{1,2,3}={緑,橙,白}と{a,b,c}={赤,青,黄}の2種類に分類される。(記号の割り当て方は、もちろん、{1,2,3}={緑,橙,白}と{a,b,c}={赤,青,黄}を一斉に入れ替えて、{1,2,3}={赤,青,黄}、 {a,b,c}={緑,橙,白}としても良い。)
 {1,2,3}の要素は互いに対等(対称)であり、(a,b,c}の要素も互いに対等(対称)である。すなわち、対等な色同士の1組を入れ替えても、9個のcubeのセットは変わらないが、しかし{1,2,3}の要素と{a,b,c}の要素を1組あるいは2組だけ入れ替えると、セットには存在しないcubeの配色になってしまう。

[2] 観察結果を使って
[2-1] パズルの解Sは、cubeを並べて作られた頂上面に現れる6×6のマス目の色の配列によって指定できる。すなわち、頂上面以外の面の色の並び方(cubeの置き方)は自動的に決まってしまう。

[2-2] 解がひとつあれば、色の入れ替えで解がたくさん得られる。
パズルの解Sが一つ与えられたとする。Sの色の並びを記号{1,2,3,a,b,c}を使って表しておいて、次に記号と色の対応を差し替えれば、それも解になっていることになる。ただし色を自由に差し替えられるわけではなく、
  ({1,2,3}={緑,橙,白} かつ {a,b,c}={赤,青,黄}) または
     ({1,2,3}={赤,青,黄} かつ {a,b,c}={緑,橙,白})
が成り立たなくてはならない。
 ({1,2,3}={緑,橙,白} かつ {a,b,c}={赤,青,黄})の場合について、{緑,橙,白}に{1,2,3}を割り振るやり方(順列)は6通り、{赤,青,黄}に{a,b,c}を割り振るやり方も6通り、それぞれ独立に選べるから36通り。 ({1,2,3}={赤,青,黄} かつ {a,b,c}={緑,橙,白})の場合についても36通り。つまり解Sが一つあれば、色の入れ替えで72通りの解が得られたことになる。そこで、
  (step 1){1,2,3,a,b,c}の記号で表されたパズル(「記号パズル」と呼ぼう)の解sを探索する。
  (step 2)記号パズルの解sがひとつ見つかったら、{1,2,3,a,b,c}を色に変換して、解の集合S(s)を生成する。
という方法で、効率よく解をみつけることができる。

[2-3] どの解Sについても、Sかその鏡像S'は、色の割り当てを選ぶことで、その中央の2×2のマス目が
(12型)
  1 2
  a b

(1a型)
  1 a
  b 2
のどちらかになるように記号と色とを対応づけることができる。

[2-4](12型)の解Sの集合をXとする。また、Sの鏡像をS'、Sを時計回りに90度回転したものを1(S)、Sを180度回転したものを2(s), sを反時計回りに90度回転したものを3(S)と書くことにする。S∈Xのとき、S', 1(S), 2(S), 3(S)はどれも解である。そして、
  S∈X ⇒ S'∉X
であり、そこで
  X' = { S' | S∈X}
とすると X'∩X = ∅ である。そして容易にわかる通り
  { 1(S) | s∈X} = X'
  { 2(S) | S∈X} = X
  { 3(S) | S∈X} = X'
なので、結局(12型)の解から得られる解の集合は
  X∪X'
だとわかる。つまり、記号パズルの(12型)の解sをひとつ見つけると、その鏡像s'も決まり、それらに対して色を割り当てることで144通りの解S(S∈X∪X')が得られる。

[2-5](1a)型の解sの集合をYとすると、明らかに
  Y∩X = ∅, Y∩X' = ∅
であり、さらに容易にわかる通り
  { S' | S∈Y} = Y
  { 1(S) | S∈Y} = Y
  { 2(S) | S∈Y} = Y
  { 3(S) | S∈Y} = Y
である。だから、記号パズルの(1a)型の解sをひとつ見つけると、色を割り当てることで72通りの解S(S∈Y)が得られる。

[2-6] 以上によって、全ての解(X∪X'∪Y)が得られる。まとめると
  (step 1.1)記号パズルの(12型)の解sを探索する。sとs'はどちらも記号パズルの(12型)の解である。
  (step 1.2) sとs'それぞれについて、{1,2,3,a,b,c}を色に変換して、解の集合S(s)∪S(s')(144通り)を生成する。
  (step 2.1)記号パズルの(1a型)の解sを探索する。
  (step 2.2) sについて{1,2,3,a,b,c}を色に変換して、解の集合S(s)(72通り)を生成する。
とやれば、重複なく全ての解が得られる。
    • good
    • 0

回転体は8種類(0度90度180度270度とその鏡像)ですが。


色は6種類なんでしょうか。
1つのブロックは8色の組み合わせのようですが、よく見ると、上下同じ(上下」回転すると同じになる)ようで4色のようです。
「カラーキューブ数独をc言語でときたいです」の回答画像3
    • good
    • 0

>1つの解を回転することで得られる解は同一とみなしたい.


>この意味で重複なく列挙するにはどうしたらよいですか?
1)1つの解から整数を対応せる関数を定義する。
2)回転させたすべての解に対して、関数値を求める。
3)最小値となる解以外は重複として出力しない
でいかが?
    • good
    • 0

「カラーキューブ数独」とやらがどんなものなのか知らんけど


「1つの解を回転することで得られる」ものを「解」とはみなさない
ように対称性を破る条件を付ければいいんじゃないかな.
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

教えて!goo グレード

このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング