GreyRoar

纯属抛砖引玉. 在啄木鸟上贴我写的这个版本之前,我也给hoxide看过，希望他能够写出更好的程序。这个是用遍历做的，25号写的第一个版本。27号做出了一些优化，重写了mulitarg()、pailie5()，调整了一下遍历时条件判断的位置和顺序。代码的确写得很烂，不过功能确实实现了。关于代码书写与功能实现的关系，我在我的页里谈到了一下(GreyRoar)

Einstein.py

   1 # -*- coding: cp936 -*-
   2 data=[["黄房子","蓝房子","白房子","红房子","绿房子"],["挪威人","英国人","德国人","丹麦人","瑞典人"],["DUNHILL","PRINCE","混合烟", "PALL MALL","BLUE MASTER"],["咖啡","矿泉水","茶","牛奶","啤酒"],["鱼","猫","马", "鸟","狗"]]
   3 def mulitarg(x,y):
   4     return [[0 for col in range(x)] for row in range(y)]
   5 def pailie5():
   6     a=range(5)
   7     def newlist(i,oldlist):
   8         return [x for x in oldlist if x!=i]
   9     return [[x,y,z,i,m] for x,y,z,i,m in [(x,y,z,i,m) for x in a for y in newlist(x,a) for z in newlist(y,newlist(x,a)) for i in newlist(z,newlist(y,newlist(x,a))) for m in newlist(i,newlist(z,newlist(y,newlist(x,a))))]]
  10 answer=mulitarg(5,5)
  11 g=pailie5()
  12 for i in range(120):
  13     if data[0][g[i][1]]=="蓝房子":
  14         answer[0]=[data[0][g[i][0]],data[0][g[i][1]],data[0][g[i][2]],data[0][g[i][3]],data[0][g[i][4]]]
  15         if answer[0].index("白房子")-answer[0].index("绿房子")==1:
  16             for j in range(120):
  17                 if data[1][g[j][0]]=="挪威人":
  18                     answer[1]=[data[1][g[j][0]],data[1][g[j][1]],data[1][g[j][2]],data[1][g[j][3]],data[1][g[j][4]]]
  19                     if answer[0][answer[1].index("英国人")]=="红房子":
  20                         for k in range(120):
  21                             answer[2]=[data[2][g[k][0]],data[2][g[k][1]],data[2][g[k][2]],data[2][g[k][3]],data[2][g[k][4]]]
  22                             if answer[1][answer[2].index("PRINCE")]=="德国人":
  23                                 if answer[0][answer[2].index("DUNHILL")]=="黄房子":
  24                                     for l in range(120):
  25                                         if data[3][g[l][2]]=="牛奶":
  26                                             answer[3]=[data[3][g[l][0]],data[3][g[l][1]],data[3][g[l][2]],data[3][g[l][3]],data[3][g[l][4]]]
  27                                             if answer[2][answer[3].index("啤酒")]=="BLUE MASTER":
  28                                                 if answer[1][answer[3].index("茶")]=="丹麦人":
  29                                                     if answer[0][answer[3].index("咖啡")]=="绿房子":
  30                                                         import math
  31                                                         if int(math.fabs(answer[3].index("矿泉水")-answer[2].index("混合烟")))==1:
  32                                                             for m in range(120):
  33                                                                 answer[4]=[data[4][g[m][0]],data[4][g[m][1]],data[4][g[m][2]],data[4][g[m][3]],data[4][g[m][4]]]
  34                                                                 if answer[2][answer[4].index("猫")]!="混合烟":
  35                                                                     if int(math.fabs(answer[2].index("混合烟")-answer[4].index("猫")))==1:
  36                                                                         if int(math.fabs(answer[4].index("马")-answer[2].index("DUNHILL")))==1:
  37                                                                             if answer[1][answer[4].index("狗")]=="瑞典人":
  38                                                                                 if answer[2][answer[4].index("鸟")]=="PALL MALL":
  39                                                                                     for i in range(5):
  40                                                                                         print answer[i][answer[4].index("鱼")],
  41                                                                                     print

Hoxide

粗略讲一下,用了生成器在所有可能的状态空间里进行搜索, times变量用来计算搜索的节点个数, 大概2.9k个节点. 这里看更详细的解释EinsteinHoxide

EinsteinHoxide.py

   1 data=[['Yellow','Blue','White','Red','Green'],
   2       ['Norwegian','Brit','German','Dane','Swede'],
   3       ['Dunhill','Prince','Blends', 'PallMall','BlueMaster'],
   4       ['Coffee','Water','Tea','Milk','Beer'],
   5       ['Fish','Cat','Horse', 'Bird','Dog']
   6       ]
   7 
   8 def walk(gens):
   9     times=0
  10     ST=[None]*(5*5)
  11     FS=[]
  12     g=gens[0](ST)
  13     FS.append(g)
  14     while FS:
  15         times+=1
  16         #print ST
  17         #print len(FS)
  18         try:
  19             ST=FS[-1].next()
  20             if len(FS)<len(gens):
  21                 g=gens[len(FS)](ST)
  22                 FS.append(g)
  23         except StopIteration:
  24             del FS[-1]
  25     print times
  26 
  27 def geti(v):
  28     global data
  29     for i in range(5):
  30         if data[i].count(v)>0:
  31             return i
  32     print 'error', v
  33     raise EXP
  34 
  35 def setitmpl(t, assert_):
  36     j ,v= assert_
  37     i = geti(v)
  38     if (t[i*5+j] is not None) and t[i*5+j] != v:
  39         return
  40     else:
  41         tt=t+[]
  42         tt[i*5+j] = v
  43         yield tt
  44 
  45 def eqtmpl(t, assert_):
  46     (iv, jv) = assert_
  47     i, j = geti(iv), geti(jv)
  48     ic, jc = t.count(iv), t.count(jv)
  49     if ic==0 and jc==1:
  50         i, j, ic, jc, iv, jv = j, i, jc, ic, jv, iv
  51     if ic==1 and jc==0:
  52         k = t.index(iv) - i*5
  53         if t[j*5+k] is None:
  54             tt=t+[]
  55             tt[j*5+k] = jv
  56             yield tt
  57     elif ic==1 and jc==1:
  58         if t.index(iv)==t.index(jv):
  59             yield t
  60     elif ic==0 and jc==0:
  61         for k in range(5):
  62             if (t[i*5+k] is None) and (t[j*5+k] is None):
  63                 tt = t+[]
  64                 tt[i*5+k], tt[j*5+k] = iv, jv
  65                 yield tt
  66 
  67 def lefttmpl(t,  assert_):
  68     (iv, jv) = assert_
  69     i, j = geti(iv), geti(jv)
  70     ic, jc = t.count(iv), t.count(jv)
  71     if ic==0 and jc==1:
  72         k = t.index(jv) -1 - j*5
  73         if k>=0 and (t[i*5+k] is None):
  74             tt=t+[]
  75             tt[i*5+k] = iv
  76             yield tt
  77     elif ic==1 and jc==0:
  78         k = t.index(iv)+1 - i*5
  79         if k<5 and (t[j*5+k] is None):
  80             tt=t+[]
  81             tt[j*5+k] = jv
  82             yield tt
  83     elif ic==1 and jc==1:
  84         if t.index(iv)+1 ==t.index(jv):
  85             yield t
  86     elif ic==0 and jc==0:
  87         for k in range(4):
  88             if (t[i*5+k] is None) and (t[j*5+k] is None):
  89                 tt = t+[]
  90                 tt[i*5+k], tt[j*5+k+1] = iv, jv
  91                 yield tt
  92 
  93 def nexttmpl(t,  assert_):
  94     (iv, jv) = assert_
  95     i, j = geti(iv), geti(jv)
  96     ic, jc = t.count(iv), t.count(jv)
  97     if ic==0 and jc==1:
  98         i, j, ic, jc, iv, jv = j, i, jc, ic, jv, iv
  99     if ic==1 and jc==0:
 100         k = t.index(iv)+1 - i*5
 101         if k<5 and (t[j*5+k] is None):
 102             tt=t+[]
 103             tt[j*5+k] = jv
 104             yield tt
 105         k = t.index(iv)-1 - i*5
 106         if k>=0 and (t[j*5+k] is None):
 107             tt=t+[]
 108             tt[j*5+k] = jv
 109             yield tt
 110     elif ic==1 and jc==1:
 111         if (t.index(iv)-t.index(jv))**2 == 1:
 112             yield t
 113     elif ic==0 and jc==0:
 114         for k in range(4):
 115             if t[i*5+k]==None and t[j*5+k+1]==None:
 116                 tt = t+[]
 117                 tt[i*5+k], tt[j*5+k+1] = iv, jv
 118                 yield tt
 119             if t[i*5+k+1]==None and t[j*5+k]==None:
 120                 tt = t+[]
 121                 tt[i*5+k+1], tt[j*5+k] = iv, jv
 122                 yield tt
 123 
 124 def magicgen(t):
 125     for i in range(5):
 126         print t[i*5:(i+1)*5]
 127     print
 128     yield None
 129     
 130 gens = [ lambda t: setitmpl(t, (2, 'Milk')),
 131          lambda t: setitmpl(t, (0, 'Norwegian')),
 132          lambda t: eqtmpl(t, ('Red', 'Brit')),
 133          lambda t: eqtmpl(t, ('Swede', 'Dog')),
 134          lambda t: eqtmpl(t, ('Dane', 'Tea')),
 135          lambda t: eqtmpl(t, ('Green', 'Coffee')),
 136          lambda t: eqtmpl(t, ('PallMall', 'Bird')),
 137          lambda t: eqtmpl(t, ('Yellow', 'Dunhill')),
 138          lambda t: eqtmpl(t, ('BlueMaster', 'Beer')),
 139          lambda t: eqtmpl(t, ('German', 'Prince')),
 140          lambda t: lefttmpl(t, ('Green', 'White')),
 141          lambda t: nexttmpl(t, ('Blends', 'Cat')),
 142          lambda t: nexttmpl(t, ('Horse', 'Dunhill')),
 143          lambda t: nexttmpl(t, ('Norwegian', 'Blue')),
 144          lambda t: nexttmpl(t, ('Blends', 'Water')),
 145          lambda t: magicgen(t)
 146          ]
 147 
 148 from time import *
 149 start=clock()
 150 walk(gens)
 151 end=clock()
 152 print end-start

Nicholas Ding(Prolog)

装上SWI-Prolog;进去之后使用

?- [fish].
?- einstein(Houses, Fish_Owner).

就看到答案了。

fish.pl

next_to(X, Y, List) :- iright(X, Y, List).
next_to(X, Y, List) :- iright(Y, X, List).

iright(L, R, [L | [R | _]]).
iright(L, R, [_ | Rest]) :- iright(L, R, Rest).


einstein(Houses, Fish_Owner) :-
  =(Houses, [[house, norwegian, _, _, _, _], _, [house, _, _, _, milk, _], _, _]),
  member([house, brit, _, _, _, red], Houses),
  member([house, swede, dog, _, _, _], Houses),

  member([house, dane, _, _, tea, _], Houses),
  iright([house, _, _, _, _, green], [house, _, _, _, _, white], Houses),
  member([house, _, _, _, coffee, green], Houses),
  member([house, _, bird, pallmall, _, _], Houses),

  member([house, _, _, dunhill, _, yellow], Houses),
  next_to([house, _, _, dunhill, _, _], [house, _, horse, _, _, _], Houses),
  member([house, _, _, _, milk, _], Houses),
  next_to([house, _, _, marlboro, _, _], [house, _, cat, _, _, _], Houses),

  next_to([house, _, _, marlboro, _, _], [house, _, _, _, water, _], Houses),
  member([house, _, _, winfield, beer, _], Houses),
  member([house, german, _, rothmans, _, _], Houses),
  next_to([house, norwegian, _, _, _, _], [house, _, _, _, _, blue], Houses),

  member([house, Fish_Owner, fish, _, _, _], Houses).