Python/数独求解器/方法运行不正确

huangapple go评论78阅读模式
英文:

Python/ Sudoku solver/ Method works incorrect

问题

我正在尝试在Python中实现数独求解器,我的一个方法尽管相当简单和短小,但并不总是正确运行。我的代码中有一个sudoku_grid(零表示空格),还有一个包含每个格子可能数字的possibility_arrays列表。问题出现在change_value(row, column, value)这个方法中,它会在找到一个数字后简单地更改一个格子的值,并从同一行、列和九宫格中的其他可能性数组中删除这个特定数字。

以下是代码(我只放了相关部分 - 还有其他方法,简单地应用了不同的消除技巧 - 我进行了一些跟踪,发现问题似乎出现在这个方法中):

sudoku_grid = [
    [4, 2, 9, 0, 0, 3, 0, 0, 0],
    [3, 7, 0, 1, 0, 0, 9, 0, 0],
    [0, 0, 0, 2, 9, 0, 3, 0, 0],
    [8, 3, 0, 0, 1, 0, 4, 0, 6],
    [0, 0, 0, 8, 0, 0, 7, 5, 0],
    [7, 4, 5, 9, 3, 0, 0, 1, 0],
    [9, 0, 0, 7, 0, 0, 0, 3, 1],
    [2, 5, 7, 0, 0, 0, 6, 0, 0],
    [6, 0, 3, 0, 0, 9, 8, 0, 7]
]
possibility_arrays = []
for _ in range(9):
    possibility_arrays.append([])
for s in range(9):
    for x in range(9):
        possibility_arrays[x].append([])

def is_valid(row, column, num):
    # 检查数字是否已经存在于行中
    if num in sudoku_grid[row]:
        return False

    # 检查数字是否已经存在于列中
    for i in range(9):
        if sudoku_grid[i][column] == num:
            return False

    # 检查数字是否已经存在于3x3九宫格中
    start_row = (row // 3) * 3
    start_col = (column // 3) * 3
    for a in range(start_row, start_row + 3):
        for b in range(start_col, start_col + 3):
            if sudoku_grid[a][b] == num:
                return False

    return True

def change_value(row, column, value):

    if is_valid(row, column, value):
        sudoku_grid[row][column] = value
        possibility_arrays[row][column] = []

        for k in range(9):
            if value in possibility_arrays[k][column]:
                possibility_arrays[k][column].remove(value)
            if value in possibility_arrays[row][k]:
                possibility_arrays[row][k].remove(value)

        start_row = (row // 3) * 3
        start_col = (column // 3) * 3
        for a in range(start_row, start_row + 3):
            for b in range(start_col, start_col + 3):
                if value in possibility_arrays[a][b]:
                    possibility_arrays[a][b].remove(value)
    else:
        print("存在错误")

在一些消除过程后,以下是possibility_arrays的样子:

[[], [], [], [], [], [], [1], [8], [5]],
[[], [], [], [], [4, 5], [4, 5], [], [6], [2]],
[[], [], [], [], [], [4, 8], [], [7, 8], [4]],
[[], [], [], [], [], [], [], [], []],
[[], [], [], [], [2, 4], [2, 4], [], [], [3]],
[[], [], [], [], [], [6], [], [], []],
[[], [], [], [], [2, 6], [2, 6], [], [], []],
[[], [], [], [3], [8], [1], [], [], []],
[[], [], [], [], [5], [], [], [], []],

当我运行代码 change_value(5, 5, possibility_array[5][5][0]) 时,它会如预期地从 possibility_array[6][5] 中移除 6,因为它位于相同的列,但还会从 possibility_arrays[6][4] 中移除 6,并且变成了这样:

[[], [], [], [], [], [], [1], [8], [5]]
[[], [], [], [], [4, 5], [4, 5], [], [6], [2]]
[[], [], [], [], [], [4, 8], [], [7, 8], [4]]
[[], [], [], [], [], [], [], [], []]
[[], [], [], [], [2, 4], [2, 4], [], [], [3]]
[[], [], [], [], [], [], [], [], []]
[[], [], [], [], [2], [2], [], [], []]
[[], [], [], [3], [8], [1], [], [], []]
[[], [], [], [], [5], [], [], [], []]

我不知道为什么它有时会不正确工作,有时却能正常工作。正如我所说,我只是在这两种状态之间加入了这一行代码(change_value(5, 5, possibility_array[5][5][0]))。这些数组彼此之间没有关联,它们是独立的。为什么会出现这种情况呢?

英文:

I am trying to implement a sudoku solver in Python and one of my methods does not work correctly even though it is pretty simple and short. There is one sudoku_grid (zero means box is empty) in my code and one possibility_arrays list which contains possible numbers for each box. So this problematic method is change_value(row, column, value) which simply changes the value for one box once it is found and removes this particular number from other possiblity arrays in the same box, column and grid.

Here is the code (i only put related parts -there is other methods which simply applies different elimination techniques-i did some tracking and found problem lies in this method for some reason-:

    sudoku_grid = [
[4, 2, 9, 0, 0, 3, 0, 0, 0],
[3, 7, 0, 1, 0, 0, 9, 0, 0],
[0, 0, 0, 2, 9, 0, 3, 0, 0],
[8, 3, 0, 0, 1, 0, 4, 0, 6],
[0, 0, 0, 8, 0, 0, 7, 5, 0],
[7, 4, 5, 9, 3, 0, 0, 1, 0],
[9, 0, 0, 7, 0, 0, 0, 3, 1],
[2, 5, 7, 0, 0, 0, 6, 0, 0],
[6, 0, 3, 0, 0, 9, 8, 0, 7]
]
possibility_arrays = []
for _ in range(9):
possibility_arrays.append([])
for s in range(9):
for x in range(9):
possibility_arrays[x].append([])
def is_valid(row, column, num):
# Check if the number already exists in the row
if num in sudoku_grid[row]:
return False
# Check if the number already exists in the column
for i in range(9):
if sudoku_grid[i][column] == num:
return False
# Check if the number already exists in the 3x3 grid
start_row = (row // 3) * 3
start_col = (column // 3) * 3
for a in range(start_row, start_row + 3):
for b in range(start_col, start_col + 3):
if sudoku_grid[a][b] == num:
return False
return True
def change_value(row, column, value):
if is_valid(row,column,value):
sudoku_grid[row][column] = value
possibility_arrays[row][column] = []
for k in range(9):
if value in possibility_arrays[k][column]:
possibility_arrays[k][column].remove(value)
if value in possibility_arrays[row][k]:
possibility_arrays[row][k].remove(value)
start_row = (row // 3) * 3
start_col = (column // 3) * 3
for a in range(start_row, start_row + 3):
for b in range(start_col, start_col + 3):
if value in possibility_arrays[a][b]:
possibility_arrays[a][b].remove(value)
else:
print("THERE IS A MISTAKE")

And here is the possibility_arrays after some elimination process:

[[], [], [], [], [], [], [1], [8], [5]],
[[], [], [], [], [4, 5], [4, 5], [], [6], [2]],
[[], [], [], [], [], [4, 8], [], [7, 8], [4]],
[[], [], [], [], [], [], [], [], []],
[[], [], [], [], [2, 4], [2, 4], [], [], [3]],
[[], [], [], [], [], [6], [], [], []],
[[], [], [], [], [2, 6], [2, 6], [], [], []],
[[], [], [], [3], [8], [1], [], [], []],
[[], [], [], [], [5], [], [], [], []],

And when i put the code change_value(5, 5, possibility_array[5][5][0]) it simply removes 6 as expected from possibility_array[6][5] since it is in the same column but also removes 6 from possibility_arrays[6][4] and turns into this:

[[], [], [], [], [], [], [1], [8], [5]]
[[], [], [], [], [4, 5], [4, 5], [], [6], [2]]
[[], [], [], [], [], [4, 8], [], [7, 8], [4]]
[[], [], [], [], [], [], [], [], []]
[[], [], [], [], [2, 4], [2, 4], [], [], [3]]
[[], [], [], [], [], [], [], [], []]
[[], [], [], [], [2], [2], [], [], []]
[[], [], [], [3], [8], [1], [], [], []]
[[], [], [], [], [5], [], [], [], []]

I have no idea how it sometimes works incorrect and works totally fine. As i said i only put this line (change_value(5, 5, possibility_array[5][5][0])) between these two states. And arrays are not related to each other, they are individual. Why this might happen?

答案1

得分: 1

事实证明,change_value 方法并不是问题的根本原因。显然,在我实现数独解决技巧(hidden_pairs)的另一个方法中,我输入了以下代码:

possibility_arrays[i][j] = mutual_array
possibility_arrays[i][k] = mutual_array

这些代码似乎是导致问题的原因。当我将其编辑为以下方式后,问题就解决了:

possibility_arrays[i][j] = mutual_array.copy()
possibility_arrays[i][k] = mutual_array.copy()

我之前认为change_value 是问题的原因,因为它一次删除了2个值,但现在我认为问题出在了数组上。

英文:

Turns out change_value method was not the problem. Apperantly, in one of my other methods that I implement sudoku solving techniques (hidden_pairs), I typed a code which simply says

possibility_arrays[i][j] = mutual_array
possibility_arrays[i][k] = mutual_array

And this was somehow causing the problem, I guess. When I edited as this, the problem was fixed:

possibility_arrays[i][j] = mutual_array.copy()
possibility_arrays[i][k] = mutual_array.copy()

I thought change_value was the problem since it was removing 2 values at the same time, but now I assume it was the arrays.

答案2

得分: 0

如果您的代码有问题,这里没有显示出来。 使用change_value不断传播值可以很好地解决这个谜题:

# 使用正确的初始状态设置 possibility_array。
for row in range(9):
    for col in range(9):
        possibility_arrays[row][col].extend(range(1, 10))
for row in range(9):
    for col in range(9):
        value = sudoku_grid[row][col]
        if value > 0:
            # 通过一种巧妙的方式传播更改,而不会导致 is_valid 检查失败。
            sudoku_grid[row][col] = 0
            change_value(row, col, value)

# 持续传播只有一个可能性的单元格。
progress = True
while progress:
    progress = False
    for row in range(9):
        for col in range(9):
            if len(possibility_arrays[row][col]) == 1:
                change_value(row, col, possibility_arrays[row][col][0])
                progress = True

# 要么我们解决了这个谜题,要么不得不猜测。
from pprint import pprint
pprint(sudoku_grid)
[[4, 2, 9, 6, 7, 3, 1, 8, 5],
 [3, 7, 8, 1, 4, 5, 9, 6, 2],
 [5, 6, 1, 2, 9, 8, 3, 7, 4],
 [8, 3, 2, 5, 1, 7, 4, 9, 6],
 [1, 9, 6, 8, 2, 4, 7, 5, 3],
 [7, 4, 5, 9, 3, 6, 2, 1, 8],
 [9, 8, 4, 7, 6, 2, 5, 3, 1],
 [2, 5, 7, 3, 8, 1, 6, 4, 9],
 [6, 1, 3, 4, 5, 9, 8, 2, 7]]
英文:

If there's something wrong with your code, it's not shown here. Continuously propagating values with change_value solved the puzzle just fine:

# Setup possibility_array with correct values for starting state.
for row in range(9):
    for col in range(9):
        possibility_arrays[row][col].extend(range(1, 10))
for row in range(9):
    for col in range(9):
        value = sudoku_grid[row][col]
        if value > 0:
            # Hacky way of propagating changes without failing the is_valid check.
            sudoku_grid[row][col] = 0
            change_value(row, col, value)

# Continuosly propagate cells with a single possibility.
progress = True
while progress:
    progress = False
    for row in range(9):
        for col in range(9):
            if len(possibility_arrays[row][col]) == 1:
                change_value(row, col, possibility_arrays[row][col][0])
                progress = True

# We either solved the puzzle, or have to guess.
from pprint import pprint
pprint(sudoku_grid)
[[4, 2, 9, 6, 7, 3, 1, 8, 5],
[3, 7, 8, 1, 4, 5, 9, 6, 2],
[5, 6, 1, 2, 9, 8, 3, 7, 4],
[8, 3, 2, 5, 1, 7, 4, 9, 6],
[1, 9, 6, 8, 2, 4, 7, 5, 3],
[7, 4, 5, 9, 3, 6, 2, 1, 8],
[9, 8, 4, 7, 6, 2, 5, 3, 1],
[2, 5, 7, 3, 8, 1, 6, 4, 9],
[6, 1, 3, 4, 5, 9, 8, 2, 7]]

huangapple
  • 本文由 发表于 2023年7月18日 00:26:11
  • 转载请务必保留本文链接:https://go.coder-hub.com/76706424.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定