我在编程论坛 Ohjelmointiputka 中发现了这个问题：
-
https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=ahdruu https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=ahdruu and
-
https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=ahdruu2 https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=ahdruu2
有人说计算机可以找到解决方案，但我找不到证明。
证明存在一个包含 117 个元素且包含数字的矩阵，使得人们可以读取数字 1、2、...、100 的平方。
这里的 read 意味着你固定起始位置和方向（8 种可能性），然后朝那个方向走，连接数字。例如，如果您可以连续找到数字 1,0,0,0,0,4，则您找到了整数 100004，其中包含 1、2、10、100 和 20 的平方数，因为您可以从该序列中读出 1、4、100、10000 和 400（反转）。
但是要找到的数字太多了（准确地说，是 100 个平方数，如果删除另一个总共 312 位的平方数中包含的数字，则为 81 个），而矩阵中的整数又太少了，因此您必须将所有这些数都放入平方数如此密集，以至于找到这样的矩阵很困难，至少对我来说是这样。
我发现如果存在这样一个矩阵mxn，我们可以不失一般性地假设m1x117, 3x39 or 9x13。但是什么样的算法可以找到矩阵呢？
我已经成功地编写了一个程序来检查要添加的数字是否可以放在黑板上。但如何实现搜索算法呢？
# -*- coding: utf-8 -*-
# Returns -1 if can not put and value how good a solution is if can be put. Bigger value of x is better.
def can_put_on_grid(grid, number, start_x, start_y, direction):
# Check that the new number lies inside the grid.
x = 0
if start_x < 0 or start_x > len(grid[0]) - 1 or start_y < 0 or start_y > len(grid) - 1:
return -1
end = end_coordinates(number, start_x, start_y, direction)
if end[0] < 0 or end[0] > len(grid[0]) - 1 or end[1] < 0 or end[1] > len(grid) - 1:
return -1
# Test if new number does not intersect any previous number.
A = [-1,-1,-1,0,0,1,1,1]
B = [-1,0,1,-1,1,-1,0,1]
for i in range(0,len(number)):
if grid[start_x + A[direction] * i][start_y + B[direction] * i] not in ("X", number[i]):
return -1
else:
if grid[start_x + A[direction] * i][start_y + B[direction] * i] == number[i]:
x += 1
return x
def end_coordinates(number, start_x, start_y, direction):
end_x = None
end_y = None
l = len(number)
if direction in (1, 4, 7):
end_x = start_x - l + 1
if direction in (3, 6, 5):
end_x = start_x + l - 1
if direction in (2, 0):
end_x = start_x
if direction in (1, 2, 3):
end_y = start_y - l + 1
if direction in (7, 0, 5):
end_y = start_y + l - 1
if direction in (4, 6):
end_y = start_y
return (end_x, end_y)
if __name__ == "__main__":
A = [['X' for x in range(13)] for y in range(9)]
numbers = [str(i*i) for i in range(1, 101)]
directions = [0, 1, 2, 3, 4, 5, 6, 7]
for i in directions:
C = can_put_on_grid(A, "10000", 3, 5, i)
if C > -1:
print("One can put the number to the grid!")
exit(0)
我还发现认为暴力搜索或最佳优先搜索太慢。我认为可能有一个使用模拟退火、遗传算法或装箱算法的解决方案。我还想知道是否可以应用马尔可夫链以某种方式找到网格。不幸的是，以我目前的技能来说，这些似乎太难实现了。
