1.生成A9排列矩阵
1到9，9个数字的全排列可以说是数独的基础，根据统计学可以计算出9个数字的全排列是362880个。三十多万个，很容易可以用穷举法求出全部的排列，并且保存到文件中。下面的类用来实现生成1到9九个数的全排列，保存到文件中，若要使用，则可以直接从文件读取。
import json
#362880个
class GenA9:
A9=[0]*9
A9_ans = []
A9_count = 0
#从文件读取已经保存的全排列，public
def readFromFile(self):
f = open('A9_ans','r+')
self.A9_ans = json.load(f)
self.A9_count = len(self.A9_ans)
f.close()
#枚举所有排列并保存到文件中，public
def gen(self):
f = open('A9_ans','w+')
self.next_a9(0)
json.dump(self.A9_ans,f)
f.close()
#枚举第x个数，private
def next_a9(self,x):
if x==9:
self.A9_count += 1
self.A9_ans.append(self.A9.copy())
return
for n in range(1,10):
if n not in self.A9:
self.A9[x] = n
self.next_a9(x+1)
self.A9[x] = 0
2. 生成数独矩阵
满足数独规则的矩阵的个数，通过查询相关文献，总共约6.671*10^21个，这个级别的数据已经不是可能全部枚举出来的了，因此要生成数独矩阵，这里仅仅生成一个。并且保证随机，每次生成的矩阵，都不一样。
我们首先通过一般枚举，找到一个数独矩阵就停止：
class ShuDuCore:
sz = [[0 for x in range(9)] for y in range(9)]
def next_sz(self,x):
if x==81:
return True
i = x//9
j = x%9
for n in range(1,10):
if not self.find_num(i,j,n):
self.sz[i][j] = n
if self.next_sz(x+1):
return True
self.sz[i][j] = 0
def find_num(self,i,j,num):
for k in range(9):
if self.sz[i][k]==num:
return True
if self.sz[k][j]==num:
return True
sx = i//3*3
sy = j//3*3
for x in range(0,3):
for y in range(0,3):
if self.sz[sx+x][sy+y]==num:
return True
return False
若想得到随机的数独矩阵，可以利用上一节实现的GenA9类，用随机的某一个排列，替代for n in range(1,10)循环中的range(1,10)即可。
from GenA9 import GenA9
import random
class ShuDuCore:
sz = [[0 for x in range(9)] for y in range(9)]
def __init__(self):
self.genA9 = GenA9()
self.genA9.readFromFile()
def next_sz(self,x):
if x==81:
return True
i = x//9
j = x%9
index = random.randrange(self.genA9.A9_count)
for n in self.genA9.A9_ans[index]:
if not self.find_num(i,j,n):
self.sz[i][j] = n
if self.next_sz(x+1):
return True
self.sz[i][j] = 0
def find_num(self,i,j,num):
for k in range(9):
if self.sz[i][k]==num:
return True
if self.sz[k][j]==num:
return True
sx = i//3*3
sy = j//3*3
for x in range(0,3):
for y in range(0,3):
if self.sz[sx+x][sy+y]==num:
return True
return False
def genRandom(self):
self.next_sz(0)
return self.sz.copy()
用户调用genRandom即可返回一个随机的数独矩阵。
3. 生成游戏矩阵
在数独矩阵中，删除一些数得到的矩阵，就可以用来进行数独游戏了。一般来讲，已知数的范围在20-35之间，也就是未知数范围在46-61。忽略游戏难度的影响，生成游戏矩阵的方法就是在46-61之间随机选取一个数N，然后随机生成9*9矩阵中的N个坐标，将其设为0表示空，最后验证下该游戏矩阵的解是否唯一。
验证的方法与生成矩阵的算法一样，只不过需要跳过非0的数。
def solve(self,sd):
self.sd = sd
self.sd_ans = []
self.sd_count =0
self.solve_next(0)
print("共"+str(self.sd_count)+"个解")
def solve_next(self,x):
if x==81:
self.sd_count +=1
self.sd_ans.append(str(self.sd))
print("得到第"+str(self.sd_count)+"个解")
print(self.sd_ans)
return
i = x//9
j = x%9
if self.sd[i][j]==0:
for n in range(1,10):
if not self.find_num(self.sd,i,j,n):
self.sd[i][j] = n
self.solve_next(x+1)
self.sd[i][j] = 0
else:
self.solve_next(x+1)
随机生成游戏矩阵：
def __splitX(self,x):
return x//9,x%9
def __adjustX(self,x,sd):
i,j = self.__splitX(x)
while sd[i][j]==0:
x += 1
if x==81:
x = random.randrange(0,81)
i,j = self.__splitX(x)
return i,j
def __copyMatrix(self,src):
dst = [[0 for x in range(len(src))] for y in range(len(src[0]))]
for i in range(len(src)):
for j in range(len(src[0])):
dst[i][j] = src[i][j]
return dst
def __markMatrix(self,srcSD):
dstSD = self.__copyMatrix(srcSD)
N = random.randrange(46,62)
for i in range(N):
X = random.randrange(0,81)
i,j = self.__adjustX(X,dstSD)
dstSD[i][j] = 0
return dstSD
def genGame(self):
self.count += 1
srcSD = self.__genRandom()
#print(srcSD)
mult = True
while mult:
markSD = self.__markMatrix(srcSD)
solveSD = self.__copyMatrix(markSD)
if self.__solve(solveSD)==1:
mult = False
return srcSD,markSD
4. 完整的ShuDu.py文件：
from GenA9 import GenA9
import random
import time
import json
class ShuDuCore:
sz = [[0 for x in range(9)] for y in range(9)]
time1 = 0
outoftime = 500
def __init__(self):
self.genA9 = GenA9()
self.genA9.readFromFile()
def __next_sz(self,x):
if x==81:
return True
i = x//9
j = x%9
index = random.randrange(self.genA9.A9_count)
for n in self.genA9.A9_ans[index]:
if not self.__find_num(self.sz,i,j,n):
self.sz[i][j] = n
if self.__next_sz(x+1):
return True
self.sz[i][j] = 0
def __find_num(self,sz,i,j,num):
for k in range(9):
if sz[i][k]==num:
return True
if sz[k][j]==num:
return True
sx = i//3*3
sy = j//3*3
for x in range(0,3):
for y in range(0,3):
if sz[sx+x][sy+y]==num:
return True
return False
def __genRandom(self):
self.__next_sz(0)
return self.sz.copy()
def __solve(self,sd):
self.sd = sd
self.sd_ans = []
self.sd_count =0
self.__solve_next(0)
return self.sd_count
def __solve_next(self,x):
if time.time()-self.time1 > self.outoftime:
self.sd_count = 0
return True
if x==81:
self.sd_count +=1
self.sd_ans.append(str(self.sd))
if self.sd_count>1:
return True
else:
return False
i = x//9
j = x%9
if self.sd[i][j]==0:
for n in range(1,10):
if not self.__find_num(self.sd,i,j,n):
self.sd[i][j] = n
if self.__solve_next(x+1)==True:
return True
self.sd[i][j] = 0
else:
return self.__solve_next(x+1)
def __splitX(self,x):
return x//9,x%9
def __adjustX(self,x,sd):
i,j = self.__splitX(x)
while sd[i][j]==0:
x += 1
if x==81:
x = random.randrange(0,81)
i,j = self.__splitX(x)
return i,j
def __copyMatrix(self,src):
dst = [[0 for x in range(len(src))] for y in range(len(src[0]))]
for i in range(len(src)):
for j in range(len(src[0])):
dst[i][j] = src[i][j]
return dst
def __markMatrix(self,srcSD):
dstSD = self.__copyMatrix(srcSD)
N = random.randrange(46,62)
for i in range(N):
X = random.randrange(0,81)
i,j = self.__adjustX(X,dstSD)
dstSD[i][j] = 0
return dstSD
def genGame(self):
srcSD = self.__genRandom()
mult = True
tryTime = 0
self.time1 = time.time()
while mult:
tryTime += 1
markSD = self.__markMatrix(srcSD)
solveSD = self.__copyMatrix(markSD)
if self.__solve(solveSD)==1:
mult = False
dt = time.time()-self.time1
if tryTime > 2000:
return [],[],tryTime
elif dt>self.outoftime:
return [],[],0
elif tryTime%100==0:
print(" take "+str(tryTime)+"Times "+str(dt)+"sec")
return srcSD,markSD,tryTime
sdcore = ShuDuCore()
tryTimes = []
takeSec = []
sd_ans = []
f = open("sd_ans",'r')
sd_ans = json.load(f)
f.close()
count = 1
while count<=1000:
print("waiting..."+str(count)+"/1000")
time1 = time.time()
srcSD,markSD,c = sdcore.genGame()
time2 = time.time()
tryTimes.append(c)
takeSec.append(time2-time1)
if c>2000:
print("failed take "+str(c)+" Times "+ str(time2-time1)+"sec\n")
elif c==0:
print("failed out of time ..\n")
else:
print("success take "+str(c)+" Times"+ str(time2-time1)+"sec")
has = True
for sd in sd_ans:
for i in range(len(sd)):
for j in range(len(sd[0])):
if sd[i][j]!=markSD[i][j]:
has = False
break
if not has:
break
if not has:
break
if has:
print("but.. already has ...! -_-!\n")
else:
print("add to database\n")
count += 1
sd_ans.append(markSD)
save_sd_ans()
def save_sd_ans():
f = open('sd_ans','w+')
json.dump(sd_ans,f)
f.close()
网友评论