欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

leetcode python 037 求解数独

程序员文章站 2022-03-12 18:48:22
import numpy as npimport syssys.setrecursionlimit(1000) #例如这里设置为一百万def get1(n): if n<3: return 0 if n<6: return 3 return 6def get2(n): if n<3: return ......

import numpy as np
import sys
sys.setrecursionlimit(1000) #例如这里设置为一百万

def get1(n):
    if n<3:
        return 0
    if n<6:
        return 3
    return 6

def get2(n):
    if n<3:
        return 3
    if n<6:
        return 6
    return 9

def get3(arr,i,j):
    a1=list(arr[i,:])
    a2=list(arr[:,j])
    a3=list(arr[get1(i):get2(i),get1(j):get2(j)].reshape(1,-1)[0])
    a=set(a1+a2+a3)
    return b-a

def sd(arr,dep):
    count[0]+=1
    if dep==len(l):
        result.append(arr)
    else:
        x,y=l[dep]
        lac=get3(arr,x,y)
        if len(lac)>0 and len(result)==0:        
            for i in lac:
                ac=arr.copy()
                ac[x,y]=i
                sd(ac,dep+1)
    
    
array= [[5,3,0,0,7,0,0,0,0],
        [6,0,0,1,9,5,0,0,0],
        [0,9,8,0,0,0,0,6,0],
        [8,0,0,0,6,0,0,0,3],
        [4,0,0,8,0,3,0,0,1],
        [7,0,0,0,2,0,0,0,6],
        [0,6,0,0,0,0,2,8,0],
        [0,0,0,4,1,9,0,0,5],
        [0,0,0,0,8,0,0,7,9]]
array=np.array(array)
b,l,old,result,count={1,2,3,4,5,6,7,8,9},[],[],[],[0]
for i in range(0,9):
    for j in range(0,9):
        if array[i,j]==0:
            l.append((i,j))
sd(array,0)
print(result)