【プログラム クイズ】

 昔、質問した【アインシュタインのなぞなぞ】を解くプログラムを作って下さい。
 出力結果は、なぞなぞの答えだけでなく次のような表を作成するようにして下さい。
 しばらく開けませんので、ゆっくりどうぞ。

#: 12345
N: NDEGS
H: YBRGW
P: CHBFD
D: WTMCB
T: DMPRB

※記号の意味はコメントを参照してください。
※参考URL
http://q.hatena.ne.jp/1236314051

回答の条件
  • 1人1回まで
  • 13歳以上
  • 登録:2011/03/04 11:07:31
  • 終了:2011/03/09 07:57:47

ベストアンサー

id:grankoyama No.1

グラ娘。回答回数560ベストアンサー獲得回数1702011/03/06 22:09:54

ポイント100pt

とにかく長く、見づらく、遅くなりました。7527820パターンも検証してるようです。日曜プログラマの限界、、、

// nazonazo.cpp : メイン プロジェクト ファイルです。

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "time.h"
using namespace System;

#define NATION		0
#define HOUSE		1
#define PET		2
#define DRINK		3
#define TABACCO		4

char ans[5][5];
bool flg[15];
bool err_flg,mod;
int total;
//char data[5][5]={{'E','S','D','N','G'},{'R','G','W','Y','B'},{'F','D','B','C','H'},{'T','C','M','B','W'},{'P','D','M','B','R'}};
char data[5][5]={{'S','N','G','E','D'},{'G','W','R','B','Y'},{'F','D','B','C','H'},{'T','C','M','B','W'},{'P','D','M','B','R'}};//こっちのほうが正解にたどり着きにくい
bool checkandset(int a,int b,char c,int f){
	if (ans[a][b] == c){
		flg[f] = true;
		return true;
	}else if(ans[a][b] == 0){
		if (memchr(ans[a],c,5)){
			err_flg = true;
			return false;
		}
		ans[a][b] = c;
		flg[f] = true;
		mod = true;
		return true;
	}else{
		err_flg = true;
		return false;
	}
}
void set(char a, int b,int c,int f){
	if (flg[f])return;
	if (ans[b][c] == a){
		return;
	}else if(ans[b][c] != 0){
		err_flg = true;
	}else{
		ans[b][c] = a;
		flg[f] = true;
	}
}
void spe(char a, int b, char c, int d,int f){//bのaはdのc
	if (flg[f])return;
	for(int i=0;i<5;i++){
		if(ans[b][i] == a){
			checkandset(d,i,c,f);
			break;
		}
		if(ans[d][i] == c){
			checkandset(b,i,a,f);
			break;
		}
	}
}
void next(char a, int b, char c, int d,int f){//bのaは、dのcの隣に住んでいる。
	if (flg[f])return;
	for(int i=0;i<5;i++){
		if(ans[b][i] == a){
			if(i==0){
				checkandset(d,i+1,c,f);
				break;
			}else if(i<4){
				if(ans[d][i+1] != 0){
					checkandset(d,i-1,c,f);
					break;
				}else if(ans[d][i-1] != 0){
					checkandset(d,i+1,c,f);
					break;
				}
			}else{//if(i==4)
				checkandset(d,i-1,c,f);
				break;
			}
		}else if(ans[d][i] == c){
			if(i==0){
				checkandset(b,i+1,a,f);
				break;
			}else if(i<4){
				if(ans[b][i+1] != 0){
					checkandset(b,i-1,a,f);
					break;
				}else if(ans[b][i-1] != 0){
					checkandset(b,i+1,a,f);
					break;
				}
			}else{//if(i==4)
				checkandset(b,i-1,a,f);
				break;
			}
		}
	}
}
void pad(){//ラス1データを埋める
	int i,j,cnt,f,pr;
	for(i=0;i<5;i++){
		cnt = f = 0;
		for(j=0;j<5;j++){
			if(ans[i][j]!=0){
				cnt++;
				for(int k=0;k<5;k++){
					if(ans[i][j]==data[i][k])f+=(1<<k);
				}
			}else pr=j;		
		}
		if(cnt == 4){
			switch(f){
			case 2+4+8+16:ans[i][pr]= data[i][0];break;
			case 1+4+8+16:ans[i][pr]= data[i][1];break;
			case 1+2+8+16:ans[i][pr]= data[i][2];break;
			case 1+2+4+16:ans[i][pr]= data[i][3];break;
			case 1+2+4+8:ans[i][pr]= data[i][4];break;}
		}
	}
}
void hintcheck(){
	spe('E',NATION,'R',HOUSE,0);//イギリス人は赤い家に住んでいる。
	spe('S',NATION,'D',PET,1);//スウェーデン人は犬を飼っている。
	spe('D',NATION,'T',DRINK,2);//デンマーク人は紅茶を飲む。
	if (!flg[3]){//緑の家と白い家は隣同士で、緑の家が左側。
		for(int i=0;i<5;i++){
			if(ans[HOUSE][i] == 'G'){
				if(i == 4) err_flg = true;
				else checkandset(HOUSE,i+1,'W',3);
				break;
			}else if(ans[HOUSE][i] == 'W'){
				if(i == 0) err_flg = true;
				else checkandset(HOUSE,i-1,'G',3);	
				break;
			}
		}
	}
	spe('G',HOUSE,'C',DRINK,4);//緑の家の持ち主はコーヒーを飲む。
	spe('P',TABACCO,'B',PET,5);//パルマル(ポールモール)を吸う人は、鳥を飼っている。
	spe('Y',HOUSE,'D',TABACCO,6);//黄色い家の持ち主はダンヒルを吸う。
	set('M',DRINK,2,7);//中央の家に住んでいる人はミルクを飲む。
	set('N',NATION,0,8);//ノルウェー人は一番目(左端)の家に住んでいる。
	next('M',TABACCO,'C',PET,9);//ブレンドのタバコを吸う人は、猫を飼っている人の隣に住んでいる。
	next('H',PET,'D',TABACCO,10);//馬を飼っている人は、ダンヒルを吸う人の隣に住んでいる。
	spe('B',TABACCO,'B',DRINK,11);//ブルーマスターを吸う人はビールを飲む。
	spe('G',NATION,'R',TABACCO,12);//ドイツ人はプリンスを吸う。
	next('N',NATION,'B',HOUSE,13);//ノルウェー人は青い家の隣にすんでいる。
	next('M',TABACCO,'W',DRINK,14);//ブレンドのタバコを吸う人の隣人は水を飲む。
}
bool checkalldata(){
	if(memchr(ans,0,25))return false;
	memset(flg,0,sizeof(flg));
	hintcheck();
	if(err_flg)return false;	
	return true;
}
bool retry(){
	total++;
	int i,j,k;
	bool back[5][5];
	memcpy(back,ans,sizeof(back));//退避
	for(i=0;i<5;i++){//ひとつだけ情報を追加して仮定で進める作戦
		for(j=0;j<5;j++){
			if(ans[i][j]!=0) continue;
			for(k=0;k<5;k++){
				memcpy(ans,back,sizeof(back));//復帰
				if (memchr(ans[i],data[i][k],5))continue;
				memset(flg,0,sizeof(flg));
				err_flg = false;
				ans[i][j] = data[i][k];//仮のデータ代入
				for(;;){
					mod = false;
					hintcheck();
					pad();
					if(!mod)break;
					if(err_flg)break;
				}
				if(!err_flg){//ここは見込みのあるパス 整合性チェック->情報をひとつ追加する
					if (checkalldata())return true;
					if (retry())return true;
				}
			}
		}
	}
	return false;
}
int main(array<System::String ^> ^args)
{
	clock_t in,out;
	in = clock();	//かいし
	printf("start\n");

	bool b_flg[15];
	memset(ans,0,25);
	total = 0;
	for(int i=0;i<15;i++) flg[i] = false;
	for(;;){
		mod = false;
		hintcheck();
		pad();
		if(!mod)break;
	}
	memcpy(b_flg,flg,sizeof(b_flg));//退避
	for(int i=0;i<15;i++)flg[i]=false;
	if(!checkalldata()){
		memcpy(flg,b_flg,sizeof(b_flg));//復帰
		if(!retry())exit(1);
	}
	printf("#:12345\nN:%c%c%c%c%c\nH:%c%c%c%c%c\nP:%c%c%c%c%c\nD:%c%c%c%c%c\nT:%c%c%c%c%c\nretry:%d回\n答え:",
		ans[NATION][0],ans[NATION][1],ans[NATION][2],ans[NATION][3],ans[NATION][4],
		ans[HOUSE][0],ans[HOUSE][1],ans[HOUSE][2],ans[HOUSE][3],ans[HOUSE][4],
		ans[PET][0],ans[PET][1],ans[PET][2],ans[PET][3],ans[PET][4],
		ans[DRINK][0],ans[DRINK][1],ans[DRINK][2],ans[DRINK][3],ans[DRINK][4],
		ans[TABACCO][0],ans[TABACCO][1],ans[TABACCO][2],ans[TABACCO][3],ans[TABACCO][4],total);

	for(int j=0;j<5;j++){
		if(ans[PET][j]=='F'){
			switch(ans[NATION][j]){
			case 'E':printf("イギリス人\n");break;
			case 'S':printf("スウェーデン人\n");break;
			case 'D':printf("デンマーク人\n");break;
			case 'N':printf("ノルウェー人\n");break;
			case 'G':printf("ドイツ人\n");break;
			}
			break;
		}
	}
	out = clock();//おしまい
	printf("%.3f秒\n",(double)(out-in)/CLOCKS_PER_SEC);
	int dmy = getchar();
    return 0;
}

start

#:12345

N:NDEGS

H:YBRGW

P:CHBFD

D:WTMCB

T:DMPRB

retry:7527820回

答え:ドイツ人

567.891秒

その後、ちょっとした消去法を使って、有り得ないとわかっているパターンでの再帰を止めたら、数msで答えが出るようになりましたが(ろくにチェックしてないので)偶然かも知れません。試行回数6回くらいになったのです。

id:rsc96074

回答ありがとうございます。ブログもやっていたんですね。拝見させていただきました。

唯一の回答者のようです。

2011/03/09 07:44:52
  • id:rsc96074
    【アインシュタインのなぞなぞ】
     それぞれ国籍の違う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:ブレンドのタバコを吸う人の隣人は水を飲む。

  • id:taknt
    プログラムって 上記の日本語を入力して 解くということになるんですか?
  • id:SALINGER
    プログラムで言語処理を書けるのでしたそれでもいいんじゃないですか?
    解くということよりも、どのようにパズルをプログラムにおとすかだと思うので、
    人それぞれにやり方があっていいはず。
    普通の人はたぶん、「イギリス人は赤い人」ならE=Rというようにヒントを記号化していくと思うけどね。
  • id:rsc96074
    他にも方法があるかも知れませんが、出力結果の表を全パターン作成して条件を満たすかチェックしました。(^_^;
  • id:taknt
    これは マトリックスを用いた推理パズルになるので
    http://www17.plala.or.jp/yaggdrasil/guess/sui2.html

    このマトリックスに ○をつけるのを 誰がやるのか?
    というのが ポイントになると思います。

    あとは そのマトリックスを どう解くかですが。

    文章を読んで それを間違いなく判断するのは 難しいことです。
    このなぞなぞの ポイントの一つは そこですから。
  • id:SALINGER
    それはもっとつきつめるとね質問者様はご存知だと思うけどついこの前に私も同じことを言ってました。
    数学の問題やパズルを解く場合にどこからがプログラムで処理すれば、プログラムで解いたということになるか。
    明らかに自明であることだけを使いプログラムを作るべきであるのだけど、その自明という部分が難しいという話だけどね。
  • id:rsc96074
    【ヒント】1
     C++の<algorithm>のnext_permutation()を使いました。(^_^;
  • id:rsc96074
    【ヒント】2
     たくさん条件がありますが、分類すれば、次のパターン。
    ①マッチング条件(条件01,08など)
    ②順序付隣接条件(条件04)
    ③順不定隣接条件(条件10など)
  • id:rsc96074
     やっと回答が付いてくれました。o(^-^)o
    【ヒント】3
    ●BohYoh.com-C/C++ FAQ 順列の生成方法を教えてください。
    http://www.bohyoh.com/CandCPP/FAQ/FAQ00108.html
     それから、消去法でスキップするとき、出来るだけ外側のループにもってきた方が速くなるようです。
  • id:rsc96074
     回答ありがとうございました。残念ながら、こちらはBorland C++なので、コンパイルできませんでした。(^_^;
    おそらく、Visual C++では動くのでしょう。ブログも拝見させていただきました。ブログでも色々と検討されていらっしゃるようです。
    唯一の回答者のようです。いるかをさしあげます。忘れて自動終了しないうちに終了することにしました。
     プログラム例はこちらです。コンパイルは、「Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland」を使いました。ほとんどCですが、 next_permutation()を使うため拡張子をcppにしました。(^_^;
    http://d.hatena.ne.jp/rsc96074/20110307/1299490462
  • id:grankoyama
    グラ娘。 2011/03/09 12:26:17
    いるかありがとうございます。
    そして、ごめんなさい。回答のソースにはバグがあり、”たまたま”答えが出ていたようです、、、orz
    (ネタにしても酷かったです)

    Borland C++ではビルドできませんか。
    stdafx.hやらネームスペースの宣言とかぐらいしかVC依存してないはずなのですが、、、やっぱりよくわかってません。

    楽しい質問をありがとうございました。
    かれこれ、いまだに検討を続けていて、(順列とか再帰とか使わず)全パターン試さずに単純にヒントによる穴埋めと消去法で回答に
    たどり着けそうな感じがして来ているところでした。(それのログを見ながら、ほんとに想定どおり動いているのか検証中)
    考えれば考えるほどコードがどんどん長くなっていったので、(十分長いですが)上の時点のソースで回答したのでした。
    落ち着いたら、rsc96074さんのを見習って見やすくコンパクトに挑戦しようと思います。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません