-3

Python で単純な数独ソルバーを作成しようとしています。基本的なコンセプトは、数独パズルが部分的に埋められ、未解決のセルがゼロで示されるというものです。ゼロで示されるセルは、パズルのどの段階でも解くことができます。したがって、最初のセルが 0 の場合、その行、列、および 3x3 サブグリッドの値により、そのセルに可能な値が 1 つしかないことが保証されます。これが私のコードです。出力に複数の可能性が表示されるため、行き詰まっているようです。私のアルゴリズムは間違っていますか？

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 に答える