英語では、Einstein's RiddleとかEinstein's Logic Puzzleと言うようです。(^_^;
コンパイルは、「Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland」を使いました。ほとんどCですが、 next_permutation()を使うため拡張子をcppにしました。(^_^;
消去法によるスキップを全部ループの内側に持ってくると、かなり時間がかかりますが、できるだけ外側に持ってくると、ほとんど時間はかからなくなりました。
●プログラム例
/* * Einstein.cpp ほとんどC * # : 12345 * N : NDEGS * H : YBRGW * P : CHBFD * D : WTMCB * T : DMPRB */ #include <stdio.h> #include <algorithm> // next_permutation()を使うため //#include <time.h> using namespace std; // xがa[]の何番目にあるか調べる関数 int get_pos(char *a,char x) { char *p=strchr(a,x); if(p==NULL) return(-1); // ないときは、-1を返す else return((int)(p-a)); // あるときは、0〜strlen(a)-1を返す } // マッチング条件 int check_match(char *a,char x,char *b,char y) { int n=get_pos(a,x); if(n<0||4<n) return(0); // 1:TRUE; 0:FALSE if(b[n]==y) return(1); else return(0); } // 順序付き隣接条件(左からx,yの順で隣接) int check_adj_1(char *a,char x,char *b,char y) { int n=get_pos(a,x); if(n<0||3<n) return(0); // 1:TRUE; 0:FALSE if(b[n+1]==y) return(1); else return(0); } // 隣接条件(順不定) int check_adj_2(char *a,char x,char *b,char y) { return(check_adj_1(a,x,b,y)||check_adj_1(b,y,a,x)); } #define PLACE "12345" // 固定 #define NATION "DEGNS" // 要素を昇順にソートしたもの #define HOUSE "BGRWY" // 以下同様 #define PET "BCDFH" #define DRINK "BCMTW" #define TABACO "BDMPR" int main(void) { char place[] =PLACE; // 場所(固定) char nation[]=NATION; // 国、国籍 char house[] =HOUSE; // 家 char pet[] =PET; // ペット char drink[] =DRINK; // 飲み物 char tabaco[]=TABACO; // タバコ(ポルトガル語) //clock_t st,dt; //st=clock(); /* タイマースタート */ strcpy(nation,NATION); do{ // nation loop if(!check_match(nation,'N',place, '1')) continue; // 条件09 strcpy(house,HOUSE); do{ // house loop if(!check_match(nation,'E',house, 'R')) continue; // 条件01 if(!check_adj_1(house, 'G',house, 'W')) continue; // 条件04 if(!check_adj_2(nation,'N',house, 'B')) continue; // 条件14 strcpy(pet,PET); do{ // pet loop if(!check_match(nation,'S',pet, 'D')) continue; // 条件02 strcpy(drink,DRINK); do{ // drink loop if(!check_match(nation,'D',drink, 'T')) continue; // 条件03 if(!check_match(house, 'G',drink, 'C')) continue; // 条件05 if(!check_match(place, '3',drink, 'M')) continue; // 条件08 strcpy(tabaco,TABACO); do{ // tabaco loop if(!check_match(tabaco,'P',pet, 'B')) continue; // 条件06 if(!check_match(house, 'Y',tabaco,'D')) continue; // 条件07 if(!check_adj_2(tabaco,'M',pet, 'C')) continue; // 条件10 if(!check_adj_2(pet, 'H',tabaco,'D')) continue; // 条件11 if(!check_match(tabaco,'B',drink, 'B')) continue; // 条件12 if(!check_match(nation,'G',tabaco,'R')) continue; // 条件13 if(!check_adj_2(tabaco,'M',drink, 'W')) continue; // 条件15 //チェックを潜り抜けたものだけを表示 printf("#: %s\n", place ); printf("N: %s\n", nation ); printf("H: %s\n", house ); printf("P: %s\n", pet ); printf("D: %s\n", drink ); printf("T: %s\n", tabaco ); printf("\n"); }while(next_permutation(tabaco,tabaco+strlen(tabaco))); }while(next_permutation(drink,drink+strlen(drink))); }while(next_permutation(pet,pet+strlen(pet))); }while(next_permutation(house,house+strlen(house))); }while(next_permutation(nation,nation+strlen(nation))); //dt=clock()-st; /* タイマーストップ */ //printf("Runtime : %ld.%03ld [sec]\n",dt/1000,dt%1000); return(0); }
●出力結果
#: 12345 N: NDEGS H: YBRGW P: CHBFD D: WTMCB T: DMPRB
※参考URL
http://q.hatena.ne.jp/1299204450
【アインシュタインのなぞなぞ】
それぞれ国籍の違う5人の人たちが、N{ｲｷﾞﾘｽ(E),ｽｳｪｰﾃﾞﾝ(S),ﾃﾞﾝﾏｰｸ(D),ﾉﾙｳｪｰ(N),ﾄﾞｲﾂ(G)}
それぞれ色の違う5軒の家に住んでいて、H{赤(R),緑(G),白(W),黄(Y),青(B)}
それぞれ種類の違う5匹のペットを飼い、P{魚(F),犬(D),鳥(B),猫(C),馬(H)}
そして、それぞれ違う5種類の飲み物と、D{紅茶(T),コーヒー(C),ミルク(M),ビール(B),水(W)}
それぞれ違う5種類のタバコを吸っています。T{ﾊﾟﾙﾏﾙ(P),ﾀﾞﾝﾋﾙ(D),ﾌﾞﾚﾝﾄﾞのﾀﾊﾞｺ(M),ﾌﾞﾙｰﾏｽﾀｰ(B),ﾌﾟﾘﾝｽ(R)}
さて、ペットに魚を飼っているのはだれでしょう？
01:イギリス人は赤い家に住んでいる。
02:スウェーデン人は犬を飼っている。
03:デンマーク人は紅茶を飲む。
04:緑の家と白い家は隣同士で、緑の家が左側。
05:緑の家の持ち主はコーヒーを飲む。
06:パルマル(ポールモール)を吸う人は、鳥を飼っている。
07:黄色い家の持ち主はダンヒルを吸う。
08:中央の家に住んでいる人はミルクを飲む。
09:ノルウェー人は一番目(左端)の家に住んでいる。
10:ブレンドのタバコを吸う人は、猫を飼っている人の隣に住んでいる。
11:馬を飼っている人は、ダンヒルを吸う人の隣に住んでいる。
12:ブルーマスターを吸う人はビールを飲む。
13:ドイツ人はプリンスを吸う。
14:ノルウェー人は青い家の隣にすんでいる。
15:ブレンドのタバコを吸う人の隣人は水を飲む。
http://q.hatena.ne.jp/1236314051
●BohYoh.com−C/C++ FAQ 順列の生成方法を教えてください。
そういえば、回答のプログラムをBorland C++用に書き換えてみたら、確かに動きました。書くのを忘れていました。(^_^;
次のincludeとusing namespaceをコメントにして、mainの引数をvoidにしてみました。
// #include "stdafx.h" // using namespace System; // int main(array<System::String ^> ^args) int main(void)
●出力結果
start #:12345 N:NDEGS H:YBRGW P:CHBFD D:WTMCB T:DMPRB retry:7527820回 答え：ドイツ人 208.963秒
