最終更新日 2003年10月30日
正二十面体の合同でないすべての展開図を求める
正二十面体の合同でない展開図は全部で４３３８０個あります。これらの展開図を求めるには色々な方法が考えられますが、私にとって分かり易いのは次のような方法です。正二十面体の各辺に１から３０の番号をふり、面を切り離し、２０個の三角形を作ります。それらを辺の番号を合わせて並べると展開図が出来ます。あらゆる組合せを取るとすべての展開図が得られます。これを抜かりなくやるのには木構造を利用します。木の縦型探索をします。その時、同型な展開図の部分図が出てくれば、枝刈り（そのノードから下は考える必要がない）が出来ます。展開図や展開図の部分図が合同かどうかはどのようにして判定したらよいでしょうか？人間は見ただけで分かりますが、今のコンピュータはそんなこと出来ません。このようなとき、数学では不変量を見つけようとします。ここでは次のようにして、展開図や展開図の部分図に数字を対応させます。数字を巧く対応させることに成功すれば、色々と便利です。数字なら一列に並べることが出来るので、探索の技巧が使え、プログラムを飛躍的に高速化できます。平面を正三角形で覆うて、原点とｘ軸と６０度の直線で囲まれる領域に、展開図や展開図の部分図を当てはめます。正三角形に１，２，４，８，１６，・・と数字を割り当て、展開図や展開図の部分図が覆う正三角形の数字の和をその図形の数字とします。展開図や展開図の部分図は正三角形から出来ているので、６０度の倍数からなる回転とそれらと線対称を続けた合同変換の合計１２個の移動が基本的に考えられ、１２個の当てはめ方があります。したがって、１２個の数字が一つの展開図や展開図の部分図から得られますが、それらの最小値を展開図や展開図の部分図の不変量として採用します。合同でない展開図や展開図の部分図の不変量を二分木に登録しておけば、高速に新しい展開図や展開図の部分図がすでに出てきているかどうか判定できます。ものを作るのは楽しいものです。プログラミングは、高知のような僻地に住んでいるので部品が手に入らないからといって諦める必要もありません。無い部品は自分で作ればいいです。プログラミングの勉強のはじめの頃は、色々なプログラムが何でそんなことが出来るのか不思議でたまりませんでしたが、プログラムリストを読んでみると「何だ」と思うことばかりで、不思議と思うことをプログラムが実行するのは、人間がやっている通り、ただ面倒くさくてもその不思議と思うことをするようにそのままこつこつとプログラムしているだけだと心底納得したとき、プログラムが自由に作れるようになりました。このプログラムの考え方は色々なものをすべて求めるときに応用出来ます。このアルゴリズムを実装したC++のプログラムは以下のようになります。
まずtenkaizu.h のファイルです。
<![CDATA[
//---------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
const int bigsize = 12;
class bigdigit {
int digit[bigsize];
public:
void get(int *);
void put();
void initialize();
void operator+=(bigdigit);
friend bigdigit operator+(bigdigit, bigdigit);
friend bigdigit operator*(bigdigit, bigdigit);
friend bool operator==(bigdigit, bigdigit);
friend bool operator>(bigdigit, bigdigit);
};
int edgeinf[20][3] =
{{ 1, 2, 3}, { 1, 4, 5}, { 5, 6, 7}, { 6, 8, 9}, { 2,10,11}
,{10, 7,12}, {12,13,14}, {13, 9,15}, {11,16,17}, {16,14,18}
,{18,19,20}, {19,15,21}, {17,22,23}, {22,20,24}, {24,25,26}
,{25,21,27}, {23,28, 3}, {28,26,29}, {29,30, 4}, {30,27, 8}};
const int maxyoko = 18;
int yokolist[][bigsize] =
{{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
,{ 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
,{ 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
,{ 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
,{ 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
,{ 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
,{ 64, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
,{ 128, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
,{ 256, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
,{ 512, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
,{1024, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
,{2048, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
,{4096, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
,{8192, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
,{6384, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
,{2768, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
,{5536, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
,{1072, 13, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
bigdigit yoko[maxyoko];
const int maxtate = 9;
int tatelist[][bigsize] =
{{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
,{2144, 26, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
,{6736,1947, 687, 0, 0, 0, 0, 0, 0, 0, 0, 0}
,{1984, 948,3985,8014, 1, 0, 0, 0, 0, 0, 0, 0}
,{3696,4521,8696,6482,2236, 47, 0, 0, 0, 0, 0, 0}
,{4224,9912,2748,5380,3928,9400,1237, 0, 0, 0, 0, 0}
,{6256,2057,1560,6783,2672,6584,8553,2451, 3, 0, 0, 0}
,{2864,4205,8579,3651,6584,6158, 234,9173, 705, 85, 0, 0}
,{ 416, 598,3615,2648,1827,5357,3141,3062,1985, 745,2230, 0}};
bigdigit tate[maxtate];
struct facelist {
int len;
int face[20];
facelist remove(int ind);
};
struct edge {
int hen;
char muki;
int x, y;
};
struct newedgelist;
struct edgelist {
int len;
edge edges[60];
newedgelist getnewedges(int ind);
bool newpatternP();
void display();
};
struct newedgelist {
int len;
edgelist newedges[3];
};
struct coord {
int x, y;
};
struct coordlist {
int len;
coord coords[20];
coordlist rotate();
};
struct node {
bigdigit inv;
node *lt;
node *rt;
node(){lt=NULL; rt=NULL;}
};
//---------------------------------------------------------------------------
]]>
次にtenkaizu.cpp です。
<![CDATA[
//---------------------------------------------------------------------------
#include "tenkaizu.h"
node *head = NULL;
node *z = NULL;
long int number;
void bigdigit :: put() {
for (int i=0; i<bigsize; i++)
printf("%d ", digit[i]);
printf("\n");
}
void bigdigit :: get(int *list) {
for (int i=0; i<bigsize; i++)
digit[i] = list[i];
}
void bigdigit :: initialize() {
for (int i=0; i<bigsize; i++)
digit[i] = 0;
digit[0] = 1;
}
bigdigit operator+(bigdigit a1, bigdigit a2)
{
bigdigit junk;
int carry = 0;
for (int i=0; i<bigsize; i++) {
junk.digit[i] = a1.digit[i] + a2.digit[i] + carry;
carry = junk.digit[i] / 10000;
junk.digit[i] %= 10000;
}
if (carry != 0) {
printf("bigdigit overflow!!");
exit(0);
}
return junk;
}
bigdigit operator*(bigdigit a1, bigdigit a2)
{
bigdigit junk;
int carry;
int temp[2*bigsize];
long prod;
for (int i=0; i<2*bigsize; i++)
temp[i] = 0;
for (int i=0; i<bigsize; i++) {
carry = 0;
for (int j=0; j<bigsize; j++) {
prod = a1.digit[j] * a2.digit[i] + carry + temp[i+j];
temp[i+j] = prod % 10000;
carry = prod / 10000;
}
temp[i+bigsize] += carry;
}
int flag = 0;
for (int i=bigsize; i<2*bigsize; i++)
if (temp[i] != 0) {
flag = -1;
break;
}
if (flag) {
printf("\nBigdigit overflow\n");
exit(0);
}
junk.get(temp);
return junk;
}
bool operator==(bigdigit a1, bigdigit a2)
{
for (int i=0; i<bigsize; i++)
if (a1.digit[i] != a2.digit[i])
return false;
return true;
}
bool operator>(bigdigit a1, bigdigit a2)
{
for (int i=bigsize-1; i>=0; i--)
if (a1.digit[i] > a2.digit[i])
return true;
else if (a1.digit[i] < a2.digit[i])
return false;
return false;
}
void bigdigit :: operator+=(bigdigit a)
{
int junk;
int carry=0;
for (int i=0; i<bigsize; i++) {
junk = digit[i] + a.digit[i] + carry;
digit[i] = junk % 10000;
carry = junk / 10000;
}
if (carry > 0) {
printf("\nbigdigit overflow!\n");
exit(0);
}
}
void treeinitialize()
{
z = new(node);
z->lt = z;
z->rt = z;
head = new(node);
head->lt = z;
head->rt = z;
head->inv.initialize();
}
bool treesearch(node *x, bigdigit D)
{
node *p;
z->inv = D;
do {
if (x->inv == D)
break;
p = x;
if (x->inv > D)
x = x->lt;
else
x = x->rt;
} while(1);
if (x == z) {
x = new(node);
x->inv = D;
x->lt = z;
x->rt = z;
if (p->inv > D)
p->lt = x;
else
p->rt = x;
return true;
} else {
return false;
}
}
bool newP(bigdigit D)
{
return treesearch(head, D);
}
newedgelist edgelist::getnewedges(int ind)
{
newedgelist cands;
int cnt=0;
edge junk;
for (int i=0; i<3; i++) {
for (int j=0; j<len; j++) {
if (edges[j].hen == edgeinf[ind][i]) {
cands.newedges[cnt] = *this;
switch (edges[j].muki) {
case 'u':
junk.hen = edgeinf[ind][(i)%3];
junk.muki = 'd';
junk.x = edges[j].x - 1;
junk.y = edges[j].y + 1;
cands.newedges[cnt].edges[len] = junk;
junk.hen = edgeinf[ind][(i+1)%3];
junk.muki = 'h';
junk.x = edges[j].x - 1;
junk.y = edges[j].y + 1;
cands.newedges[cnt].edges[len+1] = junk;
junk.hen = edgeinf[ind][(i+2)%3];
junk.muki = 'm';
junk.x = edges[j].x - 1;
junk.y = edges[j].y + 1;
cands.newedges[cnt].edges[len+2] = junk;
cands.newedges[cnt++].len = len+3;
if (junk.x < 0) {
for (int k=0; k<len+3; k++)
cands.newedges[cnt-1].edges[k].x++;
}
break;
case 'r':
junk.hen = edgeinf[ind][(i)%3];
junk.muki = 'h';
junk.x = edges[j].x + 1;
junk.y = edges[j].y;
cands.newedges[cnt].edges[len] = junk;
junk.hen = edgeinf[ind][(i+1)%3];
junk.muki = 'm';
junk.x = edges[j].x + 1;
junk.y = edges[j].y;
cands.newedges[cnt].edges[len+1] = junk;
junk.hen = edgeinf[ind][(i+2)%3];
junk.muki = 'd';
junk.x = edges[j].x + 1;
junk.y = edges[j].y;
cands.newedges[cnt].edges[len+2] = junk;
cands.newedges[cnt++].len = len+3;
break;
case 'l':
junk.hen = edgeinf[ind][(i)%3];
junk.muki = 'm';
junk.x = edges[j].x - 1;
junk.y = edges[j].y;
cands.newedges[cnt].edges[len] = junk;
junk.hen = edgeinf[ind][(i+1)%3];
junk.muki = 'd';
junk.x = edges[j].x - 1;
junk.y = edges[j].y;
cands.newedges[cnt].edges[len+1] = junk;
junk.hen = edgeinf[ind][(i+2)%3];
junk.muki = 'h';
junk.x = edges[j].x - 1;
junk.y = edges[j].y;
cands.newedges[cnt].edges[len+2] = junk;
cands.newedges[cnt++].len = len+3;
if (junk.x < 0) {
for (int k=0; k<len+3; k++)
cands.newedges[cnt-1].edges[k].x++;
}
break;
case 'd':
junk.hen = edgeinf[ind][(i)%3];
junk.muki = 'u';
junk.x = edges[j].x + 1;
junk.y = edges[j].y - 1;
cands.newedges[cnt].edges[len] = junk;
junk.hen = edgeinf[ind][(i+1)%3];
junk.muki = 'r';
junk.x = edges[j].x + 1;
junk.y = edges[j].y - 1;
cands.newedges[cnt].edges[len+1] = junk;
junk.hen = edgeinf[ind][(i+2)%3];
junk.muki = 'l';
junk.x = edges[j].x + 1;
junk.y = edges[j].y - 1;
cands.newedges[cnt].edges[len+2] = junk;
cands.newedges[cnt++].len = len+3;
if (junk.y < 0) {
for (int k=0; k<len+3; k++)
cands.newedges[cnt-1].edges[k].y++;
}
break;
case 'h':
junk.hen = edgeinf[ind][(i)%3];
junk.muki = 'r';
junk.x = edges[j].x - 1;
junk.y = edges[j].y;
cands.newedges[cnt].edges[len] = junk;
junk.hen = edgeinf[ind][(i+1)%3];
junk.muki = 'l';
junk.x = edges[j].x - 1;
junk.y = edges[j].y;
cands.newedges[cnt].edges[len+1] = junk;
junk.hen = edgeinf[ind][(i+2)%3];
junk.muki = 'u';
junk.x = edges[j].x - 1;
junk.y = edges[j].y;
cands.newedges[cnt].edges[len+2] = junk;
cands.newedges[cnt++].len = len+3;
if (junk.x < 0) {
for (int k=0; k<len+3; k++)
cands.newedges[cnt-1].edges[k].x += 2;
}
break;
case 'm':
junk.hen = edgeinf[ind][(i)%3];
junk.muki = 'l';
junk.x = edges[j].x + 1;
junk.y = edges[j].y;
cands.newedges[cnt].edges[len] = junk;
junk.hen = edgeinf[ind][(i+1)%3];
junk.muki = 'u';
junk.x = edges[j].x + 1;
junk.y = edges[j].y;
cands.newedges[cnt].edges[len+1] = junk;
junk.hen = edgeinf[ind][(i+2)%3];
junk.muki = 'r';
junk.x = edges[j].x + 1;
junk.y = edges[j].y;
cands.newedges[cnt].edges[len+2] = junk;
cands.newedges[cnt++].len = len+3;
break;
}
}
}
}
cands.len = cnt;
return cands;
}
coordlist coordlist::rotate()
{
coordlist junk;
int x, y;
int min_x, min_y;
int delta;
for (int i=0; i<len; i++) {
x = coords[i].x;
y = coords[i].y;
if (x % 2 == 0) {
junk.coords[i].x = -2 * y - 1;
junk.coords[i].y = y + x / 2;
} else {
junk.coords[i].x = -2 * y - 2;
junk.coords[i].y = y + (x + 1) / 2;
}
}
junk.len = len;
min_x = 0;
for (int i=0; i<junk.len; i++)
if (min_x > junk.coords[i].x)
min_x = junk.coords[i].x;
delta = - min_x;
delta = (delta % 2 == 0) ? delta : delta + 1;
for (int i=0; i<junk.len; i++)
junk.coords[i].x += delta;
min_y = junk.coords[0].y;
for (int i=1; i<junk.len; i++)
if (min_y > junk.coords[i].y)
min_y = junk.coords[i].y;
delta = - min_y;
for (int i=0; i<junk.len; i++)
junk.coords[i].y += delta;
return junk;
}
bool edgelist::newpatternP()
{
coordlist figure, junk;
int cnt=0;
bigdigit pat[12];
bigdigit minpat;
int x, y;
int min_x, min_y;
int delta;
int temp[bigsize];
for (int i=0; i<len; i += 3, cnt++) {
figure.coords[cnt].x = edges[i].x;
figure.coords[cnt].y = edges[i].y;
}
figure.len = cnt;
for (int k=0; k<bigsize; k++)
temp[k] = 0;
pat[0].get(temp);
for (int i=0; i<figure.len; i++) {
pat[0] += yoko[figure.coords[i].x] * tate[figure.coords[i].y];
}
junk = figure;
for (int k=1; k<6; k++) {
junk = junk.rotate();
pat[k].get(temp);
for (int i=0; i<figure.len; i++) {
pat[k] += yoko[junk.coords[i].x] * tate[junk.coords[i].y];
}
}
for (int i=0; i<figure.len; i++) {
x = figure.coords[i].x;
y = figure.coords[i].y;
junk.coords[i].x = x + 2 * y + 1;
junk.coords[i].y = - y;
}
min_y = 0;
for (int i=0; i<figure.len; i++)
if (min_y > junk.coords[i].y)
min_y = junk.coords[i].y;
delta = - min_y;
for (int i=0; i<figure.len; i++)
junk.coords[i].y += delta;
min_x = junk.coords[0].x;
for (int i=0; i<figure.len; i++)
if (min_x > junk.coords[i].x)
min_x = junk.coords[i].x;
delta = (min_x % 2 == 0) ? min_x : min_x - 1;
for (int i=0; i<figure.len; i++)
junk.coords[i].x -= delta;
pat[6].get(temp);
for (int i=0; i<figure.len; i++) {
pat[6] += yoko[junk.coords[i].x] * tate[junk.coords[i].y];
}
for (int k=7; k<12; k++) {
junk = junk.rotate();
pat[k].get(temp);
for (int i=0; i<figure.len; i++) {
pat[k] += yoko[junk.coords[i].x] * tate[junk.coords[i].y];
}
}
minpat = pat[0];
for (int i=1; i<12; i++)
if (minpat > pat[i])
minpat = pat[i];
return newP(minpat);
}
void edgelist::display()
{
int cnt=0;
coordlist figure;
printf("\nnumber=%d\n", ++number);
for (int i=0; i<len; i += 3, cnt++) {
figure.coords[cnt].x = edges[i].x;
figure.coords[cnt].y = edges[i].y;
}
figure.len = cnt;
for (int i=0; i<figure.len; i++)
printf("(%d %d)", figure.coords[i].x, figure.coords[i].y);
printf("\n");
}
facelist facelist::remove(int ind)
{
facelist junk;
int i;
junk.len = len - 1;
for (i=0; i<ind; i++)
junk.face[i] = face[i];
for (i=ind; i<junk.len; i++)
junk.face[i] = face[i+1];
return junk;
}
void tenkai(facelist rem, edgelist midresult)
{
newedgelist cands;
facelist newrem;
if (rem.len == 0) {
midresult.display();
return;
}
for (int i=0; i<rem.len; i++) {
cands = midresult.getnewedges(rem.face[i]);
for (int j=0; j<cands.len; j++)
if (cands.newedges[j].newpatternP()) {
newrem = rem.remove(i);
tenkai(newrem, cands.newedges[j]);
}
}
}
main(int argc, char **argv)
{
facelist remainder;
edgelist midresult;
edge junk;
int temp[bigsize];
bigdigit p;
for (int k=0; k<maxyoko; k++)
yoko[k].get(yokolist[k]);
for (int k=0; k<maxtate; k++)
tate[k].get(tatelist[k]);
for (int i=0; i<19; i++)
remainder.face[i] = i+1;
remainder.len = 19;
junk.hen = 3;
junk.muki = 'd';
junk.x = 0;
junk.y = 0;
midresult.edges[0] = junk;
junk.hen = 1;
junk.muki = 'h';
junk.x = 0;
junk.y = 0;
midresult.edges[1] = junk;
junk.hen = 2;
junk.muki = 'm';
junk.x = 0;
junk.y = 0;
midresult.edges[2] = junk;
midresult.len = 3;
number = 0;
treeinitialize();
tenkai(remainder, midresult);
printf("number=%d", number);
}
//---------------------------------------------------------------------------
</body>
</html>
]]>