Python如何解数独?

How to solve Sudoku with Python?

我想知道如何在 Python 中使用人工输入和计算机求解解决这个数独游戏。 我有一个人和计算机解决 def。我尝试使用行和列来解决,但它不会每次都在板上打印结果。我尝试使用诸如 'i in range' 之类的东西来做这些。但是当我 运行 程序时,它会工作但不会在每次解决它时打印结果。 谢谢!

import time, sys, random

def print_board(sudoku):
for i in range(9):
    print(sudoku[i][0:3],'|',sudoku[i][3:6],'|',sudoku[i][6:9])
    if i==5 or i==2:
        print('-'*51)
        
if __name__ == '__main__':
 # Don't change the layout of the following sudoku examples
sudoku1 = [
    [' ', '1', '5', '4', '7', ' ', '2', '6', '9'],
    [' ', '4', '2', '3', '5', '6', '7', ' ', '8'],
    [' ', '8', '6', ' ', ' ', ' ', ' ', '3', ' '],
    ['2', ' ', '3', '7', '8', ' ', ' ', ' ', ' '],
    [' ', ' ', '7', ' ', ' ', ' ', ' ', '9', ' '],
    ['4', ' ', ' ', ' ', '6', '1', ' ', ' ', '2'],
    ['6', ' ', ' ', '1', ' ', ' ', ' ', ' ', ' '],
    [' ', ' ', '4', ' ', ' ', ' ', '1', ' ', '7'],
    [' ', ' ', ' ', ' ', '3', '7', '9', '4', ' '],
]
sudoku2 = [
    [' ', ' ', ' ', '3', ' ', ' ', ' ', '7', ' '],
    ['7', '3', '4', ' ', '8', ' ', '1', '6', '2'],
    ['2', ' ', ' ', ' ', ' ', ' ', ' ', '3', '8'],
    ['5', '6', '8', ' ', ' ', '4', ' ', '1', ' '],
    [' ', ' ', '2', '1', ' ', ' ', ' ', ' ', ' '],
    [' ', ' ', '7', '8', ' ', ' ', '2', '5', '4'],
    [' ', '7', ' ', ' ', ' ', '2', '8', '9', ' '],
    [' ', '5', '1', '4', ' ', ' ', '7', '2', '6'],
    ['9', ' ', '6', ' ', ' ', ' ', ' ', '4', '5'],
]
sudoku3 = [
    ['8', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
    [' ', ' ', '3', '6', ' ', ' ', ' ', ' ', ' '],
    [' ', '7', ' ', ' ', '9', ' ', '2', ' ', ' '],
    [' ', '5', ' ', ' ', ' ', '7', ' ', ' ', ' '],
    [' ', ' ', ' ', ' ', '4', '5', '7', ' ', ' '],
    [' ', ' ', ' ', '1', ' ', ' ', ' ', '3', ' '],
    [' ', ' ', '1', ' ', ' ', ' ', ' ', '6', '8'],
    [' ', ' ', '8', '5', ' ', ' ', ' ', '1', ' '],
    [' ', '9', ' ', ' ', ' ', ' ', '4', ' ', ' '],
]
sudoku4 = [
    [' ', '4', '1', ' ', ' ', '8', ' ', ' ', ' '],
    ['3', ' ', '6', '2', '4', '9', ' ', '8', ' '],
    [' ', ' ', ' ', ' ', ' ', ' ', ' ', '7', ' '],
    [' ', ' ', ' ', '4', '7', ' ', '2', '1', ' '],
    ['7', ' ', ' ', '3', ' ', ' ', '4', ' ', '6'],
    [' ', '2', ' ', ' ', ' ', ' ', ' ', '5', '3'],
    [' ', ' ', '7', ' ', '9', ' ', '5', ' ', ' '],
    [' ', ' ', '3', ' ', '2', ' ', ' ', ' ', ' '],
    [' ', '5', '4', ' ', '6', '3', ' ', ' ', ' '],
]
option = 2

if option == 1:
    sudoku = sudoku1
elif option == 2:
    sudoku = sudoku2
elif option == 3:
    sudoku = sudoku3
elif option == 4:
    sudoku = sudoku4
else:
    raise ValueError('Invalid choice!')

# Player Types | Computer or Player depending on the input below!
def Human_play():
   print('The Human Plays.')

def Computer_play():
   print('The Computer Plays')

# Chooses Player Type
Player_Type = ''
while Player_Type != 'Human' or 'Computer':
   Player_Type = input('"Human" or "Computer" solve?: ')
if Player_Type == 'Human' or 'human' or 'HUMAN':
    Human_play()
    print_board(sudoku)
    break
elif Player_Type == 'Computer' or 'computer' or 'COMPUTER':
    Computer_play()
    print_board(sudoku)
    break
else:
    print('Invalid Player Type!\nMake sure you use "Human" or "Computer"')

您可以像智能人一样以编程方式解决它。

拥有一组应用于组(行、列或 3×3)的发现规则,以消除可能性,或 select 值,其中只有一种可能性。

例如,考虑第一个拼图的前三行:

    [' ', '1', '5', '4', '7', ' ', '2', '6', '9'],
    [' ', '4', '2', '3', '5', '6', '7', ' ', '8'],
    [' ', '8', '6', ' ', ' ', ' ', ' ', '3', ' '],

作为一个人,我会意识到在第一行的两个空单元格中只允许 38 但在第一个单元格中不允许 8 因为它已经在左上角 3x3。您只需让您的代码按照以下行执行相同的操作:

  • 从棋盘上所有包含完整范围 123456789 的空单元格开始。您现在已经发现单元格(具有一种可能的值)和未发现的单元格(具有两种或更多可能性)。

  • 对于每个未发现的单元格,一个接一个地应用发现规则。第一行中第一个未发现的单元格已被删除,但 38 已被删除,因为第一行中的所有其他值都决定了这一点。

  • 然后246因为该列被淘汰了(不相关因为该行已经淘汰了它们)。

  • 3x3消除了152486,其中只有8有效果。这意味着该单元格现在 3 并且现在已被发现。

  • 第一行中第二个未发现的单元格现在已被删除,但 8 因为该行(这是剩余的一个值)。


我实际上实现了这样一个野兽,它实际上会这样做(a)。它使用上面给出的相对简单的规则完全解决了简单的数独谜题,但更复杂的问题必须使用前瞻性来找到不可能的情况并将其丢弃。例如,假设您遵循了所有基本发现规则,但仍有未发现的单元格。

只需将具有两种(或最少数量)可能性的空单元格之一设置为特定值,然后继续。您最终会发现:

  • 你最终在一个组中得到了一个重复的值(在这种情况下,你返回并将原始单元格设置为另一种可能性)。

  • 您成功完成了拼图,说明您最初的选择是正确的。

  • 你遇到同样的情况(每个空单元格中至少有两种可能性)。

在最后一种情况下,您只需再次执行相同的操作即可。您必须在搜索中处理多个分支 space,但使用递归这很容易。


发现策略基本上是自成体系的,例如:

  • 如果一个组已经有一个特定的(发现的)值,则可以从该组中所有其他未发现的单元格中删除该值。

  • 如果相关单元格的值在组中的其他任何地方都找不到,则一定是该值。

  • 如果一个组有 N 个单元格只允许相同的 N 值,这些值可以在其他地方消除,一个例子是一行有三个空单元格的可能性 1212123。由于前两个必须是 12,因此第三个 必须 3,即使您不知道 是哪个其他的 12


将这两条规则逐个应用于每个单元格,并根据需要重复多次,就完全解决了第一个难题:

sudoku1 = [
    ['3', '1', '5', '4', '7', '8', '2',  '6', '9'],
    ['9', '4', '2', '3', '5', '6', '7',  '1', '8'],
    ['7', '8', '6', '2', '1', '9', '4',  '3', '5'],
    ['2', '9', '3', '7', '8', '4', '6',  '5', '1'],
    ['1', '6', '7', '5', '2', '3', '8',  '9', '4'],
    ['4', '5', '8', '9', '6', '1', '3 ', '7', '2'],
    ['6', '7', '9', '1', '4', '2', '5',  '8', '3'],
    ['8', '3', '4', '6', '9', '5', '1',  '2', '7'],
    ['5', '2', '1', '8', '3', '7', '9',  '4', '6'],
]

这是您可以开始的代码,它只实现了上面显示的第一个消除规则:

import time

puzzle = [
    [' ', '1', '5', '4', '7', ' ', '2', '6', '9'],
    [' ', '4', '2', '3', '5', '6', '7', ' ', '8'],
    [' ', '8', '6', ' ', ' ', ' ', ' ', '3', ' '],
    ['2', ' ', '3', '7', '8', ' ', ' ', ' ', ' '],
    [' ', ' ', '7', ' ', ' ', ' ', ' ', '9', ' '],
    ['4', ' ', ' ', ' ', '6', '1', ' ', ' ', '2'],
    ['6', ' ', ' ', '1', ' ', ' ', ' ', ' ', ' '],
    [' ', ' ', '4', ' ', ' ', ' ', '1', ' ', '7'],
    [' ', ' ', ' ', ' ', '3', '7', '9', '4', ' '],
]

# Expand empty cells to full range of possible values.

for row in range(len(puzzle)):
    for col in range(len(puzzle[row])):
        if puzzle[row][col] == " ":
            puzzle[row][col] = "123456789"

# Exit if everything solved.

while not all([(len(cell) == 1) for row in puzzle for cell in row]):
    for row in range(len(puzzle)):
        for col in range(len(puzzle[row])):
            print(f" {puzzle[row][col]:10} ", end="")
        print()
    print("Press ENTER: ", end="")
    input()

    # Allow for full cycle with no change to break, this means
    # current rule set is not enough.

    changed = False

    # Process each undiscovered cell.

    for row in range(len(puzzle)):
        for col in range(len(puzzle[row])):
            if len(puzzle[row][col]) != 1:
                # Eliminate all values in row.

                for col2 in range(len(puzzle[row])):
                    if col2 != col and len(puzzle[row][col2]) == 1:
                        if puzzle[row][col2] in puzzle[row][col]:
                            changed = True
                            puzzle[row][col] = puzzle[row][col].replace(puzzle[row][col2], "")

                # Eliminate all values in column.

                for row2 in range(len(puzzle)):
                    if row2 != row and len(puzzle[row2][col]) == 1:
                        if puzzle[row2][col] in puzzle[row][col]:
                            changed = True
                            puzzle[row][col] = puzzle[row][col].replace(puzzle[row2][col], "")

                # Eliminate all values in 3x3.

                base_row = row - row % 3
                base_col = col - col % 3

                for row2 in range(base_row, base_row + 3):
                    for col2 in range(base_col, base_col + 3):
                        if (row2 != row or col2 != col) and len(puzzle[row2][col2]) == 1:
                            if puzzle[row2][col2] in puzzle[row][col]:
                                changed = True
                                puzzle[row][col] = puzzle[row][col].replace(puzzle[row2][col2], "")

    if not changed:
        break

这足以让它进入可以看到第二条规则开始生效的状态(尽管出于格式化目的我已经稍微修改了输出):

1-9   1     5     4     7     1-9   2     6     9
1-9   4     2     3     5     6     7     1-9   8
1-9   8     6     1-9   1-9   1-9   1-9   3     1-9
2     1-9   3     7     8     1-9   1-9   1-9   1-9
1-9   1-9   7     1-9   1-9   1-9   1-9   9     1-9
4     1-9   1-9   1-9   6     1     1-9   1-9   2
6     1-9   1-9   1     1-9   1-9   1-9   1-9   1-9
1-9   1-9   4     1-9   1-9   1-9   1     1-9   7
1-9   1-9   1-9   1-9   3     7     9     4     1-9
Press ENTER:

3     1       5    4       7     8      2      6    9
9     4       2    3       5     6      7      1    8
7     8       6    29      129   29     45     3    45
2     569     3    7       8     459    456    5    146
158   56      7    25      24    2345   3468   9    1346
4     59      89   59      6     1      38     78   2
6     23579   89   1       249   2459   358    28   35
58    2359    4    25689   29    259    1      28   7
158   25      18   2568    3     7      9      4    56
Press ENTER:

3     1       5    4       7       8      2      6   9
9     4       2    3       5       6      7      1   8
7     8       6    29      129     29     45     3   45
2     69      3    7       8       49     46     5   146
158   56      7    25      24      2345   3468   9   1346
4     59      89   59      6       1      38    78   2
6     23579   89   1       249     2459   358   28   35
58    2359    4    25689   29      259    1     28   7
158   25      18   2568    3       7      9     4    56
Press ENTER:

执行其他规则即可,例如:

  • 第三行设置了29, 129, 29,中间的必须是1
  • 第六行设置了59, 89, 59,中间的必须是8
  • 第二列只有第七行有一个7,所以一定是7.
  • 设置了 69, 56, 59 的第二列,这会消除列中其他单元格中的所有数字。

(a) 主要作为编码练习。我更喜欢自己解决它们。无论如何,目前让我老化的大脑保持功能的是 Kakuro,你应该 that 试试 :-)