证明存在特定矩阵 [英] Proving that a particular matrix exists
问题描述
我在编程论坛Ohjelmointiputka中发现了这个问题：
- https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=ahdruu 和
- https://www.ohjelmointiputka.net/postit/tehtava.php？ tunnus = ahdruu2
有人说计算机找到了解决方案，但我找不到证据
证明存在一个矩阵，其中包含117个包含数字的元素，以便人们可以读取数字1、2，...，100的平方。 p>
此处读取表示您固定了起始位置和方向（8种可能性），然后沿该方向前进，将数字连接在一起。例如，如果您可以连续找到例如数字1,0,0,0,0,4，则发现整数100004，其中包含1、2、10、100和20的平方数，因为您可以从该序列中读取1、4、100、10000和400（反向）。
但是可以找到这么多数字（100个平方数精确的；如果您删除包含在另一个平方中的总数为312位的整数），则为81；如果矩阵中的整数太少，则必须将所有这些平方数如此密集地放置，以致于很难找到这样的矩阵，至少对我而言
我发现，如果存在这样的矩阵mxn，我们可以假设m <= n而不失一般性。因此，矩阵的类型必须为 1x117 ， 3x39 或 9x13 。但是，哪种算法会找到矩阵？
我设法完成了一个程序，检查要添加的数字是否可以放在板上。但是如何实现搜索算法？
＃-*-编码：utf-8-*-
＃如果不能放置，则返回-1，并估计可以放置的解决方案的质量。 x的值越大越好。
def can_put_on_grid（网格，数字，start_x，start_y，方向）：
＃检查新数字是否位于网格内。
x = 0
如果start_x< 0或start_x> len（grid [0]）-1或start_y< 0或start_y> len（grid）-1：
return -1
end = end_coordinates（number，start_x，start_y，direction）
如果end [0]< 0或end [0]> len（grid [0]）-1或end [1]< 0或end [1]> len（grid）-1：
return -1
＃测试新数字是否不与任何先前数字相交。
A = [-1，-1，-1,0,0,1,1,1，]
B = [-1,0,1，-1,1，-1,0， 1] i在范围（0，len（number））中的
：如果grid [start_x + A [direction] * i] [start_y + B [direction] * i]不在（ X中，则
，数字[i]）：
返回-1
否则：
如果grid [start_x + A [direction] * i] [start_y + B [direction] * i] ==数字[i]：
x + = 1
返回x
def end_coordinates（数字，start_x，start_y，方向）：
end_x =无
end_y =无
l = len（number）
如果方向为（1、4、7）：
end_x = start_x-l + 1
如果方向为（3、6、5） ：
end_x = start_x + l-1
如果方向为（2，0）：
end_x = start_x
如果方向为（1、2、3）：
end_y = start_y-l + 1
如果方向为（7，0，5）：
end_y = start_y + l-1
如果方向为（4，6）：
end_y = start_y
返回（end_x，end_y）
如果__na me__ == __main__：
A = [[['X'for x in range（13）]] for y in range（9）]
数字= [str（i * i）for i in range（1，101）]
方向= [0、1、2、3、4、5、6、7]
对于i方向：
C = can_put_on_grid（A， 10000，3，5，i）
如果C> -1：
打印（可以将数字放到网格中！）
退出（0）
我还发现蛮力搜索或最佳优先搜索太慢。我认为可能有使用模拟退火，遗传算法或装箱算法的解决方案。我也想知道是否可以以某种方式应用马尔可夫链来找到网格。不幸的是，这些对于我而言，以当前的技能来说似乎太难实现了。
在 https://github.com/minkkilaukku/square-packing/blob/master/sqPackMB .py 。只需从第20行和第21行更改M = 9，N = 13。
I found this problem in a programming forum Ohjelmointiputka:
- https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=ahdruu and
- https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=ahdruu2
Somebody said that there is a solution found by a computer, but I was unable to find a proof.
Prove that there is a matrix with 117 elements containing the digits such that one can read the squares of the numbers 1, 2, ..., 100.
Here read means that you fix the starting position and direction (8 possibilities) and then go in that direction, concatenating the numbers. For example, if you can find for example the digits 1,0,0,0,0,4 consecutively, you have found the integer 100004, which contains the square numbers of 1, 2, 10, 100 and 20, since you can read off 1, 4, 100, 10000, and 400 (reversed) from that sequence.
But there are so many numbers to be found (100 square numbers, to be precise, or 81 if you remove those that are contained in another square number with total 312 digits) and so few integers in a matrix that you have to put all those square numbers so densely that finding such a matrix is difficult, at least for me.
I found that if there is such a matrix mxn, we may assume without loss of generalty that m<=n. Therefore, the matrix must be of the type 1x117, 3x39 or 9x13. But what kind of algorithm will find the matrix?
I have managed to do the program that checks if numbers to be added can be put on the board. But how can I implemented the searching algorithm?
# -*- 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)
I also found think that brute force search or best first search is too slow. I think there might be a solution using simulated annealing, genetic algorithm or bin packing algorithm. I also wondered if one can apply Markov chains somehow to find the grid. Unfortunately those seems to be too hard for me to implemented at current skills.
There is a program for that in https://github.com/minkkilaukku/square-packing/blob/master/sqPackMB.py . Just change M=9, N=13 from the lines 20 and 21.
这篇关于证明存在特定矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
