<p>这是我的解决方案。<strong>但是这不是一个快速的解决方案。它使用了搜索函数的递归实现。在每一次递归中,它探索每一行的所有可能乘积值(不包括当前行的第一个元素,直到对角线值),并检查当前解决方案是否有效。如果它到达递归的结尾,它将附加当前的矩阵解。你知道吗</p>
<p>假设是n!解决方案,但由于我在解决方案不正确时中断搜索,搜索在到达所有可能的解决方案之前停止。你知道吗</p>
<pre><code>import sys, copy
from itertools import product
def recursiveSearch(actual, index, size, matrices):
if index==size-1:
for j in range(size):
if sum([actual[i][j] for i in range(size)])>1:
return
if sum([actual[i][j] for i in range(size) for j in range(size)]) == size:
matrices.append(actual)
return
return
cur_row = len(actual)
for j in range(size):
if sum([actual[i][j] for i in range(cur_row)])>1:
return
pr = product([0, 1], repeat=size-index-1)
for p in pr:
new_row = [0 for k in range(index+1)] + list(p)
new_matrix = copy.deepcopy(actual)
new_matrix.append(new_row)
recursiveSearch(new_matrix, index+1, size, matrices)
if __name__ == '__main__':
input_ = int(sys.argv[1])
pr = product([0,1], repeat=input_)
matrices = []
for p in pr:
recursiveSearch([list(p)], 0, input_, matrices)
for m in matrices:
print(m)
</code></pre>
<p>一个更有效的解决方案是搜索列,而不是搜索行,这是我现在搜索的方式,因为检查正确性需要更少的计算(只有当前列的总和正好为1时才需要检查)</p>
<p>当然,对列的搜索只需要沿着列移动1</p>