我一直在看一个电视选秀节目,有一个人挑战了整个节目国家(!)来解决问题。我觉得我可以写一个小脚本来解决但我仍然需要以某种方式认识到这个问题。所以问题是这样的这个:
+---+---+---+
| | | | -->
+---+---+---+
| | | | --> sum of
+---+---+---+ 3 rows
| | | | -->
+---+---+---+
| | | also sum of
v v v 2 diagonals
sum of
3 columns
将从1
到9
的数字写入上面的平方,得到所有平方的相同和标记线(例如3行、3列和2条对角线的总和)。
然后,他继续展示了这个问题的解决方案暂时扩展大正方形并将数字按顺序写为:
+---+
| 3 |
+---+---+---+
| 2 | | 6 |
+---+---+---+---+---+
| 1 | | 5 | | 9 |
+---+---+---+---+---+
| 4 | | 8 |
+---+---+---+
| 7 |
+---+
然后,他删除了多余的方块,并将其中的值放在分别为最远空正方形:
+---+---+---+
| 2 | 7 | 6 |
+---+---+---+
| 9 | 5 | 1 |
+---+---+---+
| 4 | 3 | 8 |
+---+---+---+
然后他得到了总数:
rows:
2 + 7 + 6 = 15
9 + 5 + 1 = 15
4 + 3 + 8 = 15
columns:
2 + 9 + 4 = 15
7 + 5 + 3 = 15
6 + 1 + 8 = 15
diagonals:
2 + 5 + 8 = 15
6 + 5 + 4 = 15
所以问题是用一个100乘100的正方形来解决这个问题
- 这是什么问题
- 它是NP完全的吗
- 我该如何解决这个问题
我可能记错了一些细节,但它还没有在youtube上因此,请随时建议对问题进行修改。
注意电视是很棒的
它被称为"魔术方块",维基百科给出了一些生成魔术方块的算法示例。
这种正方形被称为魔术正方形。在上阅读有关其结构的信息http://en.wikipedia.org/wiki/Magic_square#Method_for_constructing_a_magic_square_of_odd_order