|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
使用随机数生成完整的数独,不使用已有的答案交换行列及数字
当前代码有一定几率使spyder内核崩溃,原因不详
- # -*- coding: utf-8 -*-
- """
- Created on Fri Apr 13 20:49:47 2018
- @author: Administrator
- """
- import numpy as np
- from random import sample as sm
- from itertools import permutations as pe
- cho=np.random.choice
- ar=np.arange
- meveryPos=list(pe(range(3),3))
- def mgenerate():
- mwhole=ar(81).reshape((9,9))#整个数独棋盘
- #下面这个循环怎么精简一下?
- for i in range(0,9,3):
- for j in range(0,9,3):
- mwhole[i:i+3,j:j+3]=cho(ar(9),(3,3),0)#给9个九宫格随机赋值0-8
- #对每三九宫格构成的行、列调整
- def madjust(mparts):
- #记录数字的列位置,9个子列表分别记录9个数字的列数字
- mdigitColumn=[[] for i in range(9)]
- for i in range(9):
- for j in range(3):
- mdigitColumn[mparts[j,i]].append(i)#记录数字的列位置
- #记录数字在每一行的可能性,初始为6种随机位置(3*2*1)
- mdigitPos=[sm(meveryPos,6) for _ in range(9)]
- #当确定一个数字的位置后,去掉其他数字在这个位置的可能性
- def deleteUnpossible(mnowDigit,mdigitPos):
- #记录起始状态,当以下循环确定下一个数字导致其他数字可能性为0时,恢复状态
- temp=mnowDigit,mdigitPos[:]
- #循环遍历当前数字的每一种可能,因为初始化可能值时已使用随机数,此处选择不必随机
- for meachpos in mdigitPos[mnowDigit][:]:
- #每次循环开始说明没有找到解,需要重新赋值,应该再写一个过程?
- #应该引用副本,害我找了一个晚的bug
- mdigitPos=temp[1][:]
- mnowDigit=temp[0]+0
- #修改当前数字的可能性为当前遍历的可能性
- mdigitPos[mnowDigit]=[meachpos]
- #记录当前数字选择后,被占用的位置,用于后面的比较
- mtakenPossition=list(zip(mdigitColumn[mnowDigit],mdigitPos[mnowDigit][0]))
- #删除当前数字以外的其他数字的不可能性
- for eachdigit in set(range(9))-set([mnowDigit]):
- #矛盾检查,查找每一种可能是否和已被占用的位置一致,任意位置存在说明不可能
- mdigitPos[eachdigit]=[eachpos for eachpos in mdigitPos[eachdigit] if sum(map(lambda x:list(zip(mdigitColumn[eachdigit],eachpos))[x]==mtakenPossition[x],range(3)))==0]
- #任意数字的可能性为空,都不再继续判断,退出循环继续下一个可能性
- if mdigitPos[eachdigit]==[]:break
- #循环没有退出,表明当前数字的可能性不影响其他数字,继续
- else:
- #下一个判断的数字,优先选择可能性最少的且不唯一的,这样写会导致虽然某个数字只有一种可能性,
- #但是没有对这种可能性进行矛盾检查,会出现位置重复,#这个bug又耗了我2个晚上
- mnowDigit=mdigitPos.index(min(mdigitPos,key=lambda x:len(x) if len(x)!=1 else 99))
- #因为上面图方便,下面这里不得不检查合法性
- #当mnowDigit==0,说明每个数字可能性唯一,同时要求所有数字的行位置和为9
- #即9个数字的行位置有三个为0,三个为1,三个为2,3个每个九宫格每个都要如此
- if mnowDigit==0 and sum(i==9 for i in np.sum(np.array(list(map(lambda x:x[0],mdigitPos))),axis=0))==3:
- #当满足各个数字可能性唯一性条件,退出递归,返回行位置
- return mdigitPos
- #进入递归
- mdigitPos=deleteUnpossible(mnowDigit,mdigitPos)
- #退出递归时,如果为0,说明没有找到解,继续循环,否则继续退出递归
- if mdigitPos:return mdigitPos
- #循环结束没有找到解,返回0
- return 0
- #从数字0开始,没必要再随机
- #因为推论:任意随机九宫格必有解,所以不必对结果判断
- mdigitPos=deleteUnpossible(0,mdigitPos)
- #给区域赋值,向量和列表一样,传的是对象的引用,结果修改以后不必返回???
- for i in range(9):
- for j in zip(mdigitPos[i][0],mdigitColumn[i]):
- mparts[j]=i
- #整个数独分9个九宫格,每次判断一行三个,一列三个
- for i in range(0,9,3):
- madjust(mwhole[i:i+3])
- madjust(mwhole[:,i:i+3].T)
- #打印,并对行列、九宫格验证
- print(mwhole+1)
- print('行唯一性',[len(set(mwhole[i])) for i in range(9)])
- print('列唯一性',[len(set(mwhole[:,i])) for i in range(9)])
- 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)])
-
- mgenerate()
复制代码 |
|