谢涛的幻方研究问题
缺陷幻方的填充问题高治源
我们的幻方研究如果能够为祖国的国防或经济建设发挥作用，那是我们十分高兴的事。谢涛先生遇到了一个幻方难题，我们称缺陷幻方的填充问题。请大家参与讨论。
谢涛同志：
你的研究项目非常深奥，它属于"反幻方"和"开天窗幻方问题"，我国有部分人研究。
反幻方问题是将所给数字，填入各线，使所含数字都不等。从基本原理上看，你的问题是可以解决的，它就是将你给定的数字填入规定的格中，使它的各行各列两条对角线等于给定的值。应该说正是另一种组合问题。
我们还可以将此问题转化为线性方程组，用矩阵来解决。在这个意义上，你的问题与构造一个新的幻方是没有区别的，因为它们都是用矩阵求解方程组的问题。
在线性规划中，有一些理论，我们似乎可以应用，或者推出一条解决此问题的算法，对于现在数学发展的情况来看，应该不成问题。
但您感兴趣的是它的应用，我们希望在研究这个问题时，有一个方向，使我们不至于在沙漠中迷失方向。
郭先强的矩阵程序，应该对这个问题有一个更明确的结论，请您与直接联系。
高治源
二○○二年七月九日
姓名: 高治源 於 2002.07.13.09:29:09
邮箱: gy1397@sina.com
主页: http://
留言内容: 谢涛同志：
你的研究项目非常深奥，它属于"反幻方"和"开天窗幻方问题"，我国有部分人研究。
反幻方问题是将所给数字，填入各线，使所含数字都不等。从基本原理上看，你的问题是可以解决的，它就是将你给定的数字填入规定的格中，使它的各行各列两条对角线等于给定的值。应该说正是另一种组合问题。
我们还可以将此问题转化为线性方程组，用矩阵来解决。在这个意义上，你的问题与构造一个新的幻方是没有区别的，因为它们都是用矩阵求解方程组的问题。
在线性规划中，有一些理论，我们似乎可以应用，或者推出一条解决此问题的算法，对于现在数学发展的情况来看，应该不成问题。
但您感兴趣的是它的应用，我们希望在研究这个问题时，有一个方向，使我们不至于在沙漠中迷失方向。
郭先强的矩阵程序，应该对这个问题有一个更明确的结论，请您与直接联系。
高治源
二○○二年七月九日
| 姓名: 谢涛 於 2002.05.13.09:25:13 邮箱: taoxie@nudt.edu.cn 主页: http:// 留言内容: 李文：你好！ 还有一个问题，对于计算机算法来说，我认为低阶缺陷幻方的填充问题是，越是低阶越难，越是高阶反而越容易，这与要求高于一般幻方的更完美的幻方构造性质一样。但对于象您这种幻方构造专家来说，如果仅用心智去填充，也许低阶缺陷幻方的填充比高阶更容易，因为人类的“心智”是有极限和维度的。您认为如何？ |
姓名: 谢涛 於 2002.04.19.03:56:08 邮箱: taoxie@nudt.edu.cn 主页: http:// 留言内容: 哲言：在排列组合问题上，机器永远比人聪明！ 构造！奇异的构造！！天才的构造！！！幻方的构造耗尽了多少善良人们的心智！猛回头，白了少年头！ 本人认为，现在是将幻方的迷恋者从苦海中解脱出来的时候了！ |
姓名: 李文 於 2002.05.15.04:09:48
邮箱: liwen39@hotmail.com
留言内容: 谢涛：你好！
首先，一般幻方就是指幻方，完美幻方只是它的子集，完美幻方的解法也是一般幻方解法的一个子集。我个人认为一般幻方的解法多余完美幻方的解法，完美幻方比一般幻方的要求高，因此一般幻方更容易解。要研究一般幻方，就要包括研究完美幻方，因此研究一般幻方的工作量远大于研究完美幻方的工作量。
其次，对于缺陷幻方的填充问题，它至少存在一个原幻方，不存在有无解的悬念,它是有解的问题。但是原幻方可能是任何一种类型的幻方，抽去的数也是随机的，因此要保证最坏的情况下找到一个解（最坏的情况只有一个解，找完所有的情况才找到解它），最坏的情况计算机要运算完全部的变化，当然阶数越高运算量越大，耗时越多，阶数越少，变化越少，耗时越少。
在寻找一些特殊幻方时，有无解本身是一个悬念，没有人找到一个解，也没有人能证明它无解，如五阶幻立方。这里有两个原因，一是不可能有解，当然就找不到解，只是要证明它无解难度比解一般幻方要大得多。这样的例子很多，如高老师设1997元奖金找十六阶三次幻方，我认为十六阶三次幻方可能没有解，只是无法证明。二是由于阶数越低，组合变化越少，对于特殊幻方成功的机会也少，解就越少，反之越多，例如七次特优完美幻方，十三阶以下可能不存在，你要去找当然十年，二十年都找不到，十三阶才有一解（实际上有很多，但本质上是同一结构），你从十三阶开始找就有可能找到，但大多数人不知道从十三阶找，一般人都习惯在低阶去寻找，以为阶数越低越好找，遇到这种没有解的时候就害死人。
我说你的问题是最难的，和一般研究幻方不同，一般研究幻方只是找幻方的某一些特殊的子集，并不找幻方的全集，（要找全集，七阶、八阶可能还无人能办到）你的缺陷幻方的填充问题要考虑最坏的情况，就要运算完全部的变化，工作量之巨大你是知道的。在阶数小的情况下，缺陷幻方的填充问题是有把握的，阶数大了，就只能让计算机去碰运气了，运气不好，一道题让计算机算上一万年也可能没有结果。
不知我讲清楚没有。
高老师：
谢谢您能关注并投入精力研究此问题，相信缺陷幻方的填充问题在几位专家的努力下能有所进展。
再次表示衷心的感谢！
谢涛
谢涛先生：
你的信，我已收到，我将你提出的问题作了一些宣传。最后，我确定，能够参与这次研究讨论的人员有四位：陕西高治源，四川李文，江苏郭先强，西藏潘凤雏。我还将大家研究讨论的信件开一个专栏宣传。您可以着重与这四位朋友加强联系。
李文的观点想法，你已得到。郭先强认为具有算法的可行性。潘凤雏用矩阵、向量、映射研究幻方，正在撰写幻方书籍，理论水平较高。我正在考察各种资料，对这个问题，作全面的思考。
高治源
二○○二年五月八日
姓名: 谢涛 於 2002.05.13.09:25:13
邮箱: taoxie@nudt.edu.cn
主页: http://
留言内容: 李文：你好！
还有一个问题，对于计算机算法来说，我认为低阶缺陷幻方的填充问题是，越是低阶越难，越是高阶反而越容易，这与要求高于一般幻方的更完美的幻方构造性质一样。但对于象您这种幻方构造专家来说，如果仅用心智去填充，也许低阶缺陷幻方的填充比高阶更容易，因为人类的“心智”是有极限和维度的。您认为如何？姓名: 谢涛 於 2002.07.02.11:20:33
邮箱: taoxie@nudt.edu.cn
主页: http://
留言内容: 不知诸位高手对“缺陷幻方”的填充问题有什么最新的研究结果？
姓名: 谢涛 於 2002.04.19.03:39:13
邮箱: taoxie@nudt.edu.cn
主页: http://
留言内容: 我研究了一种通用的幻方演化构造算法，可以构造任意阶幻方，而且对于一定的阶数，在可能存在的幻方数量内，要构造多少幻方就能构造多少，成功率为100%。采用主频450MHZ的PC机，30阶以下幻方10秒以内可以构造，50阶幻方构造仅需1分钟，100阶幻方构造目前只需1个小时。不仅如此，对于庆典幻方，采用此算法也不是一件难事。采用人机结合，在完成人的艺术性构造后，可让机器来满足幻方的条件。有兴趣者可与本人联系，本人目前正在研究高次幻方的机器构造算法。
姓名: 谢涛 於 2002.04.19.03:17:01
邮箱: taoxie@nudt.edu.cn
主页: http://
留言内容: 请问各幻方研究高手：对于一个已知的幻方，如果随机地删去其中一半自然数而留下并固定另一半自然数，试问是否存在一种通用的有效算法能恢复被删去的那一半自然数的位置呢？恢复一半自然数已固定的幻方，其难度是否要比重新构造一个完整的幻方大呢？有人能从计算复杂度上分析二者的难度吗？感兴趣的学者可以与我联系，本人将提供一定的经费资助！
| 姓名: 谢涛 於 2002.05.04.12:42:38 邮箱: taoxie@nudt.edu.cn 主页: http:// 留言内容: 李文：你好！ 谢谢你能提供一些信息！ 四阶幻方共有880种，最近又有人计算5阶幻方的数量共有275305224种，但六阶幻方的数量至今未有准确结果。Pinn与Wieczerkowski应用Monte Carlo仿真方法，估计六阶幻方数量高达(1.7745±0.0016)╳(10的19次方）. 按传统确定式填充法得到的幻方只能是某些特殊幻方，也就是那些“尽人皆知”的幻方。我所构造的幻方不是按传统的某种填充法(确定方法）填充得到的，因此不能算是特殊幻方，采用你的能在一秒内构造一亿阶幻方的填充法是得不到我的算法所能得到的幻方的。简言之，我能在每阶幻方空间中均匀采样，而非局限于幻方空间中的某些局部领域！你能吗？ “一秒钟给你一百万个5次特优完美幻方”实在有点不现实，即使按你发明的“秘诀”并采用目前世界上最快的千万亿次高性能机也是做不到的！虽然只是言其多与快，但太离谱了！ 幻方有用否？这取决于各人的知识面与专业。高次幻方有用否？我没有做过研究！各种特优完美幻方有用否？我也没有做过研究！不过，我倒是找到了普通幻方的重要应用价值，非常有意义！如果你有意，请继续关注我所提出的半缺陷幻方的完成问题，并从计算理论到实际数值计算结果分析方面提出你对此问题负责任的真知灼见，凡是我认为有价值的结论与结果我都会以一定的方式表示“物有所值”的感谢！ 谢谢各位能继续提出反馈意见的学者与幻方构造高手！ |
姓名: 谢涛 於 2002.05.05.10:02:03 邮箱: taoxie@nudt.edu.cn 主页: http:// 留言内容: 李文：你好！ 用抽取的数去恢复一个幻方，我的要求是已多次说明，即不须恢复成与原幻方一模一样的幻方，而仅须与原幻方中的固定数字组成一个幻方即可。答案很可能不是唯一的(对20阶的幻方我已证实过)，但只要能找到一个解即为成功！我希望的是，即使用尽目前世界上的所有计算资源，并有包括象您一样的幻方研究高手的人工参与，采用人机结合的方式也不可能找到半缺陷幻方的一个解，注意仅仅一个解即可！ 幻方构造算法总的来说可分为确定式算法与随机式算法。传统的“秘诀”式解法可以说是确定是算法，其实不能称为算法而只能称为一个解，即“秘诀”本身就是解而非算法。好的诸如您李文先生构造完美幻方的“秘诀”采用了模运算，因而可得到多个(完美)幻方，而一般的“秘诀”只能得到一个幻方，仅此而已！而五阶以上幻方数量的指数爆增是我们不能仅仅满足于构造几个特殊幻方，仅仅依赖极小数量的特殊幻方是不可能真正研究幻方的潜在性质的。如果能研究一种在幻方的整个空间上采样的随机式算法，通过均匀的幻方空间采样可以至少从统计上研究幻方的潜在性质。我研究的幻方算法即是属于随机式算法，这种算法从理论上可以找出阶次一定的所有幻方(但实际上几乎不可能)！ 特殊的幻方解法，即使如您目前仍未公开的那些解法，我想总是有人可以通过各种方式得到的，如独立研究、花钱购买、偷窃、与您套近乎等等。只要是特殊幻方，总有公开的一天。 另，我要求的缺陷幻方的完成“通法”指一种算法，而非一种(个）“秘诀”，即对任何一个缺陷幻方都一定能找到一个解，或对任何一个缺陷幻方有一定的成功率。 未完，待续！ |
| 姓名: 谢涛 於 2002.05.04.13:24:55 邮箱: taoxie@nudt.edu.cn 主页: http:// 留言内容: 我并不希望告知各位有关自己的身份，在学术研究领域里，真理就是真理，与身份无关。大家最好不要对人感兴趣，感兴趣的应该是“问题”与“问题的解”！以平等的心态贡献各自对于问题的真知灼见，我想是一种最好的学术研究方式！ 高老师组织有关高手在尽可能短的时间内研究该问题，成功与失败的结果对我来说同样重要，但总得有个结论，即要么此问题不存在通用的有效算法，要么此问题存在通用的有效算法！非常感谢，并静候佳音！ |
Subject: 我们准备研究 谢涛 ： 你好，我们准备对您提出的问题进行研究。这项研究似乎与您的单位的科研应用有关，如果是这样，我们将尽力去搞，我们也希望能够找到幻方的用场。我将通知有关幻方能手们进行研究。 十阶完美幻方的要求是十行十列，即十条左对角线和十条右泛对角线所含各数和等于幻和。这是一道幻方难题，４、5、7、8、9、11、12、13、15都存在完美幻方，３、6阶幻方已证明不存在完美幻方。附件为７阶完美幻方构造法。 高治源 二○○二年四月二十日 |
| 姓名: 李文 於 2002.05.05.06:27:48 邮箱: liwen39@hotmail.com 主页: http:// 留言内容: 谢涛：你好！ 今晚看了你的留言，我想起了两年前认识黄均迪先生的情形，他主张先把七阶八阶幻方的解彻底搞清楚，然后再研究高阶，高次，多维幻方。这确实把我难倒了，即使给我最先进的计算机我也没有办法研究清楚七阶幻方，更不要说八阶，九阶了。但当时我已经找到了解决多维高次幻方的方法，因为七，八阶无法彻底搞清楚，他就对我多维高次的解法表示怀疑。 你提到的“特殊幻方”和“尽人皆知的幻方”，不知道是不是和黄先生的观点有点相似？这里大家理解上可能存在误区。 第一；我所能解出的幻方不是填充法得到的特殊幻方， 第二；不知你有什么为人不知幻方解法？ 第三：我认为你的问题非常之难，就是因为幻方的解太多，你的原幻方可能是你发现的任意一个幻方，而抽取的数也是任意的，要用抽取的数去复幻方，答案很可能不是唯一的，因此要通法我认为几乎不能， 第四：我认为只能在一定的阶数内，很小的阶数内，对你的问题给出计算机程序纯计算解法。正如你提到的六阶要计算它的数量是如此之难，这种方法在阶数上每突破一阶都非常之难。 第五：对你的原幻方作出限制，用某一种特殊的解法构成的幻方，这样可以得到通法。特殊的解法，是现未公开的解法，几乎无人掌握的解法，这类解法我有一些。 |
请高老师把有关我半缺陷幻方的填充问题的最新信息通知我！
高老师：你好！ |
| 高老师：你好！ 我用计算机产生20阶与30阶的幻方，每阶10个，然后在每个幻方中随机删去大约一半的元素，被删去的数字位置以0表示。请您或其他幻方高手在所附20阶幻方与30阶幻方中的0位置上用被我故意删去的数字集合中的数字添上，使得与其它已被固定的数字仍然构成一幻方。注意，所添数字只能属于被我删去的数字组成的集合，也即表中每一缺陷幻方中非0数字(固定数字)集合的补集，数字全集：30阶的幻方为连续自然数1，2，3，...,900；20阶的幻方为连续自然数1，2，3，...，400。数据表格为微软Office软件中的EXCEL，相信你们已安装！ 请不要参考我寄给您的压缩文件上的20阶与30阶的幻方数据，答案即在其中！ 如果你们果真能找到一种有效的P算法(非NP算法)，在可容许的计算时间内添上这些缺陷幻方中数字，那我们将有更多的有意义的问题等待更深一步的讨论，并且本人将提供科研经费！ 注意，完成这些缺陷幻方的填充之后，我将重新寄几组的新的幻方，作为检验！ |
To: 谢涛 Sent: Saturday, April 20, 2002 9:32 AM Subject: 你寄来的程序我们不知如何打开 谢涛朋友： 你好，来信已阅。你好大的气魄，一下子写了那么多，把我震惊了。 你提到：“对于一个已知的幻方，如果随机地删去其中一半自然数而留下并固定另一半自然数，试问是否存在一种通用的有效算法能恢复被删去的那一半自然数的位置呢？恢复一半自然数已固定的幻方，其难度是否要比重新构造一个完整的幻方大呢？”这个问题需要具体分析，看是应用那种方法构造的幻方，当去掉一半数字后，可以恢复的幻方不止一个，可能有几千种，这样显然复杂了。如果是一种特定的方法构造的幻方，我们可以通过其变化规律，迅速获得幻方原貌的恢复。我们如果从计算复杂度上分析二者的难度，那就可以这样想，若是用矩阵求解，由于已确定了一半数字，部分未知元已确定，故求解时显然简单了。但由于多解的情况，这又比单一构造幻方复杂的多。 这个问题，要具体分析，不知您遇到的问题属于那一类？我们下次再讨论。 不知你在哪里高职，我们如何更多地联系。我们有了许多构造幻方的程序，也希望搞一个幻方研究工具，加强合作是十分需要的。可是你寄来的程序我们不知如何打开，请指教。有一道幻方难题，你的程序能解决吗？即存在十阶完美幻方吗？注意不规则、无理完美幻方的理论。 高治源 2002年4月19日 |
|
高老师：你好！
本人就职于国防科学技术大学计算机学院并行与分布式处理国家重点实验室，由于一个偶然但又并非完全偶然的机会从91年10月开始研究幻方的机器构造算法，试图能找出关于一定阶数的幻方的尽量多的各种形式，即要多少就能产生多少。
所寄内容是经过Winzip70压缩过的，现把压缩处理程序寄来，安装后即能解压此类压缩文件。
至于固定一个幻方的一半元素而删去一半元素，并要求寻找另一半元素的问题，我的意思是只要能找到一种“通用的算法”求出一个解就行，即能找到另一半元素使之与已固定的一半元素仍然构造幻方，但这些找出来的元素集合必须等于原来删去的元素集合。注意，一定要是对任何阶数的幻方都通用！
另，请告知10阶完美幻方的要求，我对奇异幻方的种类了解并不多！
|
姓名: 谢涛 於 2002.04.19.14:17:28 邮箱: taoxie@nudt.edu.cn 主页: http:// 留言内容: 我正在申请专利,如果你要多少幻方我就可以给你多少幻方,但目前只能私下之间讨论,不能公开!我发现了幻方的一个构造假说,未能数学证明,但按此假说的构造成功率100%.
请高老师审阅！这是半年前的程序运行结果，现在的速度更快！PC主频450MHZ.
机器构造的幻方:要多少有多少Tao Xie [taoxie@nudt.edu.cn]，要多奇巧就有多奇巧！ |