Join the social network of Tech Nerds, increase skill rank, get work, manage projects...
 
  • Remove Function Not Working in Code That Solves Sudoku in Python

    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 12
    Answer it

    I have been trying to write a code to solve sudoku. This method basically involves finding the empty elements in the list of input, then filling the empty elements with the possible values that can be used in that box by deleting the values present in row, column or a box. Then I have tried using the method of backtracking to solve using each and every value present in the list. Moreover I believe that the remove function is not working as it should have because if it had worked correctly then the value 8 should not have been there in the list in a[1][2].

     

    def print_grid(arr):
        for i in range(9):
            for j in range(9):
                print arr[i][j],
            print ('\n')

    def emptyLoc(a):
        l=[0,0]
        for i in range(9):
            for j in range(9):
                if(a[i][j]==0):
                    a[i][j] = [1,2,3,4,5,6,7,8,9]
                    l[0] = i
                    l[1] = j
        return l

    def remove(a):
        for i in range(9):
            for j in range(9):
                    if type(a[i][j]) == list :
                                      x = a[i][j]
                            for k in x:
                                    for l in range(9):
                                        if(k == a[i][l]):
                                                x.remove(k)

        for i in range(9):
            for j in range(9):
                            if type(a[i][j]) == list:
                                x = a[i][j]
                            for k in x:
                                    for l in range(9):
                                        if(k == a[l][j]):
                                                x.remove(k)

        for i in range(9):
            for j in range(9):
                        if type(a[i][j]) == list:
                            x = a[i][j]
                            for k in x:
                                    for l in range(3):
                                        for m in range(3):
                                                if(k == a[l+i-(i%3)][m+j-(j%3)]):
                                                    x.remove(k)

        return a

    def solver(arr):
        newArr = emptyLoc(arr)
        finalArr = remove(arr)

        #Changing One element lists to that single element
        for i in range(9):
            for j in range(9):
                        if type(arr[i][j]) == list and len(arr[i][j]) == 1:
                                arr[i][j] = arr[i][j][0]

        for i in range(9):
            for j in range(9):
                        if not(type(arr[i][j]) == list):
                            return True
                        else :
                            for num in arr[i][j]:
                                    store = arr[i][j]
                                    arr[i][j] = num
                                    if (solver(arr) == True):
                                        return True
                                    else :
                                        arr[i][j] = store
                            return False


    if __name__ == "__main__":
        grid=[[3,0,6,5,0,8,4,0,0],
            [5,2,0,0,0,0,0,0,0],
            [0,8,7,0,0,0,0,3,1],
            [0,0,3,0,1,0,0,8,0],
            [9,0,0,8,6,3,0,0,5],
            [0,5,0,0,9,0,6,0,0],
            [1,3,0,0,0,0,2,5,0],
            [0,0,0,0,0,0,0,7,4],
            [0,0,5,2,0,6,3,0,0]]


        if(solver(grid)):
            print_grid(grid)
        else:
            print "No solution exists"

     

    I dont understand where I am basically going wrong with the code as I recieve an un-backtracked answer. This is the expected output 

    3 1 6 5 7 8 4 9 2 
    5 2 9 1 3 4 7 6 8 
    4 8 7 6 2 9 5 3 1 
    2 6 3 4 1 5 9 8 7 
    9 7 4 8 6 3 1 2 5 
    8 5 1 7 9 2 6 4 3 
    1 3 8 9 4 7 2 5 6 
    6 9 2 3 5 1 8 7 4 
    7 4 5 2 8 6 3 1 9 

    but I am getting this as an output

    3 [1, 4, 7, 9] 6 5 [2, 4, 7] 8 4 [2, 6, 9] [2, 6, 7, 9] 
    5 2 [1, 4, 8, 9] [1, 3, 4, 6, 7, 9] [3, 4, 7] [1, 4, 7, 9] [4, 7, 8, 9] [4, 6, 8, 9] [6, 7, 8, 9] 
    [4, 8] 8 7 [4, 6, 9] [2, 4, 8] [2, 4, 8, 9] [5, 8, 9] 3 1 
    [2, 4, 6, 7] [4, 6, 7] 3 [4, 7] 1 [2, 4, 5, 7] [4, 7, 9] 8 [2, 6, 7, 9] 
    9 [1, 4, 6, 7] [1, 2, 4, 7] 8 6 3 [1, 4, 7, 9] [1, 2, 4, 9] 5 
    [2, 4, 6, 7, 8] 5 [1, 2, 4, 7, 8] [3, 4, 7] 9 [2, 4, 7] 6 [1, 2, 4, 8] [2, 3, 7] 
    1 3 [2, 4, 7, 8, 9] [4, 7, 9] [4, 7, 8] [4, 7, 9] 2 5 [6, 8, 9] 
    [2, 6, 8] [3, 6, 9] [2, 8, 9] [1, 3, 9] [3, 5, 8] [1, 5, 8, 9] [1, 5, 8, 9] 7 4 
    [4, 6, 7, 8] [4, 6, 7, 9] 5 2 [3, 4, 7, 8] 6 3 [1, 6, 8, 9] [6, 8, 9] 

    Somebody please help me with this. Thank You !!!


     

 0 Answer(s)

Sign In
                           OR                           
                           OR                           
Register

Sign up using

                           OR                           
Forgot Password
Fill out the form below and instructions to reset your password will be emailed to you:
Reset Password
Fill out the form below and reset your password: