目标是在 Python 中创建一个 9x9 数独矩阵。
所以我走到了这一步。但我似乎无法让程序使内部的临时箱正确。
def sudoku(size):
import random as rn
mydict = {}
n = 0
while len(mydict) < 9:
n += 1
x = range(1, size+1)
testlist = rn.sample(x, len(x))
isgood = True
for dictid,savedlist in mydict.items():
if isgood == False:
break
for v in savedlist:
if testlist[savedlist.index(v)] == v:
isgood = False
break
if isgood == True:
#print 'success', testlist
mydict[len(mydict)] = testlist
return mydict, n
return_dict, total_tries = sudoku(9)
for n,v in return_dict.items():
print n,v
print 'in',total_tries,'tries'
Ala*_* T. 18
您可以生成一个随机数独解决方案板，其中填充了所有数字，然后删除其中一些以创建拼图。这将确保谜题始终有解决方案。确保它只有一个解决方案更具挑战性（提示：您必须为 9x9 数独留下至少 17 个数字）
下面的算法将立即为 N < 1000 生成 NxN 随机数独解决方案板。
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 ?
?????????????????????????????????????
[编辑]
以下是有关洗牌过程的一些附加信息......
洗牌行分为 3 行一组。可以整体交换组，但我们不能在不破坏块完整性的情况下跨组交换行。（同样的推理适用于列）
例如：
0 [6, 2, 5, 8, 4, 3, 7, 9, 1] \ -|
1 [7, 9, 1, 2, 6, 5, 4, 8, 3] | group 0 -| -| r in shuffle(rBase)
2 [4, 8, 3, 9, 7, 1, 6, 2, 5] / | -|
|
3 [8, 1, 4, 5, 9, 7, 2, 3, 6] \ | -|
4 [2, 3, 6, 1, 8, 4, 9, 5, 7] | group 1 -| * -| r in shuffle(rBase)
5 [9, 5, 7, 3, 2, 6, 8, 1, 4] / | -|
|
6 [5, 6, 9, 4, 3, 2, 1, 7, 8] \ | -|
7 [3, 4, 2, 7, 1, 8, 5, 6, 9] | group 2 -| -| r in shuffle(rBase)
8 [1, 7, 8, 6, 5, 9, 3, 4, 2] / -|
* for g in shuffle(rBase)
我们可以通过同时移动它们的所有 3 行来交换组 0,1,2：
3 [8, 1, 4, 5, 9, 7, 2, 3, 6] \ | -|
4 [2, 3, 6, 1, 8, 4, 9, 5, 7] | group 1 -| -| r in shuffle(rBase)
5 [9, 5, 7, 3, 2, 6, 8, 1, 4] / | -|
|
6 [5, 6, 9, 4, 3, 2, 1, 7, 8] \ | -|
7 [3, 4, 2, 7, 1, 8, 5, 6, 9] | group 2 -| * -| r in shuffle(rBase)
8 [1, 7, 8, 6, 5, 9, 3, 4, 2] / -|
|
0 [6, 2, 5, 8, 4, 3, 7, 9, 1] \ | -|
1 [7, 9, 1, 2, 6, 5, 4, 8, 3] | group 0 -| -| r in shuffle(rBase)
2 [4, 8, 3, 9, 7, 1, 6, 2, 5] / | -|
* for g in shuffle(rBase)
我们可以在一组的 3 行之间交换（例如 3,4,5）......
0 [6, 2, 5, 8, 4, 3, 7, 9, 1] \ -|
1 [7, 9, 1, 2, 6, 5, 4, 8, 3] | group 0 -| -| r in shuffle(rBase)
2 [4, 8, 3, 9, 7, 1, 6, 2, 5] / | -|
|
5 [9, 5, 7, 3, 2, 6, 8, 1, 4] \ | -|
4 [2, 3, 6, 1, 8, 4, 9, 5, 7] | group 1 -| * -| r in shuffle(rBase)
3 [8, 1, 4, 5, 9, 7, 2, 3, 6] / | -|
|
6 [5, 6, 9, 4, 3, 2, 1, 7, 8] \ | -|
7 [3, 4, 2, 7, 1, 8, 5, 6, 9] | group 2 -| -| r in shuffle(rBase)
8 [1, 7, 8, 6, 5, 9, 3, 4, 2] / -|
* for g in shuffle(rBase)
我们不能跨组交换行（例如 1 <--> 3）：
0 [6, 2, 5, 8, 4, 3, 7, 9, 1] \ -|
3 [8, 1, 4, 5, 9, 7, 2, 3, 6] | group 0 -| -| r in shuffle(rBase)
2 [4, 8, 3, 9, 7, 1, 6, 2, 5] / | -|
|
1 [7, 9, 1, 2, 6, 5, 4, 8, 3] \ | -|
4 [2, 3, 6, 1, 8, 4, 9, 5, 7] | group 1 -| * -| r in shuffle(rBase)
5 [9, 5, 7, 3, 2, 6, 8, 1, 4] / | -|
|
6 [5, 6, 9, 4, 3, 2, 1, 7, 8] \ | -|
7 [3, 4, 2, 7, 1, 8, 5, 6, 9] | group 2 -| -| r in shuffle(rBase)
8 [1, 7, 8, 6, 5, 9, 3, 4, 2] / -|
* for g in shuffle(rBase)
查看左上块中的重复 8，下方的重复 7，等等。
单解谜题
为了生成只有一个解决方案的数独谜题，您需要一个求解器功能，它可以告诉您是否有多个解决方案。我建议的策略是从删除 75%（或更多）的数字开始，然后检查是否只有一个解决方案。如果有多个解决方案，请放回一个数字并再次检查。您可以在随机位置放回一个数字或选择解决方案不同的位置（这将更快地收敛到单个解决方案难题）
首先编写一个求解器，它将生成它找到的所有解决方案（理想情况下作为生成器，因为我们只需要前 2 个）。这是一个简单的：
def shortSudokuSolve(board):
size = len(board)
block = int(size**0.5)
board = [n for row in board for n in row ]
span = { (n,p): { (g,n) for g in (n>0)*[p//size, size+p%size, 2*size+p%size//block+p//size//block*block] }
for p in range(size*size) for n in range(size+1) }
empties = [i for i,n in enumerate(board) if n==0 ]
used = set().union(*(span[n,p] for p,n in enumerate(board) if n))
empty = 0
while empty>=0 and empty<len(empties):
pos = empties[empty]
used -= span[board[pos],pos]
board[pos] = next((n for n in range(board[pos]+1,size+1) if not span[n,pos]&used),0)
used |= span[board[pos],pos]
empty += 1 if board[pos] else -1
if empty == len(empties):
solution = [board[r:r+size] for r in range(0,size*size,size)]
yield solution
empty -= 1
从包含solution所有数字的变量和board包含已清除 3/4 数字的谜题的变量开始，您可以将数字添加回棋盘，直到只有一种方法可以解决它：
solution=[[9, 5, 3, 1, 6, 7, 4, 2, 8],
[4, 2, 8, 3, 5, 9, 7, 6, 1],
[7, 6, 1, 8, 2, 4, 9, 5, 3],
[5, 8, 4, 9, 3, 6, 2, 1, 7],
[6, 3, 9, 7, 1, 2, 5, 8, 4],
[2, 1, 7, 4, 8, 5, 6, 3, 9],
[3, 4, 5, 6, 9, 1, 8, 7, 2],
[8, 7, 2, 5, 4, 3, 1, 9, 6],
[1, 9, 6, 2, 7, 8, 3, 4, 5]]
board=[ [0, 0, 0, 0, 0, 0, 0, 0, 8],
[0, 2, 0, 0, 5, 0, 7, 6, 0],
[0, 6, 0, 0, 0, 0, 0, 0, 3],
[5, 0, 0, 0, 0, 0, 2, 0, 7],
[0, 3, 0, 0, 1, 0, 0, 0, 0],
[2, 0, 0, 4, 0, 0, 0, 3, 0],
[0, 0, 0, 6, 0, 0, 0, 0, 0],
[8, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 2, 7, 0, 0, 4, 0]]
import random
from itertools import islice
while True:
solved = [*islice(shortSudokuSolve(board),2)]
if len(solved)==1:break
diffPos = [(r,c) for r in range(9) for c in range(9)
if solved[0][r][c] != solved[1][r][c] ]
r,c = random.choice(diffPos)
board[r][c] = solution[r][c]
输出：
?????????????????????????????????????
? ? ? ? ? ? 7 ? ? ? 8 ?
?????????????????????????????????????
? ? 2 ? ? ? 5 ? ? 7 ? 6 ? ?
?????????????????????????????????????
? ? 6 ? ? 8 ? ? 4 ? ? ? 3 ?
?????????????????????????????????????
? 5 ? ? ? ? ? ? 2 ? ? 7 ?
?????????????????????????????????????
? ? 3 ? ? ? 1 ? ? ? ? ?
?????????????????????????????????????
? 2 ? ? ? 4 ? ? ? ? 3 ? ?
?????????????????????????????????????
? ? 4 ? ? 6 ? ? ? ? ? ?
?????????????????????????????????????
? 8 ? ? ? ? ? ? 1 ? ? 6 ?
?????????????????????????????????????
? 1 ? ? ? 2 ? 7 ? ? ? 4 ? ?
?????????????????????????????????????
请注意，对于 9x9 数独板，这将在合理的时间内起作用，但对于更大的板，您将需要更好/更快的求解器功能