Python 數獨產生題目、自動解題程式教學與範例

# 產生數獨題目
def generate_board(base = 3):
    side = base*base

    # pattern for a baseline valid solution
    def pattern(r,c): return (base*(r%base)+r//base+c)%side

    # randomize rows, columns and numbers (of valid base pattern)
    from random import sample
    def shuffle(s): return sample(s,len(s))
    rBase = range(base)
    rows  = [ g*base + r for g in shuffle(rBase) for r in shuffle(rBase) ]
    cols  = [ g*base + c for g in shuffle(rBase) for c in shuffle(rBase) ]
    nums  = shuffle(range(1,base*base+1))

    # 隨機產生的數獨數字盤
    board = [ [nums[pattern(r,c)] for c in cols] for r in rows ]

    # 移除部分數字，產生數獨題目
    squares = side*side
    empties = squares * 3//4
    for p in sample(range(squares),empties):
        board[p//side][p%side] = 0

    return board

# 產生數獨題目
board = generate_board()

# 手動指定數獨題目
board = [[8, 0, 0, 0, 0, 5, 4, 3, 0],
         [0, 0, 0, 0, 0, 8, 0, 0, 0],
         [5, 0, 7, 0, 4, 0, 9, 0, 0],
         [0, 6, 0, 0, 7, 0, 0, 4, 0],
         [0, 0, 0, 0, 6, 0, 7, 1, 0],
         [0, 0, 0, 0, 0, 0, 0, 0, 0],
         [6, 0, 0, 9, 0, 7, 0, 0, 0],
         [0, 0, 0, 0, 3, 0, 0, 0, 0],
         [0, 0, 9, 0, 0, 0, 3, 0, 0]]

# 顯示簡單版數獨數字盤
def print_board(bo):
    for i in range(len(bo)):
        if i % 3 == 0 and i != 0:
            print("------+-------+------")

        for j in range(len(bo[0])):
            if j % 3 == 0 and j != 0:
                print("| ", end="")

            if j == 8:
                print(bo[i][j])
            else:
                print(str(bo[i][j]) + " ", end="")

# 顯示豪華版數獨數字盤
def print_board2(board, base = 3):
    side = base*base
    def expandLine(line):
        return line[0]+line[5:9].join([line[1:5]*(base-1)]*base)+line[9:13]
    line0  = expandLine("╔═══╤═══╦═══╗")
    line1  = expandLine("║ . │ . ║ . ║")
    line2  = expandLine("╟───┼───╫───╢")
    line3  = expandLine("╠═══╪═══╬═══╣")
    line4  = expandLine("╚═══╧═══╩═══╝")

    symbol = " 1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    nums   = [ [""]+[symbol[n] for n in row] for row in board ]
    print(line0)
    for r in range(1,side+1):
        print( "".join(n+s for n,s in zip(nums[r-1],line1.split("."))) )
        print([line2,line3,line4][(r%side==0)+(r%base==0)])

# 顯示簡單版數獨數字盤
print_board(board)

# 顯示豪華版數獨數字盤
print_board2(board)

# 自動解題
def solve(bo):
    found = find_empty(bo)
    if not found:
        return True
    else:
        row, col = found

    for i in range(1, 10):
        if valid(bo, i, (row, col)):
            bo[row][col] = i

            if solve(bo):
                return True

            bo[row][col] = 0

    return False

# 檢查指定位置的數字是否合理
def valid(bo, num, pos):
    # 檢查同一列（Row）內是否重複
    for i in range(len(bo[0])):
        if bo[pos[0]][i] == num and pos[1] != i:
            return False

    # 檢查行（Column）內是否重複
    for i in range(len(bo)):
        if bo[i][pos[1]] == num and pos[0] != i:
            return False

    # 檢查小方格內是否重複
    box_x = pos[1] // 3
    box_y = pos[0] // 3
    for i in range(box_y*3, box_y*3 + 3):
        for j in range(box_x * 3, box_x*3 + 3):
            if bo[i][j] == num and (i,j) != pos:
                return False

    return True

# 尋找一個尚未解出的位置
def find_empty(bo):
    for i in range(len(bo)):
        for j in range(len(bo[0])):
            if bo[i][j] == 0:
                # 傳回位置 (row, column)
                return (i, j)

    return None

# 自動解題
solve(board)

# 輸出數獨答案數字盤
print_board(board)