-3

我正在尝试在 python 中编写一个简单的数独求解器。基本概念是数独谜题被部分填充，未解决的单元格用零表示。任何用零表示的单元格都可以在拼图的任何阶段解决。因此，如果第一个单元格为 0，则意味着该行、列和 3x3 子网格中的值确保该单元格只能有一个可能的值。这是我的代码，我似乎被卡住了，因为输出显示了不止一种可能性。我的算法错了吗？

def solveOne (array, posR, posC):

possible = ['1','2','3','4','5','6','7','8','9']

for col in range (9):
    if array[posR][col] in possible:
        possible.remove(array[posR][col])


for row in range (9):
    if array[row][posC] in possible:
        possible.remove(array[row][posC])

for row in range(posR, posR+3):
    for col in range (posC, posC+3):
        if array[row::][col::] in possible:
            possible.remove(array[row][col])

print (possible)
return possible

grid = [["" for _ in range(9)] for _ in range(9)] #define a 9x9 2-dimensional list

for row in range(9):
    aLine = input() #prompt user to enter one line of characters
    for col in range(9):
        grid[row][col] = aLine[col:col+1] #assign every character in a line to a position in the 2-D array

for row in range(9):
    for col in range (9):
        if grid[row][col] == '0':
            r = row
            c = col
            newV = solveOne (grid,r,c)
            grid[row][col] = newV

print()
for i in range (9):
    for k in range(9):
        print(grid[i][k], end = "")
    print()
4

1 回答 1

1

有几个错误： 

for row in range(posR, posR+3):
    for col in range (posC, posC+3):
        if array[row::][col::] in possible:
            possible.remove(array[row][col])

不会做你想让它做的事情。您最好尝试（对于 python 2.7 - 注意 div 操作不是浮点除法而是整数除法）： 

block = ((posR/3)*3,(posC/3)*3) # get the top left cell of the 3x3 block
for row in range(block[0], block[0]+3):
    for col in range (block[1], block[1]+3):
        if array[row][col] in possible:
            possible.remove(array[row][col])

所以现在效果更好了。但是通过做 

for row in range(9):
    for col in range (9):
        if grid[row][col] == '0':
            r = row
            c = col
            newV = solveOne (grid,r,c)
            grid[row][col] = newV

你只经历一次数独。有时需要不止一步解决数独问题——想想看。

而且您还必须意识到，并非每个数独都有独特的解决方案。想想解决一个空的数独 - 你几乎可以“做你想做的事”。

于 2013-05-13T10:24:43.583 回答