最近迷上python解题了,看到下面一套刑侦科推理试题,试着用python暴力解了出来。

看题

python暴力解题

直接上代码,很好理解。

from itertools import product
from time import time

dic_1 = {'a':1, 'b':2, 'c':3, 'd':4}
dic_2 = {'a':'c', 'b':'d', 'c':'a', 'd':'b'}
dic_3 = {'a':[3,6,2,4], 'b':[6,3,2,4], 'c':[2,3,6,4], 'd':[4,3,6,2]}
dic_4 = {'a':[1,5], 'b':[2,7], 'c':[1,9], 'd':[6,10]}
dic_5 = {'a':8, 'b':4, 'c':9, 'd':7}
dic_6 = {'a':[2,4], 'b':[1,6], 'c':[3,10], 'd':[5,9]}
dic_7 = {'a':'c', 'b':'b', 'c':'a', 'd':'d'}
dic_8 = {'a':7, 'b':5, 'c':2, 'd':10}
dic_9 = {'a':6, 'b':10, 'c':2, 'd':9}
dic_10 = {'a':3, 'b':2, 'c':4, 'd':1}
## 穷举所有可能结果
def all_num():
    for num in list(product('abcd', repeat=10)):
        x = ''
        for i in range(len(num)):
            x += num[i]
        yield x

def rule(x):
    dic = {}
    for i in x: 
        if i in dic.keys():
            dic[i] += 1
        else:
            dic[i] = 1
    return dic

def rule2(x):
    if x[4] == dic_2[x[1]]:
        return x

def rule3(x):
    lst = dic_3[x[2]]
    a = x[lst[0]-1]
    if a != x[lst[1]-1] and a != x[lst[2]-1] and a != x[lst[3]-1]:
        return x 

def rule4(x):
    lst = dic_4[x[3]]
    if x[lst[0]-1] == x[lst[1]-1]:
        return x

def rule5(x):
    if x[4] == x[dic_5[x[4]]-1]:
        return x 

def rule6(x):
    lst = dic_6[x[5]]
    if x[7] == x[lst[0]-1] and x[7] == x[lst[1]-1]:
        return x

def rule7(x):
    dic = rule(x)
    if dic_7[x[6]] == sorted(dic.items(), key=lambda x:x[1])[0][0]:
        return x

def rule8(x):
    if abs(dic_1[x[0]] - dic_1[x[dic_8[x[7]]-1]]) >= 2:
        return x 

def rule9(x):
    if (x[0] == x[5]) != (x[4] == x[dic_9[x[8]]-1]):
        return x 

def rule10(x):
    dic = rule(x)
    a = sorted(dic.items(), key=lambda x:x[1])
    if (a[-1][1] - a[0][1]) == dic_10[x[9]]:
        return x


def main():    
    for n in list(all_num()):
        n = rule2(n)
        if n:
            n = rule3(n)
            if n:
                n = rule4(n)
                if n:
                    n = rule5(n)
                    if n:
                        n = rule6(n)
                        if n:
                            n = rule7(n)
                            if n:
                                n = rule8(n)
                                if n:
                                    n = rule9(n)
                                    if n:
                                        n = rule10(n)
                                        if n:
                                            return n


start_time = time()
num = main()
elapsed_time = time() - start_time
print('正确答案为:' + num)
print('耗时:{0}'.format(elapsed_time))

正确答案为:bcacacdaba 耗时:2.6687490940093994

constraint-约束解决库

网上看到大牛用constraint库的解决方案,运算效率比我这个提高了N倍,学习了一下。 这里有constraint的文档,可以看看https://labix.org/python-constraint,安装方法:pip install python-constraint 代码如下:

from time import time
from constraint import *

problem = Problem()

vars = ["a1","a2","a3","a4","a5","a6","a7","a8","a9","a10"]
problem.addVariables(vars, [1, 2, 3, 4])

def a2_func(a2, a5):
    return (a2 == 1 and a5 == 3) or (a2 == 2 and a5 == 4) or (a2 == 3 and a5 == 1) or (a2 == 4 and a5 == 2)
problem.addConstraint(a2_func, ["a2", "a5"])

def a3_func(a3, a1, a2, a4, a6):
    return (a3 ==1 and a6 == a2 == a4 != a3) or (a3 == 2 and a3 == a2 == a4 != a6) or (a3 == 3 and a3 == a6 == a4 != a2) or (a3 == 4 and a3 == a6 == a2 != a4)
problem.addConstraint(a3_func, ["a3", "a1", "a2", "a4", "a6"])

def a4_func(a4, a1, a2, a5, a6, a7, a9, a10):
    return (a4 == 1 and a1 == a5) or (a4 == 2 and a2 == a7) or (a4 == 3 and a1 == a9) or (a4 == 4 and a6 == a10)
problem.addConstraint(a4_func, ["a4", "a1", "a2", "a5", "a6", "a7", "a9", "a10"])

def a5_func(a4, a5, a7, a8, a9):
    return (a5 == a8 == 1) or (a5 == a4 == 2) or (a5 == a9 == 3) or (a5 == a7 == 4)
problem.addConstraint(a5_func, ["a4", "a5", "a7", "a8", "a9"])

def a6_func(a6, a1, a2, a3, a4, a5, a8, a9, a10):
    return (a6 == 1 and a2 == a4 == a8) or (a6 == 2 and a1 == a6 == a8) or (a6 == 3 and a3 == a10 == a8) or (a6 == 4 and a5 == a9 == a8)
problem.addConstraint(a6_func, ["a6", "a1", "a2", "a3", "a4", "a5", "a8", "a9", "a10"])

def a7_func(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10):
    all_answers = [a1, a2, a3, a4, a5, a6, a7, a8, a9, a10]
    counter = [0, 0, 0, 0]
    for a in all_answers:
        counter[a - 1] += 1
    imin = counter.index(min(counter)) + 1
    return ((a7 == 1 and imin == 3) or (a7 == 2 and imin == 2) or (a7 == 3 and imin == 1) or (a7 == 4 and imin == 4))
problem.addConstraint(a7_func, vars)

def a8_func(a8, a1, a2, a5, a7, a10):
    adj = lambda x: abs(a1 - x) != 1
    return (a8 == 1 and adj(a7)) or (a8 == 2 and adj(a5)) or (a8 == 3 and adj(a2)) or (a8 == 4 and adj(a10))
problem.addConstraint(a8_func, ["a8","a1","a2","a5","a7","a10"])

def a9_func(a1, a2, a5, a6, a9, a10):
    cond1 = a1 == a6
    cond = lambda x: cond1 != (x == a5)
    return (a9 == 1 and cond(a6)) or (a9 == 2 and cond(a10)) or (a9 == 3 and cond(a2)) or (a9 == 4 and cond(a9))
problem.addConstraint(a9_func, ["a1","a2","a5","a6","a9","a10"])

def a10_func(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10):
    all_answers = [a1, a2, a3, a4, a5, a6, a7, a8, a9, a10]
    counter = [0, 0, 0, 0]
    for a in all_answers:
        counter[a - 1] += 1
    delta = abs(max(counter) - min(counter))
    return (a10 == 1 and delta == 3) or (a10 == 2 and delta == 2) or (a10 == 3 and delta == 4) or (a10 == 4 and delta == 1)
problem.addConstraint(a10_func, vars)

start_time = time()
solutions = problem.getSolutions()
elapsed_time = time() - start_time
print('耗时:{0}'.format(elapsed_time))  
chars = ['A', 'B', 'C', 'D']
for i in range(1, 11):
    key = 'a' + str(i)
    num = chars[solutions[0][key] - 1]
    #print('第{0}题的答案为:{1}'.format(i, num))
    print(num, end='')

耗时:0.07611608505249023 BCACACDABA

PHP解决方法

另外附上大牛PHP的解决方法,我不会PHP,直接上图。