Python 新手，遇到一个数学题目，想用 Python 解决。求支招

[vvvv]

12 个人做游戏，总共 12 个不同的数，每人对应一个不同的数。游戏开始，每个人需要说出自己不是 12 个数中哪 3 个数。12 个人说完，能猜出每个人是什么数吗。
只想到了 python 遍历每个人可能的数，然后进行判断比较。但是遍历的数太多了，有什么好方法吗？求教

[sunfan314]

每个人维护一个自己可能的数的数组 所有人说完之后 每个人的数组中应该只包含 9 个数
对第一个人的数组进行遍历 假设第一个人的数 1,那么之后 11 个人的数组中都应该去除 1

这种遍历方式下 一般到最后几个人的数组大小就很小了 遍历的情况会少很多

[mathzhaoliang]

如果问题的要求是每个人随便说三个与自己不同的数字，那么答案是不能。

[mathzhaoliang]

@sunfan314 你认真分析过复杂度吗？

[zynlp]

不能，你把规模缩到 3 个人，每个人说一个数，有时会出现两个候选情况满足。

[zynlp]

可以试试，先建个有向图，判断有没有环

[Nimrod]

粗想了下不行，看看有没有大佬能说清楚

[Nimrod]

@zynlp 请问这个怎么理解成图的问题？

[sunfan314]

这个问题实质感觉是和数独问题是一样的，所以未必有解 但是 12 个人每个人只说三个数其实有解甚至有很多解的概率也是很大的

[cdwyd]

不能，极端考虑一下
1 号报数:3 4 5
2 号报数:3 4 5

其他人从不是 1 2 和自身的数里面随便选 3 个，这样至少是分不出来谁是 1 谁是 2

[upczww]

1 234
2 134
3 124
4 123
5 123
6 123
7 123
8 123
9 123
10 123
11 123
12 123
来猜猜看？

[ccpp132]

搜索就行了，有多种解就多种解呗。

要问这个问题最好的做法，如果 LZ 想研究的话，可以去看看 Knuth 的论文《 Dancing Links 》

[kx5d62Jn1J9MjoXP]

不能
1~6 号说自己不是 10, 11, 12
7~12 号说自己不是 1, 2, 3

这样至少有 6! * 6!种可能性

[inhzus]

提供一个思路 回溯法 递归实现
自己没写代码, 感觉应该行得通, 就是还是很复杂. 不过至少比 for 循环好看, 能解决楼主遍历数太多的痛点

[inhzus]

@inhzus #13 补充一下 类似的问题参考 八皇后问题 回溯法的思路差不多

[trueGate]

把问题看做 12*12 的数独棋盘，每行每列有且只有一个元素。用二维数组来做

[vvvv]

学习了，感谢楼上各位大佬~

[vuser]

@trueGate 思路不错