袋马计划-生成完整数独

达锅

使用随机数生成完整的数独，不使用已有的答案交换行列及数字
当前代码有一定几率使spyder内核崩溃，原因不详

1. # -*- coding: utf-8 -*-
   
2. """
   
3. Created on Fri Apr 13 20:49:47 2018
   
4. 
   
5. @author: Administrator
   
6. """
   
7. 
   
8. import numpy as np
   
9. from random import sample as sm
   
10. from itertools import permutations as pe
    
11. 
    
12. cho=np.random.choice
    
13. ar=np.arange
    
14. meveryPos=list(pe(range(3),3))
    
15. def mgenerate():
    
16.     mwhole=ar(81).reshape((9,9))#整个数独棋盘
    
17.     #下面这个循环怎么精简一下？
    
18.     for i in range(0,9,3):
    
19.         for j in range(0,9,3):
    
20.             mwhole[i:i+3,j:j+3]=cho(ar(9),(3,3),0)#给9个九宫格随机赋值0-8
    
21.     #对每三九宫格构成的行、列调整
    
22.     def madjust(mparts):
    
23.         #记录数字的列位置,9个子列表分别记录9个数字的列数字
    
24.         mdigitColumn=[[] for i in range(9)]
    
25.         for i in range(9):
    
26.             for j in range(3):
    
27.                 mdigitColumn[mparts[j,i]].append(i)#记录数字的列位置
    
28.         #记录数字在每一行的可能性，初始为6种随机位置（3*2*1）
    
29.         mdigitPos=[sm(meveryPos,6) for _ in range(9)]
    
30.         #当确定一个数字的位置后，去掉其他数字在这个位置的可能性
    
31.         def deleteUnpossible(mnowDigit,mdigitPos):
    
32.             #记录起始状态，当以下循环确定下一个数字导致其他数字可能性为0时，恢复状态
    
33.             temp=mnowDigit,mdigitPos[:]
    
34.             #循环遍历当前数字的每一种可能，因为初始化可能值时已使用随机数，此处选择不必随机
    
35.             for meachpos in mdigitPos[mnowDigit][:]:
    
36.                 #每次循环开始说明没有找到解，需要重新赋值，应该再写一个过程？
    
37.                 #应该引用副本，害我找了一个晚的bug
    
38.                 mdigitPos=temp[1][:]
    
39.                 mnowDigit=temp[0]+0
    
40.                 #修改当前数字的可能性为当前遍历的可能性
    
41.                 mdigitPos[mnowDigit]=[meachpos]
    
42.                 #记录当前数字选择后，被占用的位置，用于后面的比较
    
43.                 mtakenPossition=list(zip(mdigitColumn[mnowDigit],mdigitPos[mnowDigit][0]))
    
44.                 #删除当前数字以外的其他数字的不可能性
    
45.                 for eachdigit in set(range(9))-set([mnowDigit]):
    
46.                     #矛盾检查，查找每一种可能是否和已被占用的位置一致，任意位置存在说明不可能
    
47.                     mdigitPos[eachdigit]=[eachpos for eachpos in mdigitPos[eachdigit] if sum(map(lambda x:list(zip(mdigitColumn[eachdigit],eachpos))[x]==mtakenPossition[x],range(3)))==0]
    
48.                     #任意数字的可能性为空，都不再继续判断，退出循环继续下一个可能性
    
49.                     if mdigitPos[eachdigit]==[]:break
    
50.                 #循环没有退出，表明当前数字的可能性不影响其他数字，继续
    
51.                 else:
    
52.                     #下一个判断的数字，优先选择可能性最少的且不唯一的，这样写会导致虽然某个数字只有一种可能性，
    
53.                     #但是没有对这种可能性进行矛盾检查，会出现位置重复，#这个bug又耗了我2个晚上
    
54.                     mnowDigit=mdigitPos.index(min(mdigitPos,key=lambda x:len(x) if len(x)!=1 else 99))
    
55.                     #因为上面图方便，下面这里不得不检查合法性
    
56.                     #当mnowDigit==0，说明每个数字可能性唯一，同时要求所有数字的行位置和为9
    
57.                     #即9个数字的行位置有三个为0，三个为1，三个为2，3个每个九宫格每个都要如此
    
58.                     if mnowDigit==0 and sum(i==9 for i in np.sum(np.array(list(map(lambda x:x[0],mdigitPos))),axis=0))==3:
    
59.                         #当满足各个数字可能性唯一性条件，退出递归，返回行位置
    
60.                         return mdigitPos
    
61.                     #进入递归
    
62.                     mdigitPos=deleteUnpossible(mnowDigit,mdigitPos)
    
63.                     #退出递归时，如果为0，说明没有找到解，继续循环，否则继续退出递归
    
64.                     if mdigitPos:return mdigitPos
    
65.             #循环结束没有找到解，返回0
    
66.             return 0
    
67.         #从数字0开始，没必要再随机
    
68.         #因为推论：任意随机九宫格必有解，所以不必对结果判断
    
69.         mdigitPos=deleteUnpossible(0,mdigitPos)
    
70.         #给区域赋值，向量和列表一样，传的是对象的引用，结果修改以后不必返回？？？
    
71.         for i in range(9):
    
72.             for j in zip(mdigitPos[i][0],mdigitColumn[i]):
    
73.                 mparts[j]=i
    
74.     #整个数独分9个九宫格，每次判断一行三个，一列三个
    
75.     for i in range(0,9,3):
    
76.         madjust(mwhole[i:i+3])
    
77.         madjust(mwhole[:,i:i+3].T)
    
78.     #打印，并对行列、九宫格验证
    
79.     print(mwhole+1)
    
80.     print('行唯一性',[len(set(mwhole[i])) for i in range(9)])
    
81.     print('列唯一性',[len(set(mwhole[:,i])) for i in range(9)])
    
82.     print('九宫格唯一性',[len(set(list(mwhole[i:i+3,j:j+3].reshape(1,9)[0]))) for i in range(0,9,3) for j in range(0,9,3)])
    
83.    
    
84. mgenerate()

复制代码