# -*- coding: utf-8 -*-
"""
Created on Wed Dec 28 12:19:37 2022

@author: s'wan

数独 v1,循环算法，同时调整候选集

"""
#%% import 
import numpy as np
from itertools import  combinations,product,permutations

#%% define

### 从文本解析九宫格
def parse(txt):
    #arr=np.array([[None]*9]*9)
    arr=np.zeros((9,9),'int8')
    for j,line in enumerate(txt.split('\n')):
        #print(j,line)
        if len(line)<9:
            continue
        for i in range(9):
            if line[i]!=' ':
                arr[j-1,i]=int(line[i])
    return arr

def is_error(arr):
    def __check_error(sub):
        u,c = np.unique(sub,return_counts=True)
        return len((np.where(c[np.where(u>0)[0]]>1)[0]))>0
    
    for r in range(9):
        if __check_error(arr[r]):
            return True
    #[__check_error(arr[r]) for r in range(9)]
    for c in range(9):
        if __check_error(arr[:,c]):
            return True
    #[__check_error(arr[:,c]) for c in range(9)]
    for g in range(9):
        rs,cs = divmod(g,3) 
        if __check_error(arr[rs*3:rs*3+3,cs*3:cs*3+3].reshape(-1)):
            return True
    return False

### 检查子集 是否合乎规则
def __check(sub):
    u = np.unique(sub)
    #return not (u[0]<1 or u[-1]>9 or len(u)!=9)
    return u[0]==1 and u[-1]==9 and len(u)==9

'''
[__check(row) for row in arr]
[__check(arr[:,c]) for c in range(9)]
for g in range(9):
      r,c = divmod(g,3)
      print(__check(arr[r*3:r*3+3,c*3:c*3+3]))
'''
### 检查大九宫 是否合乎规则
def is_done(arr):
    for row in arr:
        if not __check(row) :
            return False
    for c in range(9):
        if not __check(arr[:,c]) :
            return False
    for g in range(9):
        r,c = divmod(g,3)
        #print(arr[r*3:r*3+3,c*3:c*3+3])
        if not __check(arr[r*3:r*3+3,c*3:c*3+3]):
            return False
        
    return True

__count=lambda sub,val: sum(sub.reshape(-1)==0)
__has=lambda sub,val: sum(sub.reshape(-1)==0) > 0

### 子集（行，列，宫） 缺的数字
def absence(sub):
    u = np.unique(sub)
    return list(set(range(1,10)).difference(u[u>0]))

### 计算 每格 候选集
univer = set(range(1,10))
def candidate_set(arr):
    may=np.full((9,9),None)
    for r in range(9):
        for c in range(9):
            if arr[r,c]==0:
                rr,cc = int(r/3),int(c/3)
                '''p1=absence(arr[r])
                p2=absence(arr[:,c])
                p3=absence(arr[rr*3:rr*3+3,cc*3:cc*3+3])
                #print(r,c,list(set(p1).intersection(p2).intersection(p3)))
                #may[r,c]=list(set(p1).intersection(p2).intersection(p3))
                may[r,c]=set(p1).intersection(p2).intersection(p3)'''
                may[r,c]=univer.difference(set(arr[r]).union(arr[:,c]).union(arr[rr*3:rr*3+3,cc*3:cc*3+3].reshape(-1)))
    return may

'''
may=candidate_set(arr)
'''

### 对于只有一个候选数的格子，其他格子不能候选此数
def exclude_1(sub): # t--candidate 候选各数
    ### 统计 格子的候选数量
    cell_val_counts=np.array([len(s) if isinstance(s,set) else 0 for s in sub])
    
    # 检查 只有一个候选数的格子
    check_cells = np.where(cell_val_counts==1)[0]
    for cell in check_cells:
        for other_cell in range(9):
            if other_cell!=cell and isinstance(sub[other_cell],set): # 这个数其他格子不能候选
                sub[other_cell]=sub[other_cell].difference(sub[cell])
                #print(cell,other_cell,sub[other_cell],sub[other_cell].difference(sub[cell]))

    return len(check_cells)


'''
摒除法,只出现一次的数字，是所在格唯一候选数
2.基础摒除法，隐性唯一候选数法
'''
def exclude_hide_1(sub): 
    ### 统计 各数字被候选次数
    val_counts=np.array([sum([v in s for s in sub if isinstance(s,set)]) for v in range(1,10)])
    
    # 只被候选一次的数字所在的格，仅候选此数
    check_vals=np.where(val_counts==1)[0] + 1 # 只出现一次的数字
    val_cell={val:np.where([val in s if isinstance(s,set) else False for s in sub])[0] for val in check_vals}
    for val,cell in val_cell.items():
        sub[cell]=set([val])

    return len(check_vals)

###三链数(2,3,4,...) 删减法：子集（行列宫）的某3个格候仅候选某3个数，则其他格不能选此3数    
### n格仅候选n个数，但其他格可能也候选这n个数 #####
def exclude_n(sub,no=3): 
    ### 候选个数 >1 且 <=no 的 格子集合
    check_cells=np.array([cell for cell in range(9) if isinstance(sub[cell],set) and len(sub[cell])>1 and len(sub[cell])<=no])
    
    count=0
    ### N 个格子，no个一组，全部的组合
    for cell_comb in combinations(check_cells,no): # 格子的组合
        val_union=set() # 格子组合候选数字并集
        for cell in cell_comb:   
            val_union=val_union.union(sub[cell]) # 格子组合候选数字并集

        if len(val_union)==no: # 并集 大小 正好是 格子数
            for cell in range(9):
                if cell not in cell_comb and isinstance(sub[cell],set): # 其他格子 不能 候选这几个数
                    #print(cell,sub[cell],val_union,sub[cell].difference(val_union))
                    sub[cell]=sub[cell].difference(val_union)
                    #pass
            count+=1

    return count


### 隐性三链数(2,3,4,...)删减法：某3个数仅出现在子集（行列宫）的某3个格候选集，则此3格不能选其他数
### n个数仅被n格候选，但n格可能还候选别的数 #####
def exclude_hide_n(sub,no=3):
    ### 统计 数字候选次数
    val_counts=np.array([sum([val in s for s in sub if isinstance(s,set)]) for val in range(1,10)])
      
    check_vals=np.where(list(map(lambda val:val>1 and val<=no,val_counts)))[0] + 1 ### 出现次数 大于1且小于等于no 的数
    if len(check_vals) < no: ### 至少要no个数
        return 0
    
    # 存储 候选 每个数 的格子
    val_cell={val:np.where([val in s if isinstance(s,set) else False for s in sub])[0] for val in check_vals}
        
    ### N 个数字，3个组合，全部的组合数
    count=0
    for val_comb in combinations(check_vals,no):
        cell_union=set() # 组合各数出现位置的并集
        for val in val_comb:
            cell_union=cell_union.union(val_cell[val])
        
        if len(cell_union)==no: # 出现的位置数正好是数字个数
            ext = set(range(1,10)).difference(val_comb) # 格需要排除的候选数字
            for cell in range(9):
                if cell in cell_union and isinstance(sub[cell],set):
                    sub[cell]=sub[cell].difference(ext) # 此no格只候选此no数
                    #print(val_comb,cell_union,sub[cell],sub[cell].difference(ext))
                    
            count+=1
            
    return count
    
'''
for r in range(9):
    #print('exclude_1c',r, exclude_1c(may[r])) # 格只有一个候选
    print('exclude_1t',r, exclude_1t(may[r]))  # 数只出现一次
    #print('exclude_2',r, exclude_n(may[r],2))
    #print('exclude_hide_2',r, exclude_hide_n(may[r],2))
    #print('exclude_3',r, exclude_n(may[r],3))
    print('exclude_hide_3',r, exclude_hide_n(may[r],3))
    
for c in range(9):
    #print('exclude_1c',c, exclude_1c(may[:,c])) # 格只有一个候选
    #print('exclude_1t',c, exclude_1t(may[:,c]))  # 数只出现一次
    #print('exclude_2',c, exclude_n(may[:,c],2))
    print('exclude_hide_2',c, exclude_hide_n(may[:,c],2))
    #print('exclude_3',c, exclude_n(may[:,c],3))
    print('exclude_hide_3',c, exclude_hide_n(may[:,c],3))
    
for g in range(9):
    rs,cs = divmod(g,3) 
    sub=may[rs*3:rs*3+3,cs*3:cs*3+3].reshape(-1)
    #print('exclude_1c',g, exclude_1c(sub)) # 格只有一个候选
    #print('exclude_1t',g, exclude_1t(sub))  # 数只出现一次
    #print('exclude_2',g, exclude_n(sub,2))
    #print('exclude_hide_2',g, exclude_hide_n(sub,2))
    print('exclude_3',g, exclude_n(sub,3))
    print('exclude_hide_3',g, exclude_hide_n(sub,3))
    
'''

### 3.区块摒除法  
### 若某行（列）块确定候选某数，则同行(列)其他行（列）块 不能 候选此数

### 擦g之外其他宫的候选
def erase_row_candidate(may,row,gong,val):
    #print('erase_row_candidate',row,gong,val)
    for g in set(range(3)).difference([gong]):
        for col in range(g*3,g*3+3): #所有同行格
            if isinstance(may[row,col],set):
                may[row,col]=may[row,col].difference([val]) # val不再候选
                
def erase_col_candidate(may,col,gong,val):
    #print('erase_col_candidate',col,gong,val)
    for g in set(range(3)).difference([gong]):
        for row in range(g*3,g*3+3): #所有同列格
            if isinstance(may[row,col],set):
                may[row,col]=may[row,col].difference([val]) # val不再候选
                
def exclude_block(arr,may):
    count=0
    for s in range(0,9,3):
        # 统计3行的所有已填数
        vals= np.unique(list(filter(lambda v:v>0,arr[s:s+3].reshape(-1))))
        # 遍历每个数
        for val in vals:
            #   1 确定所在块的 宫位置
            pos=np.where(arr[s:s+3]==val) # pos[0] 所在行,pos[1]所在列
            on_gongs = np.int8(np.floor(pos[1]/3)) # 所在宫
            
            # 要检查的 行 和 宫
            rows = list(set(list(range(s,s+3))).difference(pos[0]+s))
            gongs = list(set(list(range(3))).difference(on_gongs))
            if len(gongs)==1: # 只需处理1宫
                erase_row_candidate(may,rows[0],gongs[0],val)                
                count+=1
                
            elif len(gongs)==2: # 2宫，看有没有某宫可定：只有宫的某块填！！！！
                status = [(r,g,np.all(list(map(lambda v:v is None,may[r,g*3:g*3+3])))) for r,g in product(rows,gongs)]
                filled = np.where(list(map(lambda t: t[2],status)))[0] ### 已填的块 
                for i in filled:
                    other_same_gong = np.where(list(map(lambda t: t[1]==status[i][1] and t[0]!=status[i][0],status)))[0][0]
                    erase_row_candidate(may,status[other_same_gong][0],status[other_same_gong][1],val)
                    count+=1
                    
                    other_same_line = np.where(list(map(lambda t: t[1]!=status[i][1] and t[0]==status[i][0],status)))[0][0]
                    erase_row_candidate(may,status[other_same_line][0],status[other_same_line][1],val)
                    count+=1
                    
    for s in range(0,9,3):
        # 统计3列的所有已填数
        vals= np.unique(list(filter(lambda v:v>0,arr[:,s:s+3].reshape(-1))))
        # 遍历每个数
        for val in vals:
            #   1 确定所在块的 宫位置
            pos=np.where(arr[:,s:s+3]==val) # pos[0] 所在行,pos[1]所在列
            on_gongs = np.int8(np.floor(pos[0]/3)) # 所在宫
            
            # 要检查的 列 和 宫
            cols = list(set(list(range(s,s+3))).difference(pos[1]+s))
            gongs = list(set(list(range(3))).difference(on_gongs))
            if len(gongs)==1: # 只需处理1宫
                erase_col_candidate(may,cols[0],gongs[0],val)
                count+=1
                
            elif len(gongs)==2: # 2宫，看有没有某宫可定：只有宫的某块填！！！！
                status = [(c,g,np.all(list(map(lambda v:v is None,may[g*3:g*3+3,c])))) for c,g in product(cols,gongs)]
                filled = np.where(list(map(lambda t: t[2],status)))[0] ### 已填的块 
                for i in filled:
                    other_same_gong = np.where(list(map(lambda t: t[1]==status[i][1] and t[0]!=status[i][0],status)))[0][0]
                    erase_col_candidate(may,status[other_same_gong][0],status[other_same_gong][1],val)
                    count+=1
                    
                    other_same_line = np.where(list(map(lambda t: t[1]!=status[i][1] and t[0]==status[i][0],status)))[0][0]
                    erase_col_candidate(may,status[other_same_line][0],status[other_same_line][1],val)
                    count+=1
    
    return count
                    
'''
块排斥法：某数只被宫内某行(列)候选，则该行其他宫不能候选此数
'''
def union_set(sub):
    un=set()
    for s in sub:
        if isinstance(s,set):
            un=un.union(s)
    return un

def repel_block(arr,may):
    for rg in range(3):
        for cg in range(3):
            row_cand=[union_set(may[row,cg*3:cg*3+3]) for row in range(rg*3,rg*3+3)]
            diff_union = {i+rg*3:row_cand[i].difference(row_cand[j].union(row_cand[k])) for i,j,k in permutations(range(3))}
            for row,s in diff_union.items():
                '''if len(s)>0:###
                    print('repel_row',rg,cg,row,s)'''
                if len(s)==1:
                    #print('repel_row',rg,cg,row,s)
                    erase_row_candidate(may,row,cg,list(s)[0])
                    
            col_cand=[union_set(may[rg*3:rg*3+3,col]) for col in range(cg*3,cg*3+3)]
            diff_union = {i+cg*3:col_cand[i].difference(col_cand[j].union(col_cand[k])) for i,j,k in permutations(range(3))}
            for col,s in diff_union.items():
                '''if len(s)>0:###
                    print('repel_col',rg,cg,col,s)'''
                if len(s)==1:
                    #print('repel_col',rg,cg,col,s)
                    erase_col_candidate(may,col,rg,list(s)[0])
    

### 5.矩形摒除法（矩形顶点删减法）
### 某两列（行）仅在相同行（列）可取某数，则这两行（列）其他格不能取此数
### 三链列（行）删减法 --矩形删减法扩展

def intersection(k_kv,ks):
    its=set(range(9))
    for k in ks:
        its = its.intersection(k_kv[k].keys())
    return its

def set_equal(k_kv,rows,val):
    for row in rows[1:]:
        if k_kv[rows[0]][val] != k_kv[row][val]:
            return False
    return True
    
def exclude_rectangle(arr,may,no=2):
    count=0
    ## 计算各行 被选2次的数字所在位置
    rows_v2ps=[]
    for row in range(9):
        v2ps={val:{col for col in range(9) if isinstance(may[row,col],set)  and val in may[row,col]} \
              for val in  range(1,10) if val not in arr[row]}
        rows_v2ps.append({v:ps for v,ps in v2ps.items() if len(ps)==no})
    rows_v2ps={row:v2ps for row,v2ps in enumerate(rows_v2ps) if len(v2ps)>0}
    
    ## 寻找 数字 与 位置 都相同的 行对
    '''for r1,r2 in combinations(rows_v2ps, 2):
        jiaoji = set(rows_v2ps[r1].keys()).intersection(rows_v2ps[r2].keys())
        for val in jiaoji:
            if rows_v2ps[r1][val] == rows_v2ps[r2][val]:
                print('row',{r1,r2},val,rows_v2ps[r1][val])
                ### 从两列的其他候选 删除 该值
                for col in rows_v2ps[r1][val]:
                    for row in range(9):
                        if row not in (r1,r2) and isinstance(may[row,col],set):
                            may[row,col]=may[row,col].difference([val])'''
    for rows in combinations(rows_v2ps, no):
        jiaoji = intersection(rows_v2ps,rows)
        for val in jiaoji:
            if set_equal(rows_v2ps,rows,val):
                #print('row',rows,val,rows_v2ps[rows[0]][val])
                ### 从两列的其他候选 删除 该值
                for col in rows_v2ps[rows[0]][val]:
                    for row in range(9):
                        if row not in rows and isinstance(may[row,col],set):
                            may[row,col]=may[row,col].difference([val])
                count+=1
                            
    ## 计算各列 被选2次的数字所在位置
    cols_v2ps=[]
    for col in range(9):
        v2ps={val:{row for row in range(9) if isinstance(may[row,col],set)  and val in may[row,col]} \
              for val in  range(1,10) if val not in arr[:,col]}
        cols_v2ps.append({v:ps for v,ps in v2ps.items() if len(ps)==no})
    cols_v2ps={col:v2ps for col,v2ps in enumerate(cols_v2ps) if len(v2ps)>0}
    
    ## 寻找 数字 与 位置 都相同的 列对
    '''for c1,c2 in combinations(cols_v2ps, 2):
        jiaoji = set(cols_v2ps[c1].keys()).intersection(cols_v2ps[c2].keys())
        for val in jiaoji:
            if cols_v2ps[c1][val] == cols_v2ps[c2][val]:
                print('col',{c1,c2},val,cols_v2ps[c1][val])
                ### 从两行的其他候选 删除 该值
                for row in cols_v2ps[c1][val]:
                    for col in range(9):
                        if col not in (c1,c2) and isinstance(may[row,col],set):
                            may[row,col]=may[row,col].difference([val])'''
    for cols in combinations(cols_v2ps, no):
        jiaoji = intersection(cols_v2ps,cols)
        for val in jiaoji:
            if set_equal(cols_v2ps,cols,val):
                #print('col',cols,val,cols_v2ps[cols[0]][val])
                ### 从两列的其他候选 删除 该值
                for row in cols_v2ps[cols[0]][val]:
                    for col in range(9):
                        if col not in cols and isinstance(may[row,col],set):
                            may[row,col]=may[row,col].difference([val])
                count+=1
    return count

### 多数字 链摒除
def exclude_link(sub):
    count =  exclude_1(sub)        # 1链 摒除
    count += exclude_hide_1(sub)   # 隐性1链 摒除
    
    count += exclude_n(sub,2)      # 2链 摒除
    count += exclude_hide_n(sub,2) # 隐性2链 摒除
    
    count += exclude_n(sub,3)      # 3链 摒除
    count += exclude_hide_n(sub,3) # 隐性3链 摒除
    
    count += exclude_n(sub,4)      # 4链 摒除
    count += exclude_hide_n(sub,4) # 隐性4链 摒除
    
    return count

### 总搜寻
def search(arr):
    may=candidate_set(arr)
    repel_block(arr,may) # 寻找区块以摒除
    
    for r in range(9):
        sub=may[r]
        exclude_link(sub)
        #print('row',r,exclude_link(sub))
        may[r]=sub
    
    for c in range(9):
        sub=may[:,c]
        exclude_link(sub)
        #print('col',c,exclude_link(sub))
        may[:,c]=sub
        
    for g in range(9):
        rs,cs = divmod(g,3) 
        sub=may[rs*3:rs*3+3,cs*3:cs*3+3].reshape(-1)
        exclude_link(sub)
        #print('gong',g,exclude_link(sub))
        may[rs*3:rs*3+3,cs*3:cs*3+3] = sub.reshape(3,3)
        
    exclude_block(arr,may) # 划分区块以摒除
    exclude_rectangle(arr, may,2) # 矩形摒除
    exclude_rectangle(arr, may,3) # 三连行（列）摒除
    #exclude_rectangle(arr, may,4)
    
    count=0
    for r in range(9):
        for c in range(9):
            if isinstance(may[r,c],set) and len(may[r,c])==1:
                arr[r,c]=list(may[r,c])[0]
                count+=1
    return count

'''
count=81
while count>0 and not is_done(arr):
#while not is_done(arr):
    count = search(arr)
    print(count)
    
np.array([[len(may[r,c]) if isinstance(may[r,c],set) else None  for c in range(9)] for r in range(9)])

'''
    
#%% usage

### 2,001
txt="""
 61 3  2 
 5   81 7
     7 34
  9  6378
  32795  
57 3  9 2
19 76    
8 24  76 
64  1 25 
"""
arr=parse(txt)

### 3,001 能解
arr=np.array([
    [8,1,5, 0,0,0, 0,0,0],
    [0,0,0, 9,0,0, 0,0,7],
    [0,3,7, 0,0,0, 1,0,8],
    
    [0,0,0, 0,9,0, 7,0,6],
    [0,4,0, 0,5,0, 0,1,0],
    [3,0,2, 0,1,0, 0,0,0],
    
    [1,0,9, 0,0,0, 3,4,0],
    [2,0,0, 0,0,6, 0,0,0],
    [0,0,0, 0,0,0, 6,5,1],
    ])

### 6,001, 不能解，中间 人工 置数 可解；答案唯一；这类问题如何破局？？
arr=np.array([
    [0,0,1, 3,5,0, 0,0,0],
    [0,3,0, 0,0,7, 0,0,0],
    [5,0,0, 0,0,0, 9,0,0],
    
    [7,0,0, 2,0,0, 4,0,0],
    [9,0,0, 0,0,0, 6,0,0],
    [0,2,0, 0,0,8, 0,0,7],
    
    [0,0,4, 6,8,0, 1,0,2],
    [0,0,0, 0,0,0, 0,8,0],
    [0,0,0, 0,0,4, 3,0,0],
    ])

'''
search(arr)
search(arr)
search(arr)

arr[0,6]=2 # 8 # 
或
arr[8,8]=5
或
arr[5,2]=3 #6 #  都走不动，不是关键点

is_error(arr)
is_done(arr)
'''
### 6,091 能解
arr=np.array([
    [1,0,0, 5,0,0, 0,9,0],
    [0,0,3, 0,4,0, 0,0,6],
    [0,0,0, 0,0,0, 0,3,0],
    
    [0,6,0, 0,0,7, 0,0,0],
    [4,0,9, 0,0,0, 8,0,5],
    [0,0,0, 6,0,0, 0,2,0],
    
    [0,9,0, 0,0,0, 0,0,0],
    [2,0,0, 0,5,0, 1,0,0],
    [0,4,0, 0,0,3, 0,0,8],
    ])
### 9,001 能解
arr=np.array([
    [0,7,0, 4,0,0, 6,0,2],
    [0,0,4, 0,9,0, 0,0,0],
    [1,0,0, 0,2,5, 0,0,0],
    
    [6,0,5, 0,0,0, 4,1,0],
    [0,0,7, 0,8,4, 0,6,5],
    [4,0,2, 0,0,0, 7,8,0],
    
    [8,0,0, 0,7,2, 0,0,0],
    [0,0,6, 0,4,0, 0,0,0],
    [0,9,0, 8,0,0, 1,0,4],
    ])
### 9,050 能解
arr=np.array([
    [0,0,1, 0,2,0, 0,0,0],
    [9,8,0, 0,0,0, 2,0,0],
    [0,0,0, 4,0,0, 6,0,0],
    
    [0,0,5, 0,0,2, 9,0,0],
    [0,4,0, 0,8,0, 5,0,6],
    [8,0,0, 0,0,0, 0,0,0],
    
    [0,0,3, 5,0,4, 0,0,1],
    [0,6,2, 0,0,0, 0,4,0],
    [0,0,0, 0,1,0, 0,0,0],
    ])
### 10,050, 能解
arr=np.array([
    [0,0,0, 0,0,0, 0,0,0],
    [0,3,8, 5,0,0, 4,1,0],
    [0,6,0, 7,0,0, 0,2,0],
    
    [0,0,0, 8,0,5, 3,4,0],
    [0,0,0, 0,9,0, 0,0,0],
    [0,1,7, 6,0,2, 0,0,0],
    
    [0,5,0, 0,0,3, 0,6,0],
    [0,7,2, 0,0,1, 5,8,0],
    [0,0,0, 0,0,0, 0,0,0],
    ])

### 10,101 能解
arr=np.array([
    [1,0,0, 4,0,0, 0,0,5],
    [0,2,3, 0,0,0, 0,6,0],
    [0,0,0, 0,0,8, 0,7,0],
    
    [0,0,9, 0,5,0, 0,0,1],
    [0,0,0, 6,0,7, 0,0,0],
    [5,0,0, 0,2,0, 4,0,0],
    
    [0,3,0, 9,0,0, 0,0,0],
    [0,4,0, 0,0,0, 3,2,0],
    [7,0,0, 0,0,6, 0,0,9],
    ])

### 网上 单元摒除法
arr=np.array([
    [8,0,0, 0,9,2, 0,0,0],
    [5,0,0, 0,3,0, 0,6,0],
    [0,1,0, 0,0,0, 0,9,0],
    
    [0,8,0, 0,7,0, 0,0,0],
    [0,0,9, 0,0,0, 0,8,2],
    [0,0,5, 0,2,0, 0,4,0],
    
    [6,0,3, 5,0,0, 4,0,0],
    [0,0,0, 1,0,0, 0,0,7],
    [0,0,0, 0,0,7, 9,0,0],
    ])

#%% old code

### {{ 野路子
def findSameSet(sub):
    cnt = len(sub)
    for i in range(cnt-1):
        if sub[i] is None:
            continue
        for j in (range(i+1,cnt)):
            if sub[j] is None:
                continue
            if sub[i]==sub[j]:
                return i,j
    return None,None

def DiffSame2_Rest1(sub):
    a,b = findSameSet(sub) # 有相同候选集
    if not a is None:
        equalSet=sub[a]
        if len(equalSet)==2: # 相同候选集 因素个数是2
            for i,ss in enumerate(sub):
                if isinstance(ss,list) and i != a and i != b: # 相同候选集之外的 候选集
                    tmp=list(set(ss).difference(equalSet))
                    if len(tmp)==1: # 刨除相同候选集的元素，只剩一个元素
                        return i,tmp[0]
    return None,None
### 野路子}}

### 某数只出现在一个候选集中，则该单元就是次数
def onlyOne(sub):
    counts=np.array([sum([v in s for s in sub if isinstance(s,list)]) for v in range(1,10)])
    pos=np.where(counts==1)[0]
    res=[]
    for p in pos:
        v=p+1
        i=np.where([v in s if isinstance(s,list) else False for s in sub])[0][0]
        res.append((i,v))
    return res
'''
for r in range(9):
    print(r,len( onlyOne(may[r])))
for c in range(9):
    print(c,len( onlyOne(may[:,c])))
for g in range(9):
    rs,cs = divmod(g,3) 
    print(g,len( onlyOne(may[rs*3:rs*3+3,cs*3:cs*3+3].reshape(-1))))
'''

def search(arr):
                
    count=0
    for r in range(9):
        for c in range(9):
            if isinstance(may[r,c],list) and len(may[r,c])==1:
                arr[r,c]=may[r,c][0]
                count+=1
    '''if count > 0:
        return count
    '''
    '''
    stat=np.array([[len(may[r,c]) if isinstance(may[r,c],set) else None  for c in range(9)] for r in range(9)])
    pos=np.where(stat==2)
    [(x,y,may[x,y]) for x,y in zip(pos[0],pos[1])]
    '''
    for r in range(9):
        res=onlyOne(may[r])
        for t in res:
            arr[r,t[0]]=t[1]
            count+=1
        '''c,val = DiffSame2_Rest1(may[r])
        if not c is None:
           arr[r,c] = val
           count+=1'''
                
    for c in range(9):
        res=onlyOne(may[:,c])
        for t in res:
            arr[t[0],c]=t[1]
            count+=1
        '''r,val = DiffSame2_Rest1(may[:,c])
        if not r is None:
           arr[r,c] = val
           count+=1'''

    for g in range(9):
        rs,cs = divmod(g,3)
        res=onlyOne(may[rs*3:rs*3+3,cs*3:cs*3+3].reshape(-1))
        for t in res:
            rr,cc = divmod(t[0],3) # 宫内位置
            r,c = rs*3+rr,cs*3+cc
            arr[r,c]=t[1]
            count+=1
        '''rs,cs = divmod(g,3)        
        p,val = DiffSame2_Rest1(may[rs*3:rs*3+3,cs*3:cs*3+3].reshape(-1))
        if not p is None:            
            rr,cc = divmod(p,3) # 宫内位置
            r,c = rs*3+rr,cs*3+cc
            arr[r,c] = val
            count+=1'''
    
    return count
    
count=81
while count>0 and not check(arr):
#while not check(arr):
    count = search(arr)
    print(count)
    
check(arr)