Python 数独程序未生成结果

Question

我一直在尝试编写一个生成数独谜题的程序，但我的程序似乎无法运行。由于我的 4X4 能够生成结果，因此该程序似乎花费了运行太长的时间。插入的 2 个打印语句确实在打印“1”和“2”。

import random

board = []
for nine in range(9):
    board.append([0, 0, 0, 0, 0, 0, 0, 0, 0])

def sudoku():
    for index in range(81):
        row = index // 9
        col = index % 9
        while board[row][col] == 0:
            chosen = random.randint(1, 9)
            print(1)
            if chosen not in board[row]:
                if check_col(col, chosen) != 1:
                    if row < 3:
                        if col < 3:
                            if check_square(0, 0, chosen) != 1:
                                board[row][col] = chosen
                        elif col < 6:
                            if check_square(0, 3, chosen) != 1:
                                board[row][col] = chosen
                        else:
                            if check_square(0, 6, chosen) != 1:
                                board[row][col] = chosen
                                print(2)
                    elif row < 6:
                        if col < 3:
                            if check_square(3, 0, chosen) != 1:
                                board[row][col] = chosen
                        elif col < 6:
                            if check_square(3, 3, chosen) != 1:
                                board[row][col] = chosen
                        else:
                            if check_square(3, 6, chosen) != 1:
                                board[row][col] = chosen
                    else:
                        if col < 3:
                            if check_square(6, 0, chosen) != 1:
                                board[row][col] = chosen
                        elif col < 6:
                            if check_square(6, 3, chosen) != 1:
                                board[row][col] = chosen
                        else:
                            if check_square(6, 6, chosen) != 1:
                                board[row][col] = chosen


def check_col(col, chosen):
    check = 0
    for c_row in range(9):
        if chosen == board[c_row][col]:
            check = 1
    return check

def check_square(starting_row, starting_col, chosen):
    check = 0
    for c_add in range(3):
        if chosen in board[starting_row + c_add][starting_col:starting_col + 3]:
            check = 1
    return check

sudoku()
for printing in range(9):
    print(board[printing])

Answer 1

您可以生成一个随机的数独解决方案板，其中填写了所有数字，然后删除其中一些以创建拼图。这将确保拼图始终有解决方案。确保它只有一个解决方案更具挑战性（提示：您必须为 9x9 数独保留至少 17 个数字）

下面的算法将立即生成一个 NxN 的随机数独答案板，N < 1000。

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))

# produce board using randomized baseline pattern
board = [ [nums[pattern(r,c)] for c in cols] for r in rows ]

for line in board: print(line)

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

然后您可以从数独解决方案中删除一些数字来创建拼图：

squares = side*side
empties = squares * 3//4
for p in sample(range(squares),empties):
    board[p//side][p%side] = 0

numSize = len(str(side))
for line in board: print("["+"  ".join(f"{n or '.':{numSize}}" for n in line)+"]")

[6  .  .  .  .  3  .  .  1]
[.  9  .  .  .  .  .  .  3]
[4  .  3  .  .  .  6  .  .]
[.  .  .  5  9  .  2  .  6]
[.  .  .  .  .  .  .  .  .]
[.  .  7  .  .  .  .  .  4]
[.  .  .  .  .  .  1  7  .]
[.  .  2  .  .  8  .  .  .]
[.  .  8  .  .  .  .  4  2]

对于 4x4 到 36x36 的拼图，您可以像这样打印出更好的棋盘：

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)])

╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗
║ 6 │   │   ║   │   │ 3 ║   │   │ 1 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │ 9 │   ║   │   │   ║   │   │ 3 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 4 │   │ 3 ║   │   │   ║ 6 │   │   ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║   │   │   ║ 5 │ 9 │   ║ 2 │   │ 6 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │   ║   │   │   ║   │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │ 7 ║   │   │   ║   │   │ 4 ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║   │   │   ║   │   │   ║ 1 │ 7 │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │ 2 ║   │   │ 8 ║   │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │ 8 ║   │   │   ║   │ 4 │ 2 ║
╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝

Python 数独程序未生成结果

Python Sudoku program not generating results

python

sudoku