这道逻辑题 用 Python 代码 如何实现?

[dwadewyp]

1.第一个答案是 A 的问题是哪一个?  ()
	A:1  B:2  C:3  D:4

2.唯一的连续两个具有相同答案的问题是 ()
	A:5,6  B:6,7  C:7,8  D:8,9

3.本问题答案和哪一个问题的答案相同 ()
	A:4  B:9  C:8  D:2

4.答案是 A 的问题的个数是 ()
	A:5  B:4  C:3  D:2 

5.本问题答案和哪一个问题的答案相同 ()
	A:1  B:2  C:3  D:4

6.答案选 A 的问题的个数和答案选什么的问题的个数相同 ()	
	A:无  B:C  C:C  D:D

7.按照字母顺序, 本题答案与下一题相差 () {A 与 B 间,或 B 与 A 间均相差 1}
	A:3  B:2  C:1  D:0

8.十道题中答案为元音的题数为 ()
	A:0  B:1  C:2  D:3

9.十道题中答案为辅音的题数为 ()
	A:是合数  B:是质数  C:<5  D:是平方数

10.本题答案为 ()
	A:A  B:B  C:C  D:D

[imn1]

有趣
先确定一下，你说的是解题吧？

跟什么语言无关，主要难题是问题的语义要准确翻译到逻辑式
穷举肯定是可以的，逻辑判断解法就要想了……

[XiaoxiaoPu]

可以类似解数独的方式去做，只不过各个格子（各个问题）的合法性判断不是统一的规则，而是 10 个不同的逻辑。
把这 10 个问题 “翻译” 成判定代码，可能是最繁琐的事情了。

[superrichman]

穷举，要优化也就调整一下题目验证顺序

[dwadewyp]

@imn1 确实和语言无关， 主要是在于思路

[XiaoxiaoPu]

第一个问题可以翻译成下面的函数，answers 是一个长度为 10 的 list

def q1(answers):
𑑛𑑛𑑛𑑛for i in range(4):
𑑛𑑛𑑛𑑛𑑛𑑛𑑛𑑛if answers[i] == 'A':
𑑛𑑛𑑛𑑛𑑛𑑛𑑛𑑛𑑛𑑛𑑛𑑛return answers[0] == 'ABCD'[i]
𑑛𑑛𑑛𑑛return False

[lithiumii]

笨办法：先按 10 道题的要求写测试，然后穷举，直到能通过测试

[dwadewyp]

我想知道 如果用穷举的话， 代码实现怎么实现呢？

[zhuangzhuang1988]

https://github.com/davecom/ClassicComputerScienceProblemsInPython/blob/master/Chapter3/csp.py

看这个就可以了
通用框架

[washbrain]

用 python 做的话应该就是 DFS 了，类似数独的思想去做就行，优化就是剪枝啥的
不过这种逻辑推理题其实最合适的是直接用 prolog 做推理，你把规则和事实告诉程序，让机器去帮你推理，当然背后本质也是搜索那一套

[hello2060]

@dwadewyp

answer = new list

Getanswer(pos:0, answer) {
if (pos 越界） return
// 检查 answer 里所有现有答案逻辑是否一致，不一致返回

for (int i = 0; i < 4; I++) {
answer.push(I)
getanswer(pos + 1, answer)
answer.poplast()
}
}

[dwadewyp]

@washbrain 能否细说下 如果 dfs 的话，这棵树如何构建？

[dwadewyp]

@zhuangzhuang1988 这个通用模版 学习到了， 感谢！

[dwadewyp]

@zhuangzhuang1988 我刚才把约束满足问题框架读了一遍，不过本人愚笨，写不出我提出的这个问题的约束条件，大佬能否点拨一下？

[dwadewyp]

@washbrain 回溯思路: 一旦在搜索中碰到障碍，就会回到碰到障碍之前的最后一次做出判断的已知点, 然后选择其他一条路径(可以理解为递归式的深度优先搜索); ps:其实我在推演的过程中, 就想到了这是典型的回溯递归 dfs ；只是编码起来 有点难 😄。。。

[imn1]

@dwadewyp #7
穷举的话
每题写一个逻辑表达式
把答案排列组合写出来，逐个去测试逻辑表达式，遇到 False 就 continue 测试下一个，直到 10 题 all True 就是正解
例如 10 个 A，第二题答案 A 就 False 了，('A'*10).find('AA')==5 --> False，当然第二题的逻辑式不是 find 这么简单，只是举例而已

[imn1]

@dwadewyp
呃，楼上应该是==4，第一题序号为 0，大致意思，看得明就行

[dwadewyp]

@imn1 穷举的大致思路明白了 谢谢， 我在想一下 每一个测试的逻辑表达式，该如何写

[Dvel]

@dwadewyp #17 每题写一个函数，每个函数写 4 个 if，每个 if 返回一个 bool，这样逻辑清晰，就是逻辑繁杂写着麻烦。

[wuyamao]

if Ans1 == 1 or (Ans1==2 and Ans2==1) or (Ans1==3 and Ans2!=1 and Ans3==1) or (Ans1==4 and Ans2!=1 and Ans3!=1 and Ans1==1):
if (Ans2 == 1 and Ans5==Ans6 and Ans1 != Ans2 and Ans2 != Ans3 and Ans3 != Ans4 and Ans4 != Ans5 and Ans6 != Ans7 and Ans7 != Ans8 and Ans8 != Ans9 and Ans9 != Ans10) or (Ans2 == 2 and Ans6==Ans7 and Ans1 != Ans2 and Ans2 != Ans3 and Ans3 != Ans4 and Ans4 != Ans5 and Ans5 != Ans6 and Ans7 != Ans8 and Ans8 != Ans9 and Ans9 != Ans10) or (Ans2 == 3 and Ans8==Ans7 and Ans1 != Ans2 and Ans2 != Ans3 and Ans3 != Ans4 and Ans4 != Ans5 and Ans6 != Ans7 and Ans5 != Ans6 and Ans8 != Ans9 and Ans9 != Ans10) or (Ans2 == 4 and Ans8==Ans9 and Ans1 != Ans2 and Ans2 != Ans3 and Ans3 != Ans4 and Ans4 != Ans5 and Ans6 != Ans7 and Ans5 != Ans6 and Ans9 != Ans10):
if (Ans3 == 1 and Ans4==1) or (Ans3 == 2 and Ans9==2) or (Ans3 == 3 and Ans8==3)or (Ans3 == 4 and Ans2==4):
countA = count(1,Ans1,Ans2,Ans3,Ans4,Ans5,Ans6,Ans7,Ans8,Ans9,Ans10)
if (Ans4 == 3 and countA == 3 ) or (Ans4 == 4 and countA ==2 ):
if (Ans5 == 1 and Ans1==1) or (Ans5 == 2 and Ans2==2) or (Ans5 == 3 and Ans3==3)or (Ans5 == 4 and Ans4==4):
countB = count(2,Ans1,Ans2,Ans3,Ans4,Ans5,Ans6,Ans7,Ans8,Ans9,Ans10)
countC = count(3,Ans1,Ans2,Ans3,Ans4,Ans5,Ans6,Ans7,Ans8,Ans9,Ans10)
countD = count(4,Ans1,Ans2,Ans3,Ans4,Ans5,Ans6,Ans7,Ans8,Ans9,Ans10)
if (Ans6 == 1 and countA != countB and countA != countC and countA != countD) or (Ans6 == 2 and countA == countC and countA != countD) or (Ans6 == 3 and countA == countC and countA != countD) or (Ans6 == 4 and countA == countD and countA != countC):
if (Ans7 == 1 and abs(Ans7-Ans8)==3) or (Ans7 == 2 and abs(Ans7-Ans8)==2) or (Ans7 == 3 and abs(Ans7-Ans8)==1)or (Ans7 == 4 and Ans8==4):
if (Ans8 == 3 and Ans4 == 4) or (Ans8 == 4 and Ans4 == 3):
countBCD = 10 - countA
if (Ans9==1 and (countBCD in [6,8])) or (Ans9==2 and (countBCD in [5,7])) or (Ans9==4 and countBCD ==9 ):


自己排版吧,可能有些有点漏

[Lightbright]

也就 100 多万种可能，暴力枚举一下（🐶

[washbrain]

@dwadewyp 约束本身是很简单的
FirstA = ans(1), OnlySameAnswerIndex = ans(2), sameAnswerWithThree = ans(3) ..... 以此类推
关键是约束传播与更新这一步不太好做
从实际操作角度来说，最好是对每一道题目选某个值的约束传播简单分成两种
1. 添加全局约束检查，比如说题目 6，选 A 的时候，就添加一条检查约束，每次变量更新都做一个检查，判断是否回溯
2. 更新其他变量的值域， 比如说选择题目 1 选 D，就可以更新 1，2，3，4 的值域; 题目 3，5，7 这种直接更新的也不用说了
当然还有复合形的，比如题目 2 既有全局约束，又能更新值域
然后递归回溯，保存每一次搜索的具体值域和全局检查约束
不算通用的 CSP 问题解法，只是针对这种 CSP 问题的一种特定解法

[polymer]

A, C, B, C, A, C, D, D, B, A

[chengfeng1992]

https://gist.github.com/chengfeng-1992/1b552c64d43cba7bee3ddd72fc1592bf

用 java 写的，穷举然后各种判断，除了没判断选项的唯一，其它都差不多了。

[JeffGe]

https://paste.ubuntu.com/p/b3NYTy4mcB/

就算穷举都挺快的，0.882 秒。优化的话可以剪枝，最简单的剪枝方法之一就是在判断题目正确性的函数里面返回数字 n 代替 True/False，代表前 n 道题的答案就已经不满足要求了，穷举的下一项选择递增第 n 个答案，后面全置 A 即可。比如第二道题，“AAAAAAAAAA”的前两项可以直接判断题目 2 不可能满足，下一项判断“ABAAAAAAAA”即可，跳过了 65535 项。

[washbrain]

https://gist.github.com/hzura/d8885dcde0798916f7d6387f457f4016

@dwadewyp
用 js 写了一个约束传播剪枝 csp 的简单 demo，可以复制到浏览器 console 跑一下，搜索到正确结果只用了 61 次搜索，全部搜索完只用了 114 次搜索
当然这个 CSP 用的约束传播和选择算法还很粗糙，比如：
1. 约束传播是自己手动写的如何传播，主要是本题的约束相对复杂一点，手工作业比较多，不过具体是怎么传播的都写了注释
2. 选择下一个搜索目标是基于值域大小来的，可以有更好的方案，稍微优化一下选择搜索的方式，搜索次数可以减少到 27 次（见注释）
3. 不像真正的约束传播算法，我们这里其实值域只会在手动选择的时候做一次约束传播，理论上可以一直迭代变动到值域稳定为止，也有更多优化空间