如何在 Python 中创建数独谜题 [英] How to create a Sudoku puzzle in Python
问题描述
目标是在 Python 中创建一个 9x9 数独矩阵.
Goal is to create a 9x9 Sudoku matrix in Python.
所以我走到了这一步.但我似乎无法让程序使内部应急箱正确.
So I got this far. But I cannot seem to get the program to get the interior contingent boxes correct.
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'
推荐答案
您可以生成一个随机数独解决方案板，其中填充所有数字，然后删除其中一些数字以创建拼图.这将确保谜题始终有解决方案.确保它只有一个解决方案更具挑战性(提示:您必须为 9x9 数独留下至少 17 个数字)
You can generate a random sudoku solution board where all numbers are filled in and then remove some of them to create the puzzle. This will ensure that the puzzle always has a solution. Making sure that it has exactly one solution is a bit more challenging (hint: you must leave at least 17 numbers for a 9x9 sudoku)
下面的算法将立即生成一个 NxN 随机数独解决方案板，适用于 N <1000.
The algorithm below will generate a NxN random sudoku solution board instantly for 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]
然后您可以从数独解决方案中删除一些数字来创建拼图:
You can then remove some of the numbers from the sudoku solution to create the puzzle:
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 的拼图，您可以像这样打印出更好的棋盘:
For 4x4 up to 36x36 puzzles, you could make a nicer print of the board like this:
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 ║
╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝
这里有一些关于洗牌过程的额外信息......
Here are some additional information on the shuffling process ...
洗牌行分为 3 行一组.可以整体交换组，但我们不能在不破坏块完整性的情况下跨组交换行.(同样的推理适用于列)
Shuffling rows is broken down in groups of 3 rows. It is ok to swap groups as a whole but we can't swap rows across groups without breaking the integrity of the blocks. (the same reasoning applies to columns)
例如:
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:
We can swap groups 0,1,2 by moving all 3 of their rows at the same time:
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)...
And we can swap between the 3 rows of a group (e.g. 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):
We CANNOT swap rows across groups (e.g. 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%(或更多)的数字开始，然后检查是否只有一个解决方案.如果有多个解决方案，请放回一个数字并再次检查.您可以在随机位置放回一个数字或选择一个解决方案不同的位置(这将更快地收敛到单个解决方案难题)
In order to generate a sudoku puzzle with only one solution you will need a solver function that can tell you if there are more than one solution. The strategy I would suggest is to start with 75% (or more) of the numbers removed, then check that there is only one solution. If there is more than one solution, put back a number and check again. You can put back a number at a random position or select a position where the solutions differ (which will converge faster to a single solution puzzle)
首先编写一个求解器，它将生成它找到的所有解(理想情况下作为生成器，因为我们只需要前 2 个).这是一个简单的:
First write a solver that will generate all solutions that it finds (ideally as a generator because we only need the first 2). Here's a simple one:
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 变量和包含已清除 3/4 数字的谜题的 board 变量开始，您可以将数字添加回棋盘直到出现这只是解决它的一种方法:
Starting with a solution variable with all numbers present and board variable containing the puzzle with 3/4 of numbers cleared, you can add numbers back to the board until there is only one way to solve it:
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 数独板，这将在合理的时间内起作用，但对于更大的板，您将需要一个更好/更快的求解器功能
这篇关于如何在 Python 中创建数独谜题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
