人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

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

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


●質問者: rsc
●カテゴリ:コンピュータ ネタ・ジョーク
✍キーワード:URL なぞなぞ ゆっくり アインシュタイン クイズ
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● グラ娘。
●100ポイント ベストアンサー

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

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

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

#define NATION0
#define HOUSE1
#define PET2
#define DRINK3
#define TABACCO4

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回くらいになったのです。

◎質問者からの返答

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

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

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ