黑马程序员技术交流社区

标题: 4*4宫格问题 [打印本页]
作者: qq270628297    时间: 2016-8-1 21:08
标题: 4*4宫格问题
将1-16填入16宫格中.
        0  1  2  3
        4  5  6  7
        8  9  10 11
        12 13 15 16
* 要求:各行,各列,对角线之和都相等.
在控制台输出宫格表
作者: cat73    时间: 2016-8-1 21:16
遍历的复杂度 = 16! = 20922789888000
所以说肯定不能用遍历算法了。。。
作者: cat73    时间: 2016-8-1 22:31
遍历法，3 * 3 尚可，4 * 4 太费时了，根本就跑不完。。。
  1. 2 7 6
  2. 9 5 1
  3. 4 3 8

  5. 2 9 4
  6. 7 5 3
  7. 6 1 8

  9. 4 3 8
  10. 9 5 1
  11. 2 7 6

  13. 4 9 2
  14. 3 5 7
  15. 8 1 6

  17. 6 1 8
  18. 7 5 3
  19. 2 9 4

  21. 6 7 2
  22. 1 5 9
  23. 8 3 4

  25. 8 3 4
  26. 1 5 9
  27. 6 7 2

  29. 8 1 6
  30. 3 5 7
  31. 4 9 2

  33. [00:00:00] [DEBUG]: [8, 44.616963000000005ms]
复制代码
作者: cat73    时间: 2016-8-1 22:34
本帖最后由 cat73 于 2016-8-1 23:08 编辑

仔细考虑了下，其实有规律可循，每一个输出的行、列、对角线的总和其实都是一样的。
其规律为，按从小到大的顺序从左到右从上到下分布所有数字，然后求其对角线的总和。
这个数字就是后续有效输出中行、列、对角线的总和。
而且其实这些输出中数字的组合也是无需遍历即可预知的。
可以说解数 = N * 2 + 2（N 为长度与高度）
  1. 1 2 3
  2. 4 5 6
  3. 7 8 9

  5. 1 5 9
  6. 1 6 8
  7. 2 4 9
  8. 2 5 8
  9. 2 6 7
  10. 3 4 8
  11. 3 5 7
  12. 4 5 6
复制代码


作者: cat73    时间: 2016-8-1 23:44
似乎我发现的规律也不太对，算了，留个 TODO 以后再看吧。。。
作者: qq270628297    时间: 2016-9-3 09:00
cat73 发表于 2016-8-1 22:31
遍历法，3 * 3 尚可，4 * 4 太费时了，根本就跑不完。。。

求代码,3*3的代码怎么写出来的



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2