如何在更短的时间内更高效地生成 Python 的数独
How can I generate Sudoku in Python in less time and more efficiently
我的目标是用 1 到 N^2 范围内的正整数填充 N^2*N^2 的网格，满足以下规则：
1 到 N^2 范围内的每个整数在每列、每行和第 N * N 部分中只出现一次。
为了解决这个问题，我尝试制作一个 3x3 数独代码，它可以生成一个包含我们想要填充的单元格的数独，但是每当我尝试生成包含所有单元格的数独时，我的电脑都无法生成handle it，哪里可以改进这种算法。
import random
def MakeSudoku():
Grid = [[0 for x in range(9)] for y in range(9)]
for i in range(9):
for j in range(9):
Grid[i][j] = 0
# The range here is the amount
# of numbers in the grid
for i in range(5):
#choose random numbers
row = random.randrange(9)
col = random.randrange(9)
num = random.randrange(1,10)
while(not CheckValid(Grid,row,col,num) or Grid[row][col] != 0): #if taken or not valid reroll
row = random.randrange(9)
col = random.randrange(9)
num = random.randrange(1,10)
Grid[row][col]= num;
Printgrid(Grid)
def Printgrid(Grid):
TableTB = "|--------------------------------|"
TableMD = "|----------+----------+----------|"
print(TableTB)
for x in range(9):
for y in range(9):
if ((x == 3 or x == 6) and y == 0):
print(TableMD)
if (y == 0 or y == 3 or y== 6):
print("|", end=" ")
print(" " + str(Grid[x][y]), end=" ")
if (y == 8):
print("|")
print(TableTB)
# |-----------------------------|
# | 0 0 0 | 0 0 0 | 0 0 0 |
# | 0 0 0 | 0 0 0 | 0 0 0 |
# | 0 0 0 | 0 0 0 | 0 0 0 |
# |---------+---------+---------|
# | 0 0 0 | 0 0 0 | 0 0 0 |
# | 0 0 0 | 0 0 0 | 0 0 0 |
# | 0 0 0 | 0 0 0 | 0 0 0 |
# |---------+---------+---------|
# | 0 0 0 | 0 0 0 | 0 0 0 |
# | 0 0 0 | 0 0 0 | 0 0 0 |
# | 0 0 0 | 0 0 0 | 0 0 0 |
# |-----------------------------|
def CheckValid(Grid,row,col,num):
#check if in row
valid = True
#check row and column
for x in range(9):
if (Grid[x][col] == num):
valid = False
for y in range(9):
if (Grid[row][y] == num):
valid = False
rowsection = row // 3
colsection = col // 3
for x in range(3):
for y in range(3):
#check if section is valid
if(Grid[rowsection*3 + x][colsection*3 + y] == num):
valid = False
return valid
MakeSudoku()
部分问题是 or Grid[row][col]!=0 当您有一个有效的网格时创建一个无限循环。
但总的来说，您搜索的 space 太大了。每个有效的 9x9 数独在每一行中都有一个数字 1-9，对于您使用 属性 生成的每个网格，您会发现 1.8e27 而不是。这只是我的电脑马铃薯可以处理的。
我所知道的大多数策略都退回到广度或深度优先搜索某种风格（从 empty/partial 解决方案开始，添加一点，如果它返回一个或多个步骤导致网格破损）。我也会在这里做同样的事情。
需要注意的一些要点包括：
我们按顺序排列每个数字（1s，然后 2s，...）。大多数这样做的方法都以有效的数独结束，而尤其是对于较大的数独，一次构建一个正方形通常以无效的数独结束。
对于每个数字，我们按顺序处理行。这本身并不是强制性的，但对于我们设置为跟踪数独冲突的 hacky 数据结构（变量 idx），它允许我们在回溯潜在解决方案的隐式图时完全避免清理成本。
用 M+2 的值初始化网格只是清理了一点点逻辑。我认为 None 更具自我描述性，但是你需要用 (not el or el >= x).
之类的东西来实际处理 None 的情况，而不是 el>=x
对于大于 36x36 左右的任何东西，您将需要某种更高级的方法。高达 45x45 左右，您可能只需使用 cython 或类似工具来获得编译速度，但除此之外，您将需要更好的算法。 IIRC，数独的某些方面是NP难的；我不确定这是否只是事情的 solving/uniqueness 方面，或者生成完整的电路板是否也被证明是困难的。不过，我听说人们很容易生成 100x100 的电路板，所以无论如何我怀疑存在比我发布的更好的解决方案。
from random import sample, shuffle
from collections import deque
def rand_grid(w, h):
M = w*h
grid = [[M+2]*M for _ in range(M)]
# A stack of the next cells we'll try to fill in.
# This is sorted by the cell value, then by the row index.
stack = deque((0, k, 1) for k in sample(range(M), M))
# We want a cheap/easy way to check if we're about to violate a sudoku
# rule for a given placement, and we need it to remain cheap upon
# backtracking. For any cell-value x, idx[x][i]==j means that
# grid[i][j]==x. Since our stack is processed in row-order we can
# ignore the tail of any sub-list and never have to clean up after
# ourselves
idx = [[None]*M for _ in range(1+M)]
while True:
i, j, x = stack.pop()
idx[x][i] = j
# We've successfully filled the last row in the grid for a given
# cell-value x. Clean up and either move to x+1 or return the
# completely filled grid.
if i==M-1:
# If we go forward/backward past this cell-value x we might
# fill the grid with extra xs. We could handle that by treating
# idx as the source of truth till we construct the final grid,
# but we don't backtrack across cell-value changes often and
# do need to enumerate empty cells in a given row often, so it's
# cheaper overall to clean up the grid just a little right now.
# Better data structures probably exist.
for a,row in enumerate(grid):
for b,el in enumerate(row):
if el==x:
row[b] = M+2
# Since we've finished placing cell-value x everywhere, update the
# grid to reflect that fact
for a,b in enumerate(idx[x]):
grid[a][b] = x
# The cell-value we just placed was the last one available. Hooray!
if x==M:
return grid
# The next place we'll try to fill is row 0 with cell-value x+1
else:
i, x = 0, x+1
# The next place we'll try to fill is row i+1 with cell-value x
else:
i += 1
# At this point i and x represent the row/value we're about to attempt to
# fill. We construct a set s of the columns which have been filled with x,
# and a set t of tuples representing the upper-left corner of each box which
# has been filled with x in order to cheaply check for column/box conflicts.
s = set(idx[x][:i])
t = {(w*(a//w), h*(b//h)) for a,b in enumerate(idx[x][:i])}
# Valid candidates don't conflict with existing smaller digits or with the
# same digit in any already placed column/box.
candidates = [(i, k, x) for k,el in enumerate(grid[i])
if el>=x and k not in s and (w*(i//w), h*(k//h)) not in t]
shuffle(candidates)
stack.extend(candidates)
# rand_grid(3, 3) creates a 9x9 Sudoku
# rand_grid(4, 5) creates a 20x20 Sudoku with 4-wide by 5-tall boxes
# rand_grid(n, n) is the MakeSudoku(n) function you asked for
我的目标是用 1 到 N^2 范围内的正整数填充 N^2*N^2 的网格，满足以下规则：
1 到 N^2 范围内的每个整数在每列、每行和第 N * N 部分中只出现一次。
为了解决这个问题，我尝试制作一个 3x3 数独代码，它可以生成一个包含我们想要填充的单元格的数独，但是每当我尝试生成包含所有单元格的数独时，我的电脑都无法生成handle it，哪里可以改进这种算法。
import random
def MakeSudoku():
Grid = [[0 for x in range(9)] for y in range(9)]
for i in range(9):
for j in range(9):
Grid[i][j] = 0
# The range here is the amount
# of numbers in the grid
for i in range(5):
#choose random numbers
row = random.randrange(9)
col = random.randrange(9)
num = random.randrange(1,10)
while(not CheckValid(Grid,row,col,num) or Grid[row][col] != 0): #if taken or not valid reroll
row = random.randrange(9)
col = random.randrange(9)
num = random.randrange(1,10)
Grid[row][col]= num;
Printgrid(Grid)
def Printgrid(Grid):
TableTB = "|--------------------------------|"
TableMD = "|----------+----------+----------|"
print(TableTB)
for x in range(9):
for y in range(9):
if ((x == 3 or x == 6) and y == 0):
print(TableMD)
if (y == 0 or y == 3 or y== 6):
print("|", end=" ")
print(" " + str(Grid[x][y]), end=" ")
if (y == 8):
print("|")
print(TableTB)
# |-----------------------------|
# | 0 0 0 | 0 0 0 | 0 0 0 |
# | 0 0 0 | 0 0 0 | 0 0 0 |
# | 0 0 0 | 0 0 0 | 0 0 0 |
# |---------+---------+---------|
# | 0 0 0 | 0 0 0 | 0 0 0 |
# | 0 0 0 | 0 0 0 | 0 0 0 |
# | 0 0 0 | 0 0 0 | 0 0 0 |
# |---------+---------+---------|
# | 0 0 0 | 0 0 0 | 0 0 0 |
# | 0 0 0 | 0 0 0 | 0 0 0 |
# | 0 0 0 | 0 0 0 | 0 0 0 |
# |-----------------------------|
def CheckValid(Grid,row,col,num):
#check if in row
valid = True
#check row and column
for x in range(9):
if (Grid[x][col] == num):
valid = False
for y in range(9):
if (Grid[row][y] == num):
valid = False
rowsection = row // 3
colsection = col // 3
for x in range(3):
for y in range(3):
#check if section is valid
if(Grid[rowsection*3 + x][colsection*3 + y] == num):
valid = False
return valid
MakeSudoku()
部分问题是 or Grid[row][col]!=0 当您有一个有效的网格时创建一个无限循环。
但总的来说，您搜索的 space 太大了。每个有效的 9x9 数独在每一行中都有一个数字 1-9，对于您使用 属性 生成的每个网格，您会发现 1.8e27 而不是。这只是我的电脑马铃薯可以处理的。
我所知道的大多数策略都退回到广度或深度优先搜索某种风格（从 empty/partial 解决方案开始，添加一点，如果它返回一个或多个步骤导致网格破损）。我也会在这里做同样的事情。
需要注意的一些要点包括：
我们按顺序排列每个数字（1s，然后 2s，...）。大多数这样做的方法都以有效的数独结束，而尤其是对于较大的数独，一次构建一个正方形通常以无效的数独结束。
对于每个数字，我们按顺序处理行。这本身并不是强制性的，但对于我们设置为跟踪数独冲突的 hacky 数据结构（变量
idx），它允许我们在回溯潜在解决方案的隐式图时完全避免清理成本。用
之类的东西来实际处理M+2的值初始化网格只是清理了一点点逻辑。我认为None更具自我描述性，但是你需要用(not el or el >= x).None的情况，而不是el>=x对于大于 36x36 左右的任何东西，您将需要某种更高级的方法。高达 45x45 左右，您可能只需使用 cython 或类似工具来获得编译速度，但除此之外，您将需要更好的算法。 IIRC，数独的某些方面是NP难的；我不确定这是否只是事情的 solving/uniqueness 方面，或者生成完整的电路板是否也被证明是困难的。不过，我听说人们很容易生成 100x100 的电路板，所以无论如何我怀疑存在比我发布的更好的解决方案。
from random import sample, shuffle
from collections import deque
def rand_grid(w, h):
M = w*h
grid = [[M+2]*M for _ in range(M)]
# A stack of the next cells we'll try to fill in.
# This is sorted by the cell value, then by the row index.
stack = deque((0, k, 1) for k in sample(range(M), M))
# We want a cheap/easy way to check if we're about to violate a sudoku
# rule for a given placement, and we need it to remain cheap upon
# backtracking. For any cell-value x, idx[x][i]==j means that
# grid[i][j]==x. Since our stack is processed in row-order we can
# ignore the tail of any sub-list and never have to clean up after
# ourselves
idx = [[None]*M for _ in range(1+M)]
while True:
i, j, x = stack.pop()
idx[x][i] = j
# We've successfully filled the last row in the grid for a given
# cell-value x. Clean up and either move to x+1 or return the
# completely filled grid.
if i==M-1:
# If we go forward/backward past this cell-value x we might
# fill the grid with extra xs. We could handle that by treating
# idx as the source of truth till we construct the final grid,
# but we don't backtrack across cell-value changes often and
# do need to enumerate empty cells in a given row often, so it's
# cheaper overall to clean up the grid just a little right now.
# Better data structures probably exist.
for a,row in enumerate(grid):
for b,el in enumerate(row):
if el==x:
row[b] = M+2
# Since we've finished placing cell-value x everywhere, update the
# grid to reflect that fact
for a,b in enumerate(idx[x]):
grid[a][b] = x
# The cell-value we just placed was the last one available. Hooray!
if x==M:
return grid
# The next place we'll try to fill is row 0 with cell-value x+1
else:
i, x = 0, x+1
# The next place we'll try to fill is row i+1 with cell-value x
else:
i += 1
# At this point i and x represent the row/value we're about to attempt to
# fill. We construct a set s of the columns which have been filled with x,
# and a set t of tuples representing the upper-left corner of each box which
# has been filled with x in order to cheaply check for column/box conflicts.
s = set(idx[x][:i])
t = {(w*(a//w), h*(b//h)) for a,b in enumerate(idx[x][:i])}
# Valid candidates don't conflict with existing smaller digits or with the
# same digit in any already placed column/box.
candidates = [(i, k, x) for k,el in enumerate(grid[i])
if el>=x and k not in s and (w*(i//w), h*(k//h)) not in t]
shuffle(candidates)
stack.extend(candidates)
# rand_grid(3, 3) creates a 9x9 Sudoku
# rand_grid(4, 5) creates a 20x20 Sudoku with 4-wide by 5-tall boxes
# rand_grid(n, n) is the MakeSudoku(n) function you asked for