アインシュタイン問題には、いろいろあるようだ。
以下の図のA~Iに、1~9の数字を入れて、7つある三角形の頂点の数の和が等しくなる組合せを探すものだ。

三角形の組は、以下の7つ。これらが同じ値になればよい。
ACD、BEF、DEG、GHI、ABG、CEH、DFI
まずは、Cでプログラムを作る。
#define MAX (10)
#define A 0
#define B 1
#define C 2
#define D 3
#define E 4
#define F 5
#define G 6
#define H 7
#define I 8
#define SUM(S,X,Y,Z) (*(S+X)+*(S+Y)+*(S+Z))
int *move(int *s,int *d) {
int *w=d;
if (s) while(*(s)) *(d++)=*(s++);
*(d)=0;
return w;
}
int *cat(int *d,int a) {
int *w=d;
for(;*(d);d++);
*(d++)=a; *(d)=0;
return w;
}
//ACD=BEF=DEG=GHI=ABG=CEH=DFI
int eval(int *s) {
int i,r1,r2,r3,r4,r5,r6,r7;
r1 = SUM(s,A,C,D);
r2 = SUM(s,B,E,F);
r3 = SUM(s,D,E,G);
r4 = SUM(s,G,H,I);
r5 = SUM(s,A,B,G);
r6 = SUM(s,C,E,H);
r7 = SUM(s,D,F,I);
return (r1==r2&&r2==r3&&r3==r4&&r4==r5&&r5==r6&&r6==r7);
}
int num=0;
int **vals;
void push(int *d) {
int *r;
num++;
r = (int *)malloc(sizeof(int)*MAX);
move(d,r);
vals = (int **)realloc(vals,sizeof(int *)*num);
vals[num-1]=r;
}
void solv(int *s ,int *d) {
int i,j,k;
int s2[MAX],d2[MAX];
if (!*s) { if(eval(d)) push(d);return;}
for (i=0;*(s+i);i++) {
for(j=k=0;*(s+k);k++) if(k!=i) *(s2+j++)=*(s+k);
*(s2+j)=0;
solv(s2,cat(move(d,d2),*(s+i)));
}
}
int
main( int c , char **a) {
int N[] = {1,2,3,4,5,6,7,8,9,0};
int i,j;
solv(N,(int*)0);
printf("A B C D E F G H I\n");
printf("-----------------\n");
for(i=0; i < num ; i++) {
for(j=0 ; *(vals[i]+j);j++)
printf("%1d ",*(vals[i]+j));
printf("\n");
}
}
実行すると、以下の24通りの答えが見つかる。
timeコマンドで、実行時間も計ってみる。
約0.6秒で計算できる。
※実行マシンは、Thinkpad s30
real 0m0.610s
user 0m0.510s
sys 0m0.060s
A B C D E F G H I
1 6 9 5 2 7 8 4 3
1 8 9 5 4 3 6 2 7
1 9 6 8 2 4 5 7 3
1 9 8 6 4 2 5 3 7
2 7 9 4 5 3 6 1 8
2 9 7 6 5 1 4 3 8
3 4 7 5 2 9 8 6 1
3 7 4 8 2 6 5 9 1
3 7 8 4 6 2 5 1 9
3 8 7 5 6 1 4 2 9
4 3 9 2 5 7 8 1 6
4 9 3 8 5 1 2 7 6
6 1 7 2 5 9 8 3 4
6 7 1 8 5 3 2 9 4
7 2 3 5 4 9 6 8 1
7 3 2 6 4 8 5 9 1
7 3 6 2 8 4 5 1 9
7 6 3 5 8 1 2 4 9
8 1 3 4 5 9 6 7 2
8 3 1 6 5 7 4 9 2
9 1 2 4 6 8 5 7 3
9 1 4 2 8 6 5 3 7
9 2 1 5 6 7 4 8 3
9 4 1 5 8 3 2 6 7
今度は、Alloy4で答えを見つけてみる。
数値演算は、ライブラリのNaturalモジュールを使うことにする。
Naturalは、二項関係で数値の順番を管理する。
四則演算が、この二項関係のグラフの中で行われる。
なので、実行速度は非常に遅い。
プログラムを以下に示す。
open util/natural
abstract sig Position {n: one Natural}
one sig A,B,C,D,E,F,G,H,I extends Position{}{n != Zero}
fact {
one p: Position | p.n = One &&
all p: Position |
p.n == One =>
{one p2: Position | p2.n = inc[p.n]}
else
{one p3: Position | p3.n = dec[p.n]}
}
pred cond {
//ACD=BEF=DEG=GHI=ABG=CEH=DFI
adds[A,C,D] = adds[B,E,F] &&
adds[B,E,F] = adds[D,E,G] &&
adds[D,E,G] = adds[G,H,I] &&
adds[G,H,I] = adds[A,B,G] &&
adds[A,B,G] = adds[C,E,H] &&
adds[C,E,H] = adds[D,F,I]
}
fun adds[p1,p2,p3:Position] : Natural {add[add[p1.n,p2.n],p3.n]}
pred exec() {
cond
}
run exec for 24 Natural , 5 int
sin Position で、三角形の頂点を表し、各頂点は、値Naturalを1つ保持する。
sig A,..,I extends Position で各頂点を定義している、制約条件では、Zeroが割り当てられなようにしている。
factでは、A~Iが、Naturalの1~9が割り当てられる制約条件を記述している。
pred cond は、各頂点の合計が同じ値となる、制約条件を記述している。
fun addは、Naturalが定義している関数。
run exec for 24 Natural , 5 int としているのは、最大合計値が24(9+8+7)だから、整数のビット幅は5ビットに拡張している。
実行すると以下の結果となる。
Alloy Analyzer 4.1.8 (build date: 2008/08/07 16:29 EDT)
Executing "Run exec for 5 int, 24 Natural"
Solver=minisat(jni) Bitwidth=5 MaxSeq=4 SkolemDepth=1 Symmetry=20
9875 vars. 264 primary vars. 42980 clauses. 3945ms.
Instance found. Predicate is consistent. 89259ms.
89秒掛かって、やっと1つめの解が得られた。
あと23回行えば、全部の解が求まるはずだ。とてもやる気にならないが。
見つかった答えは、あっているようだ。

問題記述の強力さでは、alloyであるが、この問題のように数値を扱う場合は、素直な記述はできない。
factの制約条件の記述は美しくは無い。
Natural ⇒ Int に代えてやってみる。
Intは、alloy標準のIntegerだ。
abstract sig Position {n: one Int}
one sig A,B,C,D,E,F,G,H,I extends Position{}
{
all i: n | { 0 < int i && 10> int i } &&
all p: Position |
all p': Position | p!=p' => p.@n != p'.@n
}
pred cond {
//ACD=BEF=DEG=GHI=ABG=CEH=DFI
adds[A,C,D] = adds[B,E,F] &&
adds[B,E,F] = adds[D,E,G] &&
adds[D,E,G] = adds[G,H,I] &&
adds[G,H,I] = adds[A,B,G] &&
adds[A,B,G] = adds[C,E,H] &&
adds[C,E,H] = adds[D,F,I]
}
fun adds[p1,p2,p3:Position] : Int { int p1.n + int p2.n+ int p3.n}
pred exec() {
cond
}
run exec for 5 int
実行すると、以下の結果となる。
Executing "Run exec for 5 int"
Solver=minisat(jni) Bitwidth=5 MaxSeq=4 SkolemDepth=1 Symmetry=20
7377 vars. 288 primary vars. 21249 clauses. 1793ms.
Instance found. Predicate is consistent. 2143ms.
今度は、2.1秒で解けた。
この速さだと、24通りのinstanceが確認できる。

この問題の場合、試した組合せの数は、9!=362880通りである。
実際のモデルで、この数が実用的な範囲なのかは、まだ、良く分からない。
Recent Comments