Python实现9x9方格数独求解小工具

﹏ヽ暗。殇╰゛Y 2023-09-29 23:04 20阅读 0赞

为了实现9\*9方格的数独求解工具，我们需要使用Python编写程序。下面是一个简单的代码示例，可以通过命令行交互式输入和输出来实现数独求解。

board = [
        [5, 3, 0, 0, 7, 0, 0, 0, 0],
        [6, 0, 0, 1, 9, 5, 0, 0, 0],
        [0, 9, 8, 0, 0, 0, 0, 6, 0],
        [8, 0, 0, 0, 6, 0, 0, 0, 3],
        [4, 0, 0, 8, 0, 3, 0, 0, 1],
        [7, 0, 0, 0, 2, 0, 0, 0, 6],
        [0, 6, 0, 0, 0, 0, 2, 8, 0],
        [0, 0, 0, 4, 1, 9, 0, 0, 5],
        [0, 0, 0, 0, 8, 0, 0, 7, 9],
    ]
    
    def print_board(board):
        for i in range(len(board)):
            if i % 3 == 0 and i != 0:
                print("- - - - - - - - - - - - - - -")
            for j in range(len(board[0])):
                if j % 3 == 0 and j != 0:
                    print(" | ", end="")
                if j == 8:
                    print(board[i][j])
                else:
                    print(str(board[i][j]) + " ", end="")
    
    def find_empty_square(board):
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == 0:
                    return (i, j)
        return None
    
    def is_valid_move(board, num, pos):
        # Check row
        for i in range(len(board[0])):
            if board[pos[0]][i] == num and pos[1] != i:
                return False
    
        # Check column
        for i in range(len(board)):
            if board[i][pos[1]] == num and pos[0] != i:
                return False
    
        # Check box
        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 board[i][j] == num and (i,j) != pos:
                    return False
    
        return True
    
    def solve_board(board):
        find = find_empty_square(board)
        if not find:
            return True
        else:
            row, col = find
    
        for i in range(1,10):
            if is_valid_move(board, i, (row, col)):
                board[row][col] = i
    
                if solve_board(board):
                    return True
    
                board[row][col] = 0
    
        return False
    
    print_board(board)
    input("Press any key to start solving the puzzle...")
    solve_board(board)
    print("\nSolved Puzzle:\n")
    print_board(board)

上面这个程序中，我们首先定义了一个9x9的数独棋盘，并定义了一些函数用于打印棋盘、查找空白格子、检查数字是否合法以及递归求解整个棋盘。我们还提供了一个用户界面，在用户按下任意键后开始求解数独，并在求解完成后打印出结果。

因为这个程序没有图形界面，所以用户需要在命令行中输入数字来填充数独。如果要增加图形界面，可以考虑使用Python GUI框架，如PyQt或Tkinter，以便用户更方便地进行操作。

以下是一个测试案例，展示了如何使用上述程序来求解一个数独：

board = [
        [5, 3, 0, 0, 7, 0, 0, 0, 0],
        [6, 0, 0, 1, 9, 5, 0, 0, 0],
        [0, 9, 8, 0, 0, 0, 0, 6, 0],
        [8, 0, 0, 0, 6, 0, 0, 0, 3],
        [4, 0, 0, 8, 0, 3, 0, 0, 1],
        [7, 0, 0, 0, 2, 0, 0, 0, 6],
        [0, 6, 0, 0, 0, 0, 2, 8, 0],
        [0, 0, 0, 4, 1, 9, 0, 0, 5],
        [0, 0, 0, 0, 8, 0, 0, 7, 9],
    ]
    
    print("Original Puzzle:\n")
    print_board(board)
    input("Press any key to start solving the puzzle...")
    solve_board(board)
    print("\nSolved Puzzle:\n")
    print_board(board)

运行上述代码后，控制台将输出原始数独和已经求解的数独。下面是输出示例：

Original Puzzle:
    
    5 3 0 | 0 7 0 | 0 0 0
    6 0 0 | 1 9 5 | 0 0 0
    0 9 8 | 0 0 0 | 0 6 0
    - - - - - - - - - - - - - - -
    8 0 0 | 0 6 0 | 0 0 3
    4 0 0 | 8 0 3 | 0 0 1
    7 0 0 | 0 2 0 | 0 0 6
    - - - - - - - - - - - - - - -
    0 6 0 | 0 0 0 | 2 8 0
    0 0 0 | 4 1 9 | 0 0 5
    0 0 0 | 0 8 0 | 0 7 9
    
    Press any key to start solving the puzzle...
    
    Solved Puzzle:
    
    5 3 4 | 6 7 8 | 9 1 2
    6 7 2 | 1 9 5 | 3 4 8
    1 9 8 | 3 4 2 | 5 6 7
    - - - - - - - - - - - - - - -
    8 5 9 | 7 6 1 | 4 2 3
    4 2 6 | 8 5 3 | 7 9 1
    7 1 3 | 9 2 4 | 8 5 6
    - - - - - - - - - - - - - - -
    9 6 1 | 5 3 7 | 2 8 4
    2 8 7 | 4 1 9 | 6 3 5
    3 4 5 | 2 8 6 | 1 7 9

从结果中可以看出，我们的程序能够准确地求解数独。