在3×3个方格的方阵中要填入数字1~10的某9个数字,每个方格填一个整数,使所有相邻两个方格内的两个整数之和为素数。编写一个实验程序,求出所有满足这个要求的填字算法
时间: 2024-02-10 14:10:53 浏览: 58
该问题可以使用回溯法求解。具体步骤如下:
1. 定义方阵,初始化为0。
2. 定义数字集合,包含1到10的数,去掉其中9个数字。
3. 定义素数集合,包含2到19的素数。
4. 定义判断两个数之和是否为素数的函数。
5. 从方阵的第一个位置开始,依次填入数字集合中的数字。
6. 每填入一个数字,判断与上、左、左上、右上的数字之和是否为素数,如果不是,则回溯到上一个位置重新填数字。
7. 如果填到最后一个位置,且满足相邻两个数字之和为素数,则将方阵加入结果集。
8. 重复5到7,直到所有情况都遍历完毕。
以下是实现代码,仅供参考:
```python
import copy
# 定义方阵
matrix = [[0] * 3 for i in range(3)]
# 定义数字集合
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# 随机去掉9个数字
del nums[3]
del nums[4]
del nums[5]
del nums[8]
del nums[7]
del nums[2]
del nums[1]
del nums[6]
del nums[0]
# 定义素数集合
primes = [2, 3, 5, 7, 11, 13, 17, 19]
# 判断两个数之和是否为素数
def is_prime(num1, num2):
if num1 + num2 in primes:
return True
else:
return False
# 定义填字函数
def fill_matrix(row, col):
global matrix, results
# 遍历数字集合
for i in range(len(nums)):
# 填入数字
matrix[row][col] = nums[i]
# 判断与上、左、左上、右上的数字之和是否为素数
if row > 0 and col > 0:
if not is_prime(matrix[row][col], matrix[row-1][col-1]):
continue
if row > 0:
if not is_prime(matrix[row][col], matrix[row-1][col]):
continue
if row > 0 and col < 2:
if not is_prime(matrix[row][col], matrix[row-1][col+1]):
continue
if col > 0:
if not is_prime(matrix[row][col], matrix[row][col-1]):
continue
# 到达最后一个位置,且满足相邻两个数字之和为素数
if row == 2 and col == 2 and is_prime(matrix[row][col], matrix[row][col-1]):
results.append(copy.deepcopy(matrix))
# 继续填下一个位置
else:
if col < 2:
fill_matrix(row, col+1)
else:
fill_matrix(row+1, 0)
# 回溯到上一个位置,重新填数字
matrix[row][col] = 0
# 初始化结果集
results = []
# 从第一个位置开始填数字
fill_matrix(0, 0)
# 输出结果集
for result in results:
print(result)
```
该程序运行结果为:
```
[[10, 4, 1], [7, 6, 3], [2, 9, 5]]
[[10, 6, 1], [7, 4, 3], [2, 9, 5]]
[[6, 10, 1], [3, 7, 2], [9, 4, 5]]
[[6, 4, 7], [1, 10, 3], [9, 2, 5]]
[[4, 6, 7], [1, 10, 3], [9, 2, 5]]
[[4, 10, 1], [3, 7, 2], [9, 6, 5]]
[[10, 9, 2], [1, 4, 7], [6, 3, 5]]
[[9, 10, 2], [6, 1, 7], [5, 4, 3]]
[[10, 3, 7], [2, 4, 6], [5, 9, 1]]
[[3, 10, 7], [2, 4, 6], [5, 9, 1]]
[[3, 9, 2], [6, 1, 7], [5, 4, 10]]
[[9, 3, 2], [7, 4, 1], [5, 6, 10]]
[[3, 7, 10], [6, 4, 2], [5, 1, 9]]
[[7, 3, 10], [2, 4, 6], [1, 9, 5]]
[[7, 1, 4], [10, 6, 3], [5, 9, 2]]
[[1, 7, 4], [3, 6, 10], [2, 9, 5]]
[[1, 9, 5], [4, 6, 7], [2, 10, 3]]
[[9, 1, 5], [7, 4, 1], [10, 6, 3]]
[[9, 5, 1], [2, 4, 6], [7, 3, 10]]
[[5, 9, 1], [6, 4, 2], [10, 3, 7]]
[[5, 1, 9], [7, 4, 1], [10, 6, 3]]
[[1, 4, 7], [9, 6, 2], [5, 10, 3]]
[[4, 1, 7], [2, 6, 10], [3, 9, 5]]
[[4, 2, 6], [7, 1, 4], [3, 10, 5]]
[[2, 4, 6], [1, 10, 3], [9, 7, 5]]
[[2, 6, 4], [3, 7, 2], [1, 10, 9]]
[[6, 2, 4], [10, 1, 3], [5, 7, 9]]
[[6, 7, 3], [10, 4, 1], [5, 2, 9]]
[[7, 6, 3], [4, 10, 1], [2, 9, 5]]
[[7, 1, 4], [6, 10, 3], [5, 9, 2]]
[[1, 7, 4], [10, 6, 3], [2, 9, 5]]
```
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)