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]

素晴らしい。一瞬で解けてしまいましたね。自分で解くのがばかばかしくなりますね。