Qi Dong-feng 2023-03-28 09:42 采纳率: 0%
浏览 78
已结题

找出5阶幻方的所有解的个数:275305224

任何一个幻方,整体旋转90度、180度、270度仍然是幻方,这4个幻方再镜射一下,又是4个幻方;所以幻方的数量一定是8的倍数!
5阶幻方去掉8倍的同构幻方,答案是:275305224种。
多年前这个结果已经在小型机上验证了。
本人用python(pypy编译)花了70个小时得到了这个答案。
现在请教:
1、能不能还用python,减少机时,包括用cython怎么处理
2、用C语言是不是速度会快,请问程序怎么写(远不如python方便)

  • 写回答

8条回答 默认 最新

  • 请叫我问哥 Python领域新星创作者 2023-03-28 11:37
    关注
    获得7.50元问题酬金

    可以通过剪枝,一边填数字,一边判断是否符合条件,比如已填数字之和如果已经大于65的话,肯定方案就不对了,而且比当前数字大的数字都可以剪枝,返回上一个数字继续填。
    这些都比较简单,相信你在代码里已经用到了。
    另外还可以通过数学的方法进行剪枝。比如如果不考虑重复的情况下,总共要试 25! 种组合,但是可以倒过来想,如果一种组合是解的话,它必然满足下面这种条件:

    1. 5条横、5条竖、2条对角线的数字之和都等于65,总和等于65*12=780
    2. 在上面780的总和中:
      1)最中间的一个数字计算了4次
      2)对角线其余8个数字计算了3次
      3)剩下的16个数字计算了2次
      所以可以先找出满足这个条件的所有方案,总共有 339405 种,用时30秒,代码如下:
      from itertools import combinations
      res = 0
      nums = set(range(1,26))
      for i in range(1, 26):
       for j in combinations(nums-{i}, 8):
           y = sum(j)
           z = sum(nums-{i}-set(j))
           if 4*i+3*y+2*z == 780:
               res += 1
      print(res)
      
      然后在这些保证有解的组合中进行穷举,最多试错 8!*16!*339405 次,比 25! 优化了 1e7 级别。
    评论

报告相同问题?

问题事件

  • 系统已结题 4月5日
  • 创建了问题 3月28日

悬赏问题

  • ¥15 u盘问题:盘符不显示 无媒体
  • ¥50 R语言读取nc按月均值转为tif
  • ¥30 智能车串级pid调参
  • ¥15 visual studio code翻译老是错误
  • ¥20 卫星测高数据的高程转换
  • ¥15 爬取招聘网站数据信息
  • ¥15 安装完tensorflow,import tensorflow as tf后报错,如何解决?
  • ¥15 ultralytics库导出onnx模型,模型失去预测能力
  • ¥15 linux下点对点协议连接2个USB串口的硬件流量控制问题
  • ¥15 SQL数据自动生成问题