求解4x3的方格填数,1-8不重复放入8个格子中,四个角的格子为空,格子里的数字左右、上下,对角线不连续,输出某个正确结果并统计正确结果次数
时间: 2024-02-17 12:02:33 浏览: 230
这是一个稍微复杂一些的问题,需要对上面提供的算法进行适当的修改。下面是一个解法:
1. 定义一个 4x3 的二维数组,表示方格。
2. 定义一个递归函数,用来填充方格。
3. 递归函数的参数包括当前填充的行和列、可用的数字、方格二维数组。
4. 递归函数逐个尝试可用的数字,如果符合要求(不与同行、同列、同宫格中的数字重复,且左右、上下、对角线不连续),则填充到方格中。
5. 如果填充完当前行,就递归到下一行;如果填充完最后一行,就说明找到了一个可行解。
6. 如果当前位置无法填充任何数字,则返回到上一级递归,尝试其他数字。
下面是代码示例:
```
grid = [[0, 0, 0], [0, -1, 0], [0, 0, 0], [-1, 0, -1]]
def is_valid(row, col, num):
# 检查同行、同列、同宫格是否已经使用过该数字
for i in range(4):
if grid[row][i] == num or grid[i][col] == num:
return False
row_start = (row // 2) * 2
col_start = (col // 2) * 2
for i in range(row_start, row_start + 2):
for j in range(col_start, col_start + 2):
if grid[i][j] == num:
return False
# 检查左右、上下、对角线是否连续
if col > 0:
if abs(grid[row][col - 1] - num) == 1:
return False
if row > 0:
if abs(grid[row - 1][col] - num) == 1:
return False
if row > 0 and col > 0:
if abs(grid[row - 1][col - 1] - num) == 1:
return False
if row > 0 and col < 2:
if abs(grid[row - 1][col + 1] - num) == 1:
return False
return True
def solve(row, col, count):
# 如果已经填充完最后一行,返回 True 表示找到可行解
if row == 4:
print("Solution %d:" % count)
for i in range(4):
for j in range(3):
if grid[i][j] == -1:
print(" ", end="")
else:
print(grid[i][j], end="")
print()
print()
return count + 1
# 如果当前位置已经填充过,就递归到下一个位置
if grid[row][col] != 0:
if col == 2:
return solve(row + 1, 0, count)
else:
return solve(row, col + 1, count)
# 尝试填充可用数字
for num in range(1, 9):
if is_valid(row, col, num):
grid[row][col] = num
if col == 2:
count = solve(row + 1, 0, count)
else:
count = solve(row, col + 1, count)
grid[row][col] = 0
# 如果无法填充该位置,返回 False
return count
# 调用递归函数并输出结果
count = solve(0, 0, 0)
print("Total solutions: %d" % count)
```
这段代码可以求解 4x3 的方格填数问题,其中 `-1` 表示空格,数字 `1-8` 表示可用数字。运行程序后,会输出一个正确的结果,并统计所有正确结果的数量。
阅读全文