Sudoku Solver, please help to solve a problem.

[AdithyaR]

Guys, I am trying to make a sudoku solver program which solves sudokus. I am inputting each cell values in the program itself inside a dictionary. Then, I run it through a sudcheck function to see which values are suitable for those blank cells. If only one value is possible, then that value will be taken by the cell. If more than 1 is possible, it starts to input values and checks if the resulting sudoku dictionary is correct.

You can see I have declared many global variables. count, fncount, mast and dc are 4 of them. In sudcheck, you can see me using count and dc to see if the possible values after each time the function is run is the same. If they are then, it will start to input possible values into cells. Similarly, I wanted to use fncount and mast in check9 function to store the sudoku matrix in mast each time it enters the check9 function.

The problem is that when I run the function, the values stored in mast global variable is changed. For example, when fncount =1, sudoku dictionary ma is stored in mast. When it is two, a sudoku dictionary different to the previous ma is stored in mast[2]. This is how it should run and it is how dc[count] runs in the sudcheck function. The problem is that mast[1] becomes mast[2] when fncount=2. Similarly it happens again in the successive times the function is called. Why? How can I solve it? please help.

# Online Python compiler (interpreter) to run Python online.
# Write Python 3 code in this online editor and run it.

global dc,count,gv,gvn,fncount,mast
fncount=1
count=1
mast={1:{1:['Test']}}
gv={}
gvn={}
dc={1:{1:['Test']}}
#print (dc)
def check9(n,ma):
    global fncount
    fncount=fncount+1
    macopy={}
    macopy=ma
    mast[fncount]=macopy
    print('fncount is',fncount)
    print('mast is',mast)
    elm=list(range(1,(n**2)+1))
    totalcount = 0
    for i in range(1,10):
        countrows={}
        for j in range(1,10):
            if ma[(i,j)] in elm:
                if (i,ma[(i,j)]) in countrows.keys():
                    countrows[(i,ma[(i,j)])]=countrows[(i,ma[(i,j)])]+1
                else:
                    countrows[(i,ma[(i,j)])]=1
        for k in countrows.values():
            if k!=1:
                totalcount=totalcount-1
                break
    totalcount=totalcount+1
    for i in range(1,10):
        countcolumns={}
        for j in range(1,10):
            if ma[(i,j)] in elm:
                if (ma[(i,j)],i) in countcolumns.keys():
                    countcolumns[(ma[(i,j)],i)]=countcolumns[(ma[(i,j)],i)]+1
                else:
                    countcolumns[(ma[(i,j)],i)]=1
        for k in countcolumns.values():
            if k!=1:
                totalcount=totalcount-1
                break            
    totalcount=totalcount+1
    ln=[]
    v=0
    v2=0
    for i in range(0,n+1):
        v2=(n*i)+1
        ln.append(v2)
    #print(ln)
    dc1={}
    for i in range(len(ln)):
        if i+1<(len(ln)):
            dc1[i+1]=[]
            for j in range(ln[i],ln[i+1]):
                dc1[i+1].append(j)
        else:
            break
    for i in dc1.values():
        for j in dc1.values():
            countboxes={}
            for k in range(n):
                for l in range(n):
                    if ma[(i[k],j[l])] in elm:
                        if (ma[(i[k],j[l])]) in countboxes.keys():
                            countboxes[(ma[(i[k],j[l])])]=countboxes[(ma[(i[k],j[l])])]+1
                        else:
                            countboxes[(ma[(i[k],j[l])])]=1
            for k in countcolumns.values():
                if k!=1:
                    totalcount=totalcount-1
                    break
    totalcount=totalcount+1
    if totalcount==3:
        return 'true'
    else:
        return 'false'

def sudcheck(n,ma):
    global count
    
    
    ln=[]
    v=0
    v2=0
    for i in range(0,n+1):
        v2=(n*i)+1
        ln.append(v2)
    #print(ln)
    dc1={}
    for i in range(len(ln)):
        if i+1<(len(ln)):
            dc1[i+1]=[]
            for j in range(ln[i],ln[i+1]):
                dc1[i+1].append(j)
        else:
            break
    #print(dc1)
    elm=list(range(1,(n**2)+1))
    #print(elm)
    dc2={}
    x,y=0,0
    for i in elm:
        for j in elm:
            if ma[(i,j)]!=0:
                continue
            else:
                lm=[]
                lmr=[]
                lmc=[]
                lm=lm+elm
                lmr=lmr+elm
                lmc=lmc+elm
                x,y=(i//n),(j//n)
                if i%n!=0:
                    x=x+1
                if j%n!=0:
                    y=y+1
                for p in dc1[x]:
                    for q in dc1[y]:
                        if ma[(p,q)]!=0:
                            lm.remove(ma[(p,q)])
                lmc.remove(j)
                for k in lmc:
                    if ma[(i,k)] in lm and ma[(i,k)]!=0:
                        lm.remove(ma[(i,k)])
                lmr.remove(i)
                for l in lmr:    
                    if ma[(l,j)]!=0 and ma[(l,j)] in lm:
                        lm.remove(ma[(l,j)])
                dc2[(i,j)]=lm
                if len(lm)==1 and ma[(i,j)]==0:
                    ma[(i,j)]=lm[0]
    print(dc2)
    #print (ma)
    count=count+1
    dc[count]=dc2
    #print ('dc is',dc)
    if dc[count-1]!=dc[count] and len(list(dc2.keys()))!=0:
        sudcheck(n,ma)
    elif dc[count-1]==dc[count] and len(list(dc2.keys()))!=0:
        global gv,gvn
        empl=[]
        print (count-1,'is equal to',count)
        print('dc2values is',dc2.values())
        if empl not in list(dc2.values()):
            dc2val=list(dc2.values())
            lnv=elm
            for i in dc2val:
                if len(i)<len(lnv)and len(i)>0 and i not in gv.values():
                    lnv=i
            for key,value in dc2.items():
                if lnv==value:
                    gin=key
                    break
        else:
            lnvalues=list(gv.values())
            lengv=len(gv.keys())
            lnv=lnvalues[lengv-1]
            ginlist=list(gv.keys())
            gin=ginlist[lengv-1]
        print('lnv is',lnv)
        print ('gin is',gin)
        
        gv[gin]=lnv
        print (gv)
        if gin in gvn.keys():
            for i in range((gvn[gin])+1,len(gv[gin])):
                ma[gin]=gv[gin][i]
                print (ma)
                chkr=check9(n,ma)
                print(chkr)
                if chkr=='true' and empl not in dc2.values():
                    print('oh boi')
                    sudcheck(n,ma)
                elif chkr=='true' and empl in dc2.values():
                    print('oh no boi')
                    print(gin)
                    #ma=mast[fncount-1]
                    ma[gin]=0
                    if i ==((len(lnv))-1) and len(gv.keys())>1:
                        del gv[gin],gvn[gin]
                        #inxn=list(gv.keys()).index(gin)
                        #gin2=list(gv.keys())[inxn-1]
                        #gvn[gin2]=gvn[gvn2]+1
                    sudcheck(n,ma)
                elif chkr=='false':
                    print('mast is',mast)
                    #ma=mast[fncount-1]
                    ma[gin]=0
                    print(ma)
                    if i ==((len(lnv))-1) and len(gv.keys())>1:
                        del gv[gin],gvn[gin]
                        #inxn=list(gv.keys()).index(gin)
                        #gin2=list(gv.keys())[inxn-1]
                        #gvn[gin2]=gvn[gvn2]+1
                    sudcheck(n,ma)
            
        else:
            for i in range(len(gv[gin])):
                ma[gin]=gv[gin][i]
                print(ma)
                gvn[gin]=i
                chkr=check9(n,ma)
                print (chkr)
                if chkr=='true' and empl not in dc2.values():
                    print('yeah boi')
                    sudcheck(n,ma)
                elif chkr=='true' and empl in dc2.values():
                    print('no boi')
                    #ma=mast[fncount-1]
                    ma[gin]=0
                    if i ==((len(lnv))-1) and len(gv.keys())>1:
                        del gv[gin],gvn[gin]
                        #inxn=list(gv.keys()).index(gin)
                        #gin2=list(gv.keys())[inxn-1]
                        #gvn[gin2]=gvn[gvn2]+1
                    sudcheck(n,ma)
                    #for j in range((gvn[gin2])+1,len(gv[gin2])):
                     #   ma[gin2]=gv[gin2][j]
                      #  chkrr=check9(n,ma)
                       # if chkrr=='true':
                        #    sudcheck(n,ma)
                        #else:
                         #   ma[gin2]=0
                          #  sudcheck(n,ma)
                elif chkr=='false':
                    
                    ma[gin]=0
                    print(ma)
                    if i ==((len(lnv))-1) and len(gv.keys())>1:
                        del gv[gin],gvn[gin]
                        #inxn=list(gv.keys()).index(gin)
                        #gin2=list(gv.keys())[inxn-1]
                        #gvn[gin2]=gvn[gvn2]+1
                    sudcheck(n,ma)
    elif len(list(dc2.keys()))==0:
        print (ma)
        return ma

        #if len(list(gv.keys()))<2:
            #check fn
         #   if check fn true -> 
        #return ma

#mtrx1={}
#m1=int(input("Enter number of rows in the first matrix:"))
#n1=int(input("Enter number of columns in the first matrix:"))
#for i in range(int(m1)):
#    for j in range(int(n1)):
#        print("Enter the value at position (",(i+1),",",(j+1),")")
#        v1=input()
#        mtrx1[(i+1,j+1)]=v1
#print(mtrx1)
mtrx1={(1,1):5,(1,2):8,(1,3):6,(1,4):0,(1,5):7,(1,6):0,(1,7):0,(1,8):0,(1,9):0,(2,1):0,(2,2):0,(2,3):0,(2,4):9,(2,5):0,(2,6):1,(2,7):6,(2,8):0,(2,9):0,(3,1):0,(3,2):0,(3,3):0,(3,4):6,(3,5):0,(3,6):0,(3,7):0,(3,8):0,(3,9):0,(4,1):0,(4,2):0,(4,3):7,(4,4):0,(4,5):0,(4,6):0,(4,7):0,(4,8):0,(4,9):0,(5,1):9,(5,2):0,(5,3):2,(5,4):0,(5,5):1,(5,6):0,(5,7):3,(5,8):0,(5,9):5,(6,1):0,(6,2):0,(6,3):5,(6,4):0,(6,5):9,(6,6):0,(6,7):0,(6,8):0,(6,9):0,(7,1):0,(7,2):9,(7,3):0,(7,4):0,(7,5):4,(7,6):0,(7,7):0,(7,8):0,(7,9):8,(8,1):0,(8,2):0,(8,3):3,(8,4):5,(8,5):0,(8,6):0,(8,7):0,(8,8):6,(8,9):0,(9,1):0,(9,2):0,(9,3):0,(9,4):0,(9,5):2,(9,6):0,(9,7):4,(9,8):7,(9,9):0}
#print(mtrx1)
solmtx={}
solmtx=sudcheck(3,mtrx1)
print("The solved Sudoku is",sudcheck(3,mtrx1))

Gribouillis write Oct-28-2021, 06:50 AM:
Please post all code, output and errors (it it's entirety) between their respective tags. Refer to BBCode help topic on how to post. Use the "Preview Post" button to make sure the code is presented as you expect before hitting the "Post Reply/Thread" button.

I fixed for you this time. Please use code tags on future posts.

[AdithyaR]

This is my first time posting here. I'm sorry about this. There is no error. The problem, as mentioned above, is that the sudoku dictionary I store in mast when fncount is 1, that is mast[1], changes when fncount is 2. mast[1] becomes mast[2], though I am not making the change. I have not written a statement to make this change. I don't understand why this happens.

[deanhystad]

in check9(n, ma), macopy is not a copy of ma, it is ma. If you want a copy of ma you should use:

macopy = ma.copy()

This line near the top of the file does nothing:

global dc,count,gv,gvn,fncount,mast

global tells python to use the global scope when assigning values to variables. This line, not being inside a function, is in the global scope already. Using "global" only makes sense inside of a function.

[bowlofred]

Your program is very hard to follow. It might be better to break some parts up into smaller bits.

It makes a lot of recursive calls. Do you do anything to make sure the recursion doesn't go too deep? There are only 81 cells, but when I tried running it it died with a recursion limit. I suspect you are making recursive calls that are either unnecessary or are not making progress.

I don't see any sign it's changing. I modified your print statement to become print('mast1 is {mast[1]}'. It never changed throughout the program.

Output:
fncount is 2
mast1 is {1: ['Test']}
...
fncount is 3
mast1 is {1: ['Test']}
...
...
fncount is 331
mast1 is {1: ['Test']}

[AdithyaR]

Your program is very hard to follow. It might be better to break some parts up into smaller bits.

It makes a lot of recursive calls. Do you do anything to make sure the recursion doesn't go too deep? There are only 81 cells, but when I tried running it it died with a recursion limit. I suspect you are making recursive calls that are either unnecessary or are not making progress.

I don't see any sign it's changing. I modified your print statement to become print('mast1 is {mast[1]}'. It never changed throughout the program.

Output:
fncount is 2
mast1 is {1: ['Test']}
...
fncount is 3
mast1 is {1: ['Test']}
...
...
fncount is 331
mast1 is {1: ['Test']}

Yes, mast[1] does not change. It changes from mast[2]. The reason the recursion does not stop is because, I have specified in sudcheck function to call check9 function and then do sudcheck again. I originally wanted to, if check9 is false, or da2.values() have an empty list in it [], to replace the wrong ma with the ma before we input that value. I wanted to do it by storing ma each time the function check9 is called as values to keys fncount. Meaning, if fncount is 5 and the function check9 returns false or dc2.values() contain [], meaning that the input value put inside a cell the previous time is wrong, it replaces ma with mast[fncount=4]. This means the effect of inputting that value will be cancelled. But mast[2] changes too when fncount is 3. Similarly, mast[3] changes when fncount is 4. For example, when fncount is 2, or the first time the check9 function is invoked, in the sudoku matrix, (1,4)=0 and (1,6)=0. you can see these 2 values. But the next time when fncount is 3, in mast[2], these values change. And because mast[2] becomes similar to mast[3], it still is the wrong sudoku dictionary and it keeps getting repeated. This is why there are many recursions. I want to know why. Thanks for your help. mast[1] doesn't change though.

[deanhystad]

When your key is an index, take that as a sign that you want a list. I don't think dictionaries are a good choice for mast, gv, gvn or dc. Turning these into lists eliminates the need for count and fncount.

You don't need to use global unless you want to assign a value to a global variable. In sutcheck() you declare gv and gvn to be global, but you never assign them. You modify their contents (they are dictionaries that should be lists), but gv and gvn always reference the dictionaries created at the start of the program.

check9() should return True or False, not 'true' or 'false'. The end of check9() should be:

return totalcount == 3