infer

解数独算法

昨天在Ubuntu18.04上打开⾃带的数独游戏，宿舍⼏个⼈⼀起玩了很久，今天整理了⼀下玩的过程，研究出算法并写成程序，以⾃动求解数独游

戏，具体实现步骤已在代码注释中详细说明。

代码已发布在我的github上：HelloGithubHaHa

'''计算机⾃动解9x9数独游戏，输⼊题⽬后进⾏推断，若⽆法继续推断，则进⾏猜测，若猜测错误，则进⾏回溯，直到成功解出结果'''

'''题⽬信息保存在9x9的数组中，推断信息以t集合的形式存储于cheet_with_infer数组中''古代的四大美女 '

'''有两个主要的数据结构，⼀个是元素全为int的cheet_without_infer，⼀个是元素为int或t的cheet_with_infer'''

#需要⽤到深拷贝importcopy

defprint_cheet_without_infer(cheet):

'''打印没有推断信息的数组'''print()

forlineincheet:fornuminline:

print('{:^3}'.format(num),end='')print()

defprint_cheet_without_infer_to_input_again(cheet):

'''以与输⼊相同的格式，打印没有推断信息的数组，便于⼿动猜测后再次输⼊'''print()

forlineincheet:

print(','.join([str(x)forxinline]).replace('-1',''))

defprint_cheet_with_infer(cheet):

'''打印包含推断信息的数组'''print()

forlineincheet:forinferinline:

print('{:^15}'.format(str(infer).replace('','')),end='')print()

definfer(cheet,cheet_origin):'''

cheet为不包含推断信息的数组，cheet_origin为包含推断信息的数组

根据基本规则进⾏推断，每⼀个数所在⾏、列以及九宫格不能包含相同的数字

若数组中的所有元素都已经推断出，则返回2

若数组中的某个元素在此次函数调⽤中可以明确推断出，则返回1

若不能推断出任何未知元素，则返回0

若有错（某⼀位置的推断信息为空t集合），说明不满⾜任何数独的基本规则，返回-1'''

finish=True#如果数组中的所有元素都已经推断出，则finish为True

foriinrange(9):forjinrange(9):

ifcheet_origin[i][j]==-1:

finish=Fal#数组中尚有元素未推断出，finish为Fal

infer_t=t(range(1,10))#初始化推断信息

#通过⾏和列不能包含相同的数字进⾏推断forkinrange(9):

ifk!=jandcheet_origi创新英文 n[i][k]!=-1:

infer_d(cheet[i][k])

ifk!=iandcheet_origin[k][j]!=-1:infer_d(cheet[k][j])

#通过九宫格内不能包含相同的数字进⾏推断

x=j//3*3y=i//3*3

forminrange(y,y+3):forninrange(x,x+3):

if(m!=iorn!=j)andcheet_origin[m][n]!=-1:infer_d(cheet[m][n])

#判断此位置的推断信息，据此控制程序流程iflen(infer_t)==1:

cheet[i][j]=infer_()

cheet[i][j]=infer_()

cheet_origin[i][j]=cheet[i][j]return1

eliflen(infer_t)==0:

return-1el:

cheet[i][j]=infer_t

iffinish:

return2el:

return0

defpower_t(s):

'''求⼀个集合的所有⾮空真⼦集（⼆进制法），为了进⾏速度优化，需要在返回前对其进⾏排序'''

t_list=[]l=list(s)

n=len(l)

#⾮空，所以下界为1；真⼦集，所以上界是2的n次⽅

foriinrange(1,2**n-1):

combo=t()

forjinrange(n):

if(i>>j)%2==1:

(l[j])t_(combo)

t_list=sorted(t_list,key=lambdax:len(x))returnt_list

defdeep_infer(cheet,cheet_origin):'''

根据推断信息进⾏推断，去除某些位置的可能性数字

对于每⼀⾏、每⼀列、每⼀九宫格内的推断信息，

先求出这些推断信息的并集，再求出此并集的所有⾮空真⼦集，对于每⼀个⾮空真⼦集，

若推断信息中有⼩于等于此真⼦集⼤⼩数⽬的超集，并且对于其他推断信息，此真⼦集与其的交集均为空（不包含此真⼦集中的元素），

则这些位置的推断信息可置为此真⼦集

如某⼀⾏中有四个待推断元素，推断信息为：{1,3,6},{1,3,6},{1,4},{1,4}

在对其并集的⾮空真⼦集的遍历过程中，发现集合{3,6}的超集有{1,3,6}和{1,3,6}，并且其他推断信息{1,4}与此集合{3,6}的交集为空，

因此，可以将两个推断信息{1,3,6}置为{3,6}

若不能推断出任何未知元素，则返回2

若数组中的某个元素在此次函数调⽤中可以明确推断出，则返回1

若推断信息在此次函数调⽤中有修改，则返回0'''

change=Fal#推断信息是否有修改的标志

#根据每⼀⾏已有的推断信息进⾏推断

foriinrange(9):

#求并集

union_t=t()forjinrange(9):

ifisinstance(cheet[i][j],t):

union_t=union_(cheet[i][j])

#遍历根据长度排序的所有⾮空真⼦集

forsinpower_t(union_t):

contain_t_list=[]#保存列号

finish=True#若此⾏中的所有列上的推断信息的长度都⼩于等于集合s的长度，则可以提前退出，finish为True

satisfy=True#若除了集合s的超集以外，此⾏还含有推断信息与集合s的交集不为空的位置，则不能进⾏推断，satisfy为Falforjinrange(9):

ifisinstance(cheet[i][j],t老师的师怎么写 ):

iflen(cheet[i][j])>len(s):finish=Fal

et(cheet[i][j]):

contain_t_(j)

eliflen(ection(cheet[i][j]))>0:

satisfy=Fal

iffinish:

break

ifnotsatisfy:continue

iflen(contain_t_list)<=len(s)andlen(contain_t_list)>0:

#若s长度为1，则表明已经明确推断出此位置的数字，于是将t中的元素提取出来放到此位置上iflen(s)==1:

j=contain_t_list[0]cheet[i][j]=()

cheet_origin[i][j]=cheet[i][j]

cheet_origin[i][j]=cheet[i][j]return1

forjincontain_t_list:

iflen(cheet[i][j])>len(s):

cheet[i][j]=()change=True

#根据每⼀列已有的推断信息进⾏推断，和前⾯类似

forjinrange(9):

union_t=t()foriinrange(9):

ifisinstance(cheet[i][j],t):

union_t=union_(cheet[i][j])

forsinpower_t(union_t):

contain_t_list=[]

finish=Truesatisfy=True

foriinrange(9):

ifisinstance(cheet[i][j],t):

iflen(cheet[i][j])>len(s):finish=Fal

et(cheet[i][j]):

contain_t_(i)

eliflen(ection(cheet[i][j]))>0:

satisfy=Fal

iffinish:

break

ifnotsatisfy:continue

iflen(contain_t_list)<=len(s)andlen(contain_t_list)>0:iflen(s)==1:

i=contain_t_list[0]cheet[i][j]=()

cheet_origin[i][j]=cheet[i][j]return1

foriincontain_t_list:

iflen(cheet[i][j])>len(s):

cheet[i][j]=()change=True

#根麸炒白术的功效 据每⼀九宫格已有的推断信息进⾏推断，和前⾯类似

forminrange(3):

forninrange(3):union_t=t()

foriinrange(m*3,m*3+3):

forjinrange(n*3,n*3+3):ifisinstance(cheet[i][j],t):

union_t=union_(cheet[i][j])

forsinpower_t(union_t):

contain_t_list=[]

finish=Truesatisfy=True

foriinrange(m*3,m*3+3):

forjinrange(n*3,n*3+3):

ifisinstance(cheet[i][j],t):

iflen(cheet[i][j])>len(s):

finish=et(cheet[i][j]):

contain_t_((i,j))

eliflen(ection(cheet[i][j]))>0:

satisfy=Fal

iffinish:

break

ifnotsatisfy:continue

iflen(冰草的功效与作用 contain_t_list)<=len(s)andlen(contain_t_list)>0:iflen(s)==1:

i,j=contain_t_list[0]cheet[i][j]=()

cheet_origin[i][j]=cheet[i][j]return1

fori,jincontain_t_list:

iflen(cheet[i][j])>len(s):

cheet[i][j]=()change=True

ifnotchange:

return2el:

return0

deffind_min_to_guess(cheet_with_infer):

'''找到并返回⼀个推断信息的长度最⼩的位置'''

min_length=10#初始化最⼩长度标记foriinrange(9):

forjinrange(9):

ifisinstance(cheet_with_infer[i][j],t):

length=len(cheet_with_infer[i][j])

ifmin_length>length:

min_length=length

m=i

n=jreturnm,n

defstart(cheet_with_infer,cheet_without_infer):

'''开始进⾏推断，若推断成功，则返回True，否则返回Fal'''whileTrue:

print_cheet_without_infer(cheet_without_infer)

res=infer(cheet_with_infer,cheet_without_infer)

ifres==1:

continue

elifres==2:

returnTrue

elifres==-1:returnFal

whileTrue:

res=deep_infer(cheet_with_infer,cheet_without_infer)

ifres==1:

breakelifres==2:

#⽆法继续进⾏推断，于是在推断信息长度最⼩的位置进⾏假设，然后继续进⾏推断（递归），若猜测错误，则进⾏回溯

print_cheet_without_infer_to_input_again(cheet_without_infer)

print_cheet_with_infer(cheet_with_infer)

print('Cannotcontinuerefer!Beginguess!')

i,j=find_min_to_guess(cheet_with_infer)fornumincheet_with_infer[i][j]:

new_cheet_with_infer=py(cheet_with_in收据单怎么写 fer)

new_cheet_without_infer=py(cheet_without_infer)

new_cheet_with_infer[i][j]=numnew_cheet_without_infer[i][j]=num

res=start(new_cheet_with_infer,new_cheet_without_infer)ifres:

cheet_with_()

cheet_with_(new_cheet_with_infer)cheet_without_()

cheet_without_(new_cheet_without_infer)returnTrue

el:

print('Guesrror,beginnextguess!')

#⽤户通过图形界⾯输⼊题⽬信息，程序通过图形界⾯展⽰结果importtkinter

ebox

definfer_handler():

#没有推断信息的数组

cheet_without_infer=[]

forlabelsinall_labels:

nums=[]

forlabelinlabels:iflabel['text']:

(int(label['text']))el:

(-1)

cheet_without_(nums)

#有推断信息的数组，推断信息在推断的过程中加⼊

cheet_with_infer=py(cheet_without_infer)

cheet_with_infer=py(cheet_without_infer)

#开始推断

res=start(cheet_with_infer,cheet_without_infer)ifnotres:

ror('题⽬信息有误，⽆法进⾏推断！')

foriinrange(9):forjinrange(9):

all_labels[i][j]['text']=str(cheet_without_infer[i][j])

defclear_handler():

forlabelsinall_labels:

forlabelinlabels:label['text']=''

defchange_bg(source,origin_color):

forlabelsinall_labels:

forlabelinlabels:

label['bg']=origin_color

source['bg']='skyblue'defkeyboard_handler(event):

t()e==8:

forlabelsinall_labels:forlabelinlabels:

iflabel['bg']=='skyblue':

e==8:

label['text']=''el:

label['text']=ot=()

ble(Fal,Fal)

('数独解题器')

_all('',keyboard_handler)

#九宫格⾯板

top_frame=(root)

top_()

all_labels=[]

foriinrange(9):

row_labels=[]forjinrange(9):

label=(top_frame,font=('',18),width=2,height=1,relief=)origin_color=label['bg']

('',lambdaevent披着狼皮的羊 ,label=label:change_bg(label,origin_color))

(row=i,column=j)

row_(label)

all_(row_labels)

#底部按钮⾯板

bottom_frame=(root)bottom_()

infer_button=(bottom_frame,text='推断',font=('',18),command=infer_h胡豆黄 andler)infer_(side=,padx=5,pady=5)

clear_button=(bottom_frame,text='清空',font=('',18),command=clear_handler)

clear_(side=,padx=5,pady=5)op()