python~数独、ナンプレを解く
初めに
こんにちは、Keymaleです。今回は数独をpythonで解いてみたいと思います。
数独解法
とりあえず以下に数独を解くコードを載せます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
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 |
こんな感じですね。これを使って早速解いてみましょう。以下のコードを実行してみてください。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
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
-
次の記事
記事がありません