python 实现数独游戏

import pandas as pdimport numpy as npshudu_data=pd.read_csv('data/shudu.csv')data=shudu_data.copy()def block(i,data):ru3_1=data.iloc[0:3,0:3]ru3_2=data.iloc[0:3,3:6]ru3_3=data.iloc[0:3,6:]ru3_4=data.iloc[3:6,0:3]ru3_5=data.iloc[3:6,3:6]ru3_6=data.iloc[3:6,6:]ru3_7=data.iloc[6:,0:3]ru3_8=data.iloc[6:,3:6]ru3_9=data.iloc[6:,6:]ru3_list=[ru3_1,ru3_2,ru3_3,ru3_4,ru3_5,ru3_6,ru3_7,ru3_8,ru3_9]ru3=ru3_list[i]
ru3=ru3.values.tolist()
lis=[]
for l in ru3:
    lis+=l
ru3=set(lis)-{0}return ru3

def Block_dataframe(i,data):ru3_1=pd.DataFrame(data=data.iloc[0:3,0:3],index=[0,1,2],columns=['0','1','2'])ru3_2=pd.DataFrame(data=data.iloc[0:3,3:6],index=[0,1,2],columns=['3','4','5'])
ru3_3=pd.DataFrame(data=data.iloc[0:3,6:],index=[0,1,2],columns=['6','7','8'])
ru3_4=pd.DataFrame(data=data.iloc[3:6,0:3],index=[3,4,5],columns=['0','1','2'])
ru3_5=pd.DataFrame(data=data.iloc[3:6,3:6],index=[3,4,5],columns=['3','4','5'])
ru3_6=pd.DataFrame(data=data.iloc[3:6,6:],index=[3,4,5],columns=['6','7','8'])
ru3_7=pd.DataFrame(data=data.iloc[6:,0:3],index=[6,7,8],columns=['0','1','2'])
ru3_8=pd.DataFrame(data=data.iloc[6:,3:6],index=[6,7,8],columns=['3','4','5'])
ru3_9=pd.DataFrame(data=data.iloc[6:,6:],index=[6,7,8],columns=['6','7','8'])

ru3_list=[ru3_1,ru3_2,ru3_3,ru3_4,ru3_5,ru3_6,ru3_7,ru3_8,ru3_9]

return ru3_list[i]

flag=True
for ind in range(9):
    li_1=list(data.iloc[ind].values)
    li_=[]
    for li in li_1:
        if li!=0:
            li_.append(li)
    flag=(len(set(li_))==len(li_))
    if flag==False:
        return flag

for col in ['0','1','2','3','4','5','6','7','8']:
    li_2=list(data.iloc[:][col].values)
    li_=[]
    for li in li_2:
        if li!=0:
            li_.append(li)
    #print(set(li_))
    #print(li_)
    flag=(len(set(li_))==len(li_))
    if flag==False:
        return flag

for i in range(9):
    block_dataframe=Block_dataframe(i,data)
    li_3=block_dataframe.values.tolist()
    li_q=[]
    for li_ in li_3:
        li_q=li_q+li_  
    li_=[]
    for li in li_q:
        if li!=0:
            li_.append(li) 

    flag=(len(set(li_))==len(li_))
    if flag==False:
        return flagreturn flagdef full(data):for i in range(9):for j in ['0','1','2','3','4','5','6','7','8']:if data[j][i]==0:return Falsereturn Truedef Block_num(index,colums,data):if index in [0,1,2]:if colums in ['0','1','2']:block_num=0elif colums in ['3','4','5']:block_num=1else:block_num=2if index in [3,4,5]:if colums in ['0','1','2']:block_num=3elif colums in ['3','4','5']:block_num=4else:block_num=5if index in [6,7,8]:if colums in ['0','1','2']:block_num=6elif colums in ['3','4','5']:block_num=7else:block_num=8return block_numdef len_re(index,colums,data):result={1,2,3,4,5,6,7,8,9}ru1=set(data.iloc[index])ru2=set(data[colums])if index in [0,1,2]:if colums in ['0','1','2']:ru3=block(0,data)elif colums in ['3','4','5']:ru3=block(1,data)else:ru3=block(2,data)if index in [3,4,5]:if colums in ['0','1','2']:ru3=block(3,data)elif colums in ['3','4','5']:ru3=block(4,data)else:ru3=block(5,data)if index in [6,7,8]:if colums in ['0','1','2']:ru3=block(6,data)elif colums in ['3','4','5']:ru3=block(7,data)else:ru3=block(8,data)re=result-ru1-ru2-ru3-{0}return re

class result():def result(self,data):
    #计算每个位置上可能的结果，返回pos，ans
    index=[0,1,2,3,4,5,6,7,8]
    colums=['0','1','2','3','4','5','6','7','8']
    pos=[]
    ans=[]
    for ind in index:
        for col in colums:
            if data[col][ind] ==0:
                re=len_re(ind,col,data)
                ans.append(list(re))
                pos.append((ind,col)) 
    return zip(pos,ans)

       def result_min_len(data):R=result()c=R.result(data)reslut_len=[]reslut_list=[]try:for pos,ans in c:reslut_list.append(ans)reslut_len.append(len(ans))return min(reslut_len)except:return False

class paichu():def result(self,data):    data_copy=data.copy()
    #如果一个位置出现多个结果，循序试错,排除错误答案：
    i=0
    j=0
    if result_min_len(data_copy)==0:
        print('传入数据错误，计算中止')
    else:
        result_=result()
        result_1=result_.result(data_copy)
        pos_=[]
        ans_1_b=[]
        for pos,ans_list in result_1:
            ind=pos[0]
            col=pos[1]
            ans_1_a=[]
            for ans in ans_list:
                j+=1
                data_copy[col][ind]=ans
                f=result_min_len(data_copy)
                if f:
                    i+=1
                    ans_1_a.append(ans)
                data_copy[col][ind]=0
            ans_1_b.append(ans_1_a)
            pos_.append((ind,col))
        print('已经排除{}个数'.format(j-i))
        return zip(pos_,ans_1_b)

class rule_1():def result(self,data):    #如果ind=0，按行，ind=1，按列排除
    ind=0
    result_000=result()
    answer_zip=result_000.result(data)

    #rule1 如果n个相同的list在同一行/列，且元素数量等于list的个数，则该行其他待定cell可以排除list中所有元素
    index_0=[]
    index_1=[]
    index_2=[]
    index_3=[]
    index_4=[]
    index_5=[]
    index_6=[]
    index_7=[]
    index_8=[] 

    ans_0=[]
    ans_1=[]
    ans_2=[]
    ans_3=[]
    ans_4=[]
    ans_5=[]
    ans_6=[]
    ans_7=[]
    ans_8=[]

    for pos,ans in answer_zip:
        if pos[ind]==0:
            index_0.append(pos)
            ans_0.append(ans)
        elif pos[ind]==1:
            index_1.append(pos)
            ans_1.append(ans)
        elif pos[ind]==2:
            index_2.append(pos)
            ans_2.append(ans)
        elif pos[ind]==3:
            index_3.append(pos)
            ans_3.append(ans)
        elif pos[ind]==4:
            index_4.append(pos)
            ans_4.append(ans)
        elif pos[ind]==5:
            index_5.append(pos)
            ans_5.append(ans)
        elif pos[ind]==6:
            index_6.append(pos)
            ans_6.append(ans)
        elif pos[ind]==7:
            index_7.append(pos)
            ans_7.append(ans)
        elif pos[ind]==8:
            index_8.append(pos)
            ans_8.append(ans)

    index=[index_0,index_1,index_2,index_3,index_4,index_5,index_6,index_7,index_8]
    ans=[ans_0,ans_1,ans_2,ans_3,ans_4,ans_5,ans_6,ans_7,ans_8]

    ans_=[]
    for ans_array in ans:
        l2=[]
        for i in ans_array:
            l2.append(set(i))

        for i in np.unique(l2):
            if l2.count(i)==len(i):
                for k,j in enumerate(l2):
                    if i!=j:
                        j=j-i
                        l2[k]=j

        ans_.append(list(l2))

    pos_=[]
    for i in index:
        pos_=pos_+i

    ans_list=[]
    for i in ans_:
        ans_list=ans_list+i
    ans_listn=[]
    for i in ans_list:
        ans_listn.append(list(i))
    return zip(pos_,ans_listn)

def result(self,data):
    #如果ind=0，按行，ind=1，按列排除
    ind=1
    result_000=result()
    answer_zip=result_000.result(data)

    #rule1 如果n个相同的list在同一行/列，且元素数量等于list的个数，则该行其他待定cell可以排除list中所有元素
    index_0=[]
    index_1=[]
    index_2=[]
    index_3=[]
    index_4=[]
    index_5=[]
    index_6=[]
    index_7=[]
    index_8=[] 

    ans_0=[]
    ans_1=[]
    ans_2=[]
    ans_3=[]
    ans_4=[]
    ans_5=[]
    ans_6=[]
    ans_7=[]
    ans_8=[]

    for pos,ans in answer_zip:
        if pos[ind]=='0':
            index_0.append(pos)
            ans_0.append(ans)
        elif pos[ind]=='1':
            index_1.append(pos)
            ans_1.append(ans)
        elif pos[ind]=='2':
            index_2.append(pos)
            ans_2.append(ans)
        elif pos[ind]=='3':
            index_3.append(pos)
            ans_3.append(ans)
        elif pos[ind]=='4':
            index_4.append(pos)
            ans_4.append(ans)
        elif pos[ind]=='5':
            index_5.append(pos)
            ans_5.append(ans)
        elif pos[ind]=='6':
            index_6.append(pos)
            ans_6.append(ans)
        elif pos[ind]=='7':
            index_7.append(pos)
            ans_7.append(ans)
        elif pos[ind]=='8':
            index_8.append(pos)
            ans_8.append(ans)

    index=[index_0,index_1,index_2,index_3,index_4,index_5,index_6,index_7,index_8]
    ans=[ans_0,ans_1,ans_2,ans_3,ans_4,ans_5,ans_6,ans_7,ans_8]

    ans_=[]
    for ans_array in ans:
        l2=[]
        for i in ans_array:
            l2.append(set(i))

        for i in np.unique(l2):
            if l2.count(i)==len(i):
                for k,j in enumerate(l2):
                    if i!=j:
                        j=j-i
                        l2[k]=j
        ans_.append(list(l2))

    pos_=[]
    for i in index:
        pos_=pos_+i

    ans_list=[]
    for i in ans_:
        ans_list=ans_list+i
    ans_listn=[]
    for i in ans_list:
        ans_listn.append(list(i))
    return zip(pos_,ans_listn)

def result(self,data):

    result_000=result()
    answer_zip=result_000.result(data)

    #rule3 如果n个相同的list在同一9宫格，且元素数量等于list的个数，则该行其他待定cell可以排除list中所有元素
    block_0=[]
    block_1=[]
    block_2=[]
    block_3=[]
    block_4=[]
    block_5=[]
    block_6=[]
    block_7=[]
    block_8=[] 

    index_0=[]
    index_1=[]
    index_2=[]
    index_3=[]
    index_4=[]
    index_5=[]
    index_6=[]
    index_7=[]
    index_8=[] 

    for pos,ans in answer_zip:
        index=pos[0]
        colums=pos[1]

        if index in [0,1,2]:
            if colums in ['0','1','2']:
                block_0.append(ans)
                index_0.append(pos)
            elif colums in ['3','4','5']:
                block_1.append(ans)
                index_1.append(pos)
            else:
                block_2.append(ans)
                index_2.append(pos)
        if index in [3,4,5]:
            if colums in ['0','1','2']:
                block_3.append(ans)
                index_3.append(pos)
            elif colums in ['3','4','5']:
                block_4.append(ans)
                index_4.append(pos)
            else:
                block_5.append(ans)
                index_5.append(pos)
        if index in [6,7,8]:
            if colums in ['0','1','2']:
                block_6.append(ans)
                index_6.append(pos)
            elif colums in ['3','4','5']:
                block_7.append(ans)
                index_7.append(pos)
            else:
                block_8.append(ans)
                index_8.append(pos)

    index=[index_0,index_1,index_2,index_3,index_4,index_5,index_6,index_7,index_8]       
    block=[block_0,block_1,block_2,block_3,block_4,block_5,block_6,block_7,block_8]

    ans_=[]   
    for index_array in block:
        l2=[]
        for i in index_array:
            l2.append(set(i))

        for i in np.unique(l2):
            if l2.count(i)==len(i):
                for k,j in enumerate(l2):
                    if i!=j:
                        j=j-i
                        l2[k]=j    
        ans_.append(list(l2))

    pos_=[]
    for i in index:
        pos_=pos_+i

    ans_list=[]
    for i in ans_:
        ans_list=ans_list+i
    ans_listn=[]
    for i in ans_list:
        ans_listn.append(list(i))
    return zip(pos_,ans_listn)

def result(self,data):
    Rule_1=rule_1()
    Rule_2=rule_2()
    Rule_3=rule_3()

    result_dict_1={}
    for pos,ans in Rule_1.result(data):
        result_dict_1[pos]=set(ans)
    result_dict_2={}
    for pos,ans in Rule_2.result(data):
        result_dict_2[pos]=set(ans)  
    result_dict_3={}
    for pos,ans in Rule_3.result(data):
        result_dict_3[pos]=set(ans)

    #三本字典根据key值 取交集融合为最终结果
    key_list=result_dict_1.keys()
    result_dict={}
    for key in key_list:
        result_dict[key]=(result_dict_1[key])&(result_dict_2[key])&(result_dict_3[key])

    ans=[]
    pos=[]
    for key,value in result_dict.items():
        k=list(value)
        k.sort()
        ans.append(k)
        pos.append(key)

    return zip(pos,ans)

def fill_pinlv(result_zip,data):#输入数据类型为zipresult_zip=result_zip
result_list=list(result_zip)
#print(result_zip)

block_num_list=[]
for tup in result_list:
    pos=tup[0]
    ans=tup[1]
    block_num=Block_num(pos[0],pos[1],data)
    block_num_list.append(block_num)
#print(block_num_list)

ind_list_0=[]
ind_list_1=[]
ind_list_2=[]
ind_list_3=[]
ind_list_4=[]
ind_list_5=[]
ind_list_6=[]
ind_list_7=[]
ind_list_8=[]
ind_block_array=[]
for ind,num in enumerate(block_num_list):

    if num==0:
        ind_list_0.append(ind)
    if num==1:
        ind_list_1.append(ind)            
    if num==2:
        ind_list_2.append(ind)            
    if num==3:
        ind_list_3.append(ind)
    if num==4:
        ind_list_4.append(ind)            
    if num==5:
        ind_list_5.append(ind)    
    if num==6:
        ind_list_6.append(ind)
    if num==7:
        ind_list_7.append(ind)            
    if num==8:
        ind_list_8.append(ind)    
ind_block_array=[ind_list_0,ind_list_1,ind_list_2,ind_list_3,ind_list_4,ind_list_5,ind_list_6,ind_list_7,ind_list_8]
#print(ind_block_array)

result_block_array=[]
for ind_list in ind_block_array:
    result_block_list=[]
    for ind in ind_list:
        result_block_list.append(result_list[ind])
    result_block_array.append(result_block_list)  
#print(result_block_array)

#生成block_counter_array
block_counter_array=[]
for block_list in result_block_array:
    counter_list=[]
    for i in range(1,10):
        counter=0
        for pos,ans in block_list:
            if i in ans:
                counter+=1
        counter_list.append(counter)
    block_counter_array.append(counter_list) 
#print(block_counter_array)

#更新数据data
jishuqi=0
for block_index,block in enumerate(block_counter_array):
    processing_num=0
    processing_num_pos=False
    for num,count in enumerate(block):
        if count==1:
            processing_num=num+1
            for tup in result_list:
                pos=tup[0]
                ans=tup[1]

                if block_index==Block_num(pos[0],pos[1],data):
                    #print(block_index)
                    if processing_num in ans:
                        #print(pos)
                        processing_num_pos=pos
                        jishuqi+=1
                        data[processing_num_pos[1]][processing_num_pos[0]]=processing_num
                        if jianyan(data)==False:
                            data[processing_num_pos[1]][processing_num_pos[0]]=0
                            return jishuqi

return jishuqi   

def fill_jilian(data):jishuqi=0for i in range(1,10):index_list=[]col_list=[]block_dataframe=pd.DataFrame()for block_num in range(9):#print(block_num)block_dataframe=Block_dataframe(block_num,data)index_list=list(block_dataframe.index)col_list=list(block_dataframe.columns)if i not in block_dataframe.values:#排除行 indexfor ind in index_list:for col in range(9):if i==data.iloc[ind][col]:index_list.remove(ind)#排除列 colfor col in col_list:for ind in range(9):if i ==data[col][ind]:col_list.remove(col)        #排除有数的cell        pos_list=[]
        for ind in index_list:
            for col in col_list:
                pos=(ind,col)
                pos_list.append(pos)
        for pos in pos_list:
            if data[pos[1]][pos[0]]!=0:
                pos_list.remove(pos)
        #print(pos_list)
        #填入数字
        if len(pos_list)==1:
            pos=pos_list[0]
            data[pos[1]][pos[0]]=i  
            jishuqi+=1
#print('已经填入{}个数字'.format(jishuqi))
return jishuqi

def fill(data,classname):#print('执行中。。。')data=dataif classname =='result':cla=result()elif classname=='paichu':cla=paichu()elif classname=='rule':cla=rule()#如果位置上只有一种可能，就直接填入datai=0
m=0
flag_1=True
while(flag_1):

    if result_min_len(data)==0:
        #print('上一轮输入的数据有误')
        flag_1=False  
    m=i
    for pos,ans in cla.result(data):
        #print(len(ans))
        if len(ans)==1:
            i+=1
            ind=pos[0]
            col=pos[1]
            data[col][ind]=ans[0]
            if jianyan(data)==False:
                #print('填入数据出错，已停止填写')
                flag_1=False
                break           
    if m == i:
        break             

#如果位置上只有多种可能，就使用fill_jilian（）填入data
j=0
m=0
flag_2=True
while(flag_2):

    if result_min_len(data)==0:
        #print('上一轮输入的数据有误')
        flag_2=False
    if jianyan(data)==False:
        #print('填入数据出错，已停止填写')
        flag_2=False
    m=j
    j=j+fill_pinlv(cla.result(data),data)
    if m == j:
        break

def labelinit(data):R=rule()label_list=[]for pos,ans in R.result(data):label_list.append([pos,ans,[None]*len(ans)])return label_listdef label_change_B(pos,ans,label_list):#label_list_copy=label_list.copy()for l in label_list:if l[0]==pos:for a in range(len(l[2])):l[2][a]=Falseif ans == l[1][a]:l[2][a]=Truereturndef label_change_A(pos,ans,label_list):#label_list_copy=label_list.copy()for l in label_list:if l[0]==pos:for a in range(len(l[2])):l[2][a]=Falseif ans == l[1][a]:l[2][a]=Falsereturndef label_rechange(data,label_list):try:#更新label_listfor ind,l in enumerate(label_list):if (None not in l[2]) and (True not in l[2]):#清空最后一行process_1=[None]*len(l[1])#上一行True后移一个单位process_2=label_list[ind-1][2]index=process_2.index(True)+1process_2.pop()process_2.insert(0,False)label_list[ind][2]=process_1label_list[ind-1][2]=process_2return Trueexcept:print('label_rechange 出错')print('请确认输入数据正确！！！')return Falsedef data_change(data,label_list):#根据label_list更新数据datatry:for l in label_list:if True in l[2]:pos=l[0]ans=l[1]marker=l[2]data[pos[1]][pos[0]]=ans[marker.index(True)]else:print('data 按照label假设完成')breakexcept:print('data_change 出错')def AB_test(data_copy):flag=None#AB判断（3种方向，1成功，2返回，3继续，）
flag_1=jianyan(data_copy)
flag_2=full(data_copy)
flag_3=result_min_len(data)
if flag_1==True:
    if flag_2==True:
        #1成功
        print('C:成功找到结果')
        print(data_copy)
        flag='C'
    if flag_2==False:
        if flag_3==0:
            #2返回
            print('A:遍历下一个ans')
            flag='A'
            #label_change(pos,ans,result_label_list)
        if flag_3>0:
            #3继续
            print('B:进入下一位置')
            flag='B'
            #label_change(pos,ans,result_label_list) 
if flag_1==False:
    #2返回
    print('A:遍历下一个ans')
    flag='A'
    #label_change(pos,ans,result_label_list)
return flag

def jiashe(data,label_list_array,lunci):data_copy=data.copy()R=result()
ans_list=label_list_array[lunci][1]
pos=label_list_array[lunci][0]

for ans in ans_list:
    #假设
    data_copy[pos[1]][pos[0]]=ans 
    #推导
    fill(data_copy,'result')
    fill(data_copy,'rule_')
    fill(data_copy,'rule_')
    label=AB_test(data_copy)

    if label=='B':
        #假设下一位置 重启假设函数
        label_change_B(pos,ans,label_list_array)
        return 'B'
    elif label=='A':
        #假设下一ans 遍历下一个ans
        label_change_A(pos,ans,label_list_array) 
    elif label=='C':
        #print('success')
        return data_copy

def jie(data,label_list_array):ind=0for i in range(10):    f_1=jiashe(data,label_list_array,ind)    if type(f_1)==pd.core.frame.DataFrame:
        return f_1

    f_2=label_rechange(data,label_list_array)
    data_change(data,label_list_array)
    ind+=1
    if f_2:
        ind-=1
        print('B：返回上一位置')
    if f_2==False:
        return False    #print(label_list_array[0:5])   def main(data):datacopy=data.copy()fill(data,'result')fill(data,'rule')label_list_array=label_init(data)shudu_jie=jie(data,label_list_array)print('原始数据')print(data_copy)print('结果是')print(shudu_jie)main(data)