カラーキューブ数独をc言語でときたいです。

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

No.4 回答者： stomachman 回答日時： 2021/12/14 11:09

[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通り）を生成する。
とやれば、重複なく全ての解が得られる。

No.3 回答者： トモクンアヤチャン 回答日時： 2021/12/10 08:51

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

色は6種類なんでしょうか。
1つのブロックは8色の組み合わせのようですが、よく見ると、上下同じ（上下」回転すると同じになる）ようで4色のようです。

No.2 回答者： usa3usa 回答日時： 2021/12/08 21:08

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

＞この意味で重複なく列挙するにはどうしたらよいですか？
１）1つの解から整数を対応せる関数を定義する。
２）回転させたすべての解に対して、関数値を求める。
３）最小値となる解以外は重複として出力しない
でいかが？

No.1 回答者： Tacosan 回答日時： 2021/12/08 19:53

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

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