python~数独、ナンプレを解く
初めに
こんにちは、Keymaleです。今回は数独をpythonで解いてみたいと思います。
数独解法
とりあえず以下に数独を解くコードを載せます。
backtracks = 0
def solveSudoku(grid, i=0, j=0):
global backtracks
i, j = findNextCellTOFill(grid)
if i == -1:
return True
for e in range(1, 10):
if isValid(grid, i, j, e):
grid[i][j] = e
if solveSudoku(grid, i, j):
return True
backtracks += 1
grid[i][j] = 0
return False
def findNextCellTOFill(grid):
for x in range(0, 9):
for y in range(0, 9):
if grid[x][y] == 0:
return x, y
return -1, -1
def isValid(grid, i, j, e):
rowOK = all([e != grid[i][x] for x in range(9)])
if rowOK:
clumnOK = all([e != grid[x][j] for x in range(9)])
if clumnOK:
secTopX, secTopY = 3*(i//3), 3*(j//3)
for x in range(secTopX, secTopX + 3):
for y in range(secTopY, secTopY + 3):
if grid[x][y] == e:
return False
return True
return False
def printSudoku(grid):
numrow = 0
for row in grid:
if numrow % 3 == 0 and numrow != 0:
print(' ')
print(row[0:3], ' ', row[3:6], ' ', row[6:9])
numrow += 1
こんな感じですね。これを使って早速解いてみましょう。以下のコードを実行してみてください。
if __name__ == '__main__':
input_data = [[5, 1, 7, 6, 0, 0, 0, 3, 4],
[2, 8, 9, 0, 0, 4, 0, 0, 0],
[3, 4, 6, 2, 0, 5, 0, 9, 0],
[6, 0, 2, 0, 0, 0, 0, 1, 0],
[0, 3, 8, 0, 0, 6, 0, 4, 7],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 9, 0, 0, 0, 0, 0, 7, 8],
[7, 0, 3, 4, 0, 0, 5, 6, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0]]
solveSudoku(input_data)
printSudoku(input_data)
すると以下のような結果が出るはずです。
[5, 1, 7] [6, 9, 8] [2, 3, 4]
[2, 8, 9] [1, 3, 4] [7, 5, 6]
[3, 4, 6] [2, 7, 5] [8, 9, 1]
[6, 7, 2] [8, 4, 9] [3, 1, 5]
[1, 3, 8] [5, 2, 6] [9, 4, 7]
[9, 5, 4] [7, 1, 3] [6, 8, 2]
[4, 9, 5] [3, 6, 2] [1, 7, 8]
[7, 2, 3] [4, 8, 1] [5, 6, 9]
[8, 6, 1] [9, 5, 7] [4, 2, 3]
素晴らしい。一瞬で解けてしまいましたね。自分で解くのがばかばかしくなりますね。
-
前の記事
python~tkinterを用いたオセロ(リバーシ)改良版:CPU対戦付き~ 2020.09.23
-
次の記事
python~幅優先探索とキュー 2020.11.24
コメントを書く