## page was renamed from PyPorgramGames/Einstein
##language:zh
'''
[python-chinese] 谁养鱼的问题.
'''
<<TableOfContents>>
= GreyRoar =

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

== Einstein.py ==
{{{
#!python
# -*- coding: cp936 -*-
data=[["黄房子","蓝房子","白房子","红房子","绿房子"],["挪威人","英国人","德国人","丹麦人","瑞典人"],["DUNHILL","PRINCE","混合烟", "PALL MALL","BLUE MASTER"],["咖啡","矿泉水","茶","牛奶","啤酒"],["鱼","猫","马", "鸟","狗"]]
def mulitarg(x,y):
    return [[0 for col in range(x)] for row in range(y)]
def pailie5():
    a=range(5)
    def newlist(i,oldlist):
        return [x for x in oldlist if x!=i]
    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))))]]
answer=mulitarg(5,5)
g=pailie5()
for i in range(120):
    if data[0][g[i][1]]=="蓝房子":
        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]]]
        if answer[0].index("白房子")-answer[0].index("绿房子")==1:
            for j in range(120):
                if data[1][g[j][0]]=="挪威人":
                    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]]]
                    if answer[0][answer[1].index("英国人")]=="红房子":
                        for k in range(120):
                            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]]]
                            if answer[1][answer[2].index("PRINCE")]=="德国人":
                                if answer[0][answer[2].index("DUNHILL")]=="黄房子":
                                    for l in range(120):
                                        if data[3][g[l][2]]=="牛奶":
                                            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]]]
                                            if answer[2][answer[3].index("啤酒")]=="BLUE MASTER":
                                                if answer[1][answer[3].index("茶")]=="丹麦人":
                                                    if answer[0][answer[3].index("咖啡")]=="绿房子":
                                                        import math
                                                        if int(math.fabs(answer[3].index("矿泉水")-answer[2].index("混合烟")))==1:
                                                            for m in range(120):
                                                                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]]]
                                                                if answer[2][answer[4].index("猫")]!="混合烟":
                                                                    if int(math.fabs(answer[2].index("混合烟")-answer[4].index("猫")))==1:
                                                                        if int(math.fabs(answer[4].index("马")-answer[2].index("DUNHILL")))==1:
                                                                            if answer[1][answer[4].index("狗")]=="瑞典人":
                                                                                if answer[2][answer[4].index("鸟")]=="PALL MALL":
                                                                                    for i in range(5):
                                                                                        print answer[i][answer[4].index("鱼")],
                                                                                    print
}}}


= Hoxide =

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

== EinsteinHoxide.py ==
{{{
#!python
data=[['Yellow','Blue','White','Red','Green'],
      ['Norwegian','Brit','German','Dane','Swede'],
      ['Dunhill','Prince','Blends', 'PallMall','BlueMaster'],
      ['Coffee','Water','Tea','Milk','Beer'],
      ['Fish','Cat','Horse', 'Bird','Dog']
      ]

def walk(gens):
    times=0
    ST=[None]*(5*5)
    FS=[]
    g=gens[0](ST)
    FS.append(g)
    while FS:
        times+=1
        #print ST
        #print len(FS)
        try:
            ST=FS[-1].next()
            if len(FS)<len(gens):
                g=gens[len(FS)](ST)
                FS.append(g)
        except StopIteration:
            del FS[-1]
    print times

def geti(v):
    global data
    for i in range(5):
        if data[i].count(v)>0:
            return i
    print 'error', v
    raise EXP

def setitmpl(t, assert_):
    j ,v= assert_
    i = geti(v)
    if (t[i*5+j] is not None) and t[i*5+j] != v:
        return
    else:
        tt=t+[]
        tt[i*5+j] = v
        yield tt

def eqtmpl(t, assert_):
    (iv, jv) = assert_
    i, j = geti(iv), geti(jv)
    ic, jc = t.count(iv), t.count(jv)
    if ic==0 and jc==1:
        i, j, ic, jc, iv, jv = j, i, jc, ic, jv, iv
    if ic==1 and jc==0:
        k = t.index(iv) - i*5
        if t[j*5+k] is None:
            tt=t+[]
            tt[j*5+k] = jv
            yield tt
    elif ic==1 and jc==1:
        if t.index(iv)==t.index(jv):
            yield t
    elif ic==0 and jc==0:
        for k in range(5):
            if (t[i*5+k] is None) and (t[j*5+k] is None):
                tt = t+[]
                tt[i*5+k], tt[j*5+k] = iv, jv
                yield tt

def lefttmpl(t,  assert_):
    (iv, jv) = assert_
    i, j = geti(iv), geti(jv)
    ic, jc = t.count(iv), t.count(jv)
    if ic==0 and jc==1:
        k = t.index(jv) -1 - j*5
        if k>=0 and (t[i*5+k] is None):
            tt=t+[]
            tt[i*5+k] = iv
            yield tt
    elif ic==1 and jc==0:
        k = t.index(iv)+1 - i*5
        if k<5 and (t[j*5+k] is None):
            tt=t+[]
            tt[j*5+k] = jv
            yield tt
    elif ic==1 and jc==1:
        if t.index(iv)+1 ==t.index(jv):
            yield t
    elif ic==0 and jc==0:
        for k in range(4):
            if (t[i*5+k] is None) and (t[j*5+k] is None):
                tt = t+[]
                tt[i*5+k], tt[j*5+k+1] = iv, jv
                yield tt

def nexttmpl(t,  assert_):
    (iv, jv) = assert_
    i, j = geti(iv), geti(jv)
    ic, jc = t.count(iv), t.count(jv)
    if ic==0 and jc==1:
        i, j, ic, jc, iv, jv = j, i, jc, ic, jv, iv
    if ic==1 and jc==0:
        k = t.index(iv)+1 - i*5
        if k<5 and (t[j*5+k] is None):
            tt=t+[]
            tt[j*5+k] = jv
            yield tt
        k = t.index(iv)-1 - i*5
        if k>=0 and (t[j*5+k] is None):
            tt=t+[]
            tt[j*5+k] = jv
            yield tt
    elif ic==1 and jc==1:
        if (t.index(iv)-t.index(jv))**2 == 1:
            yield t
    elif ic==0 and jc==0:
        for k in range(4):
            if t[i*5+k]==None and t[j*5+k+1]==None:
                tt = t+[]
                tt[i*5+k], tt[j*5+k+1] = iv, jv
                yield tt
            if t[i*5+k+1]==None and t[j*5+k]==None:
                tt = t+[]
                tt[i*5+k+1], tt[j*5+k] = iv, jv
                yield tt

def magicgen(t):
    for i in range(5):
        print t[i*5:(i+1)*5]
    print
    yield None
    
gens = [ lambda t: setitmpl(t, (2, 'Milk')),
         lambda t: setitmpl(t, (0, 'Norwegian')),
         lambda t: eqtmpl(t, ('Red', 'Brit')),
         lambda t: eqtmpl(t, ('Swede', 'Dog')),
         lambda t: eqtmpl(t, ('Dane', 'Tea')),
         lambda t: eqtmpl(t, ('Green', 'Coffee')),
         lambda t: eqtmpl(t, ('PallMall', 'Bird')),
         lambda t: eqtmpl(t, ('Yellow', 'Dunhill')),
         lambda t: eqtmpl(t, ('BlueMaster', 'Beer')),
         lambda t: eqtmpl(t, ('German', 'Prince')),
         lambda t: lefttmpl(t, ('Green', 'White')),
         lambda t: nexttmpl(t, ('Blends', 'Cat')),
         lambda t: nexttmpl(t, ('Horse', 'Dunhill')),
         lambda t: nexttmpl(t, ('Norwegian', 'Blue')),
         lambda t: nexttmpl(t, ('Blends', 'Water')),
         lambda t: magicgen(t)
         ]

from time import *
start=clock()
walk(gens)
end=clock()
print end-start
}}}


= Nicholas Ding(Prolog) =
 * 将 fish.pl，放到你的~/目录下。
 * 装上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).
}}}