我正在尝试填充 3x3 矩阵(正方形(中缺失的字段以形成一个魔方(行,列两个对角线的总和相同,填充任何不重复的正整数(。 这种正方形的一个例子是:
[_ _ _]
[_ _ 18]
[_ 28 _]
由于它不遵循普通魔方的基本规则,其中其整数限制为 1-9(从 1 到 n^2(。 ,魔术常数(总和(不等于 15 (n(n^2+1(/2( 相反,它是未知的,并且有许多可能的值。
我尝试了一种非常幼稚的方法,我在空字段中生成随机数,任意最大值为 99,然后我把整个正方形传递给一个函数,检查它是否是一个有效的魔方。
它基本上永远持续下去,直到它在正确的位置找到数字组合。
不用说,这个解决方案很愚蠢,它会持续数小时才能找到答案。
我还考虑过进行详尽的数字生成(基本上尝试每种数字组合(,直到找到正确的数字,但这面临着同样的问题。
所以我需要帮助找出一种算法或某种方法来限制生成的随机数的范围
3 x 3 魔方是具有以下三个基元素的向量空间:
1 1 1 0 1 -1 -1 1 0
1 1 1 -1 0 1 1 0 -1
1 1 1 1 -1 0 0 -1 1
您可以引入 3 个变量 a、b、c,它们代表 3 个基元素中每个元素的贡献,并在给定偏解的情况下为它们编写方程。
例如,给定您的示例网格,您将拥有:
a + b - c = 18
a - b - c = 28
立即给出 2b = 10 或 b=-5。和 a-c = 23,或 c=a-23。
解决方案的空间如下所示:
23 2a-28 a+5
2a-18 a 18
a-5 28 2a-23
您可以看到每行/列/对角线加起来为 3a。
现在,您只需要找到满足正约束和非重复约束的 a 和 c 的整数解。
例如,a=100, b=-5, c=77 给出:
23 172 105
182 100 18
95 28 177
具有正整数元素的最小和魔方出现在 a=15 时,总和为 3a=45。
23 2 20
12 15 18
10 28 7
碰巧这里没有重复。如果有,我们只需尝试下一个更大的a
值,依此类推。
一种可能的方法是将给定的数字转换为其他值。简单的除法是不可能的,但你可以用(N-13(/5翻译。然后你有一个部分填充的正方形:
- - - 2 7 6
- - 1 for which there is a solution 9 5 1
- 3 - 4 3 8
When you translate these numbers back with (N*5)+13, you obtain:
23 48 43
58 38 18 which sums up to 114 in all directions (5 * 15) + (3 * 13)
33 28 53