Python continuously updating array

Question

I wrote a simple backtracking algorithm in python to solve sudoku's, and for a while had difficulty because it seemed to update an array that should not have been updated, which caused the entire program to backup.

Essentially, as part of the code, I stored an array of the initial values and then made a copy of the array so that when I was backtracking and assigning new values, I didn't change any of the numbers that were given in the original sudoku. However, in the process I somehow updated my array of initial numbers. I eventually figured out it was being caused by the line grid=initial, which should have set my working grid (grid) to the initial values (initial) but was only called at the start of the program. When I took that line out and manually assigned grid to the same thing as initial (via copy/paste), the program worked fine.

I've included my full code below, anybody know why that line may have been getting called again? I can't figure it out.

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

#The following line used to be grid=initial

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


def printBoard(grid):
    for i in range(0,8):
        print(grid[i])

def checkValidity(num,row,col):
    if num in grid[row]:
        return False


    for i in range(0,8):
        if grid[i][col]==num:
            return False


    cageRow=row//3
    cageCol=col//3
    for i in range(0,3):
        if num in grid[3*cageRow+i][3*cageCol:3*cageCol+3]:
            return False


    return True

def nextCell(row,col,backtrack):
    if backtrack==0:
        if col==8:
            row+=1
            col=0
        else:
            col+=1
    else:
        if col==0:
            row-=1
            col=8
        else:
            col-=1
    if row<0:
        print("Error: Backtracked too far.")
    return (row,col)

def findNewNumber(row,col,num,backtrack):
    for i in range(num+1,10):
        if checkValidity(i,row,col):
            return (i,0)
    return (0,1)


row=0
col=0
backtrack=0
print("Solving...")

while row<9:
    if grid[row][col]==initial[row][col] and initial[row][col]!=0:
        [row,col]=nextCell(row,col,backtrack)
    else:
        num=grid[row][col]
        grid[row][col]=99
        [num,backtrack]=findNewNumber(row,col,num,backtrack)
        grid[row][col]=num
        [row,col]=nextCell(row,col,backtrack)

print("Solved!")
printBoard(initial)
print("")
printBoard(grid)

cmd · Accepted Answer · 2014-05-22 21:45:35Z

4

grid = initial
id(initial) == id(grid)
>>> True

This doesn't set grid to the same values as initial. It makes grid refer to the same object as initial. What people commonly do is make a shallow copy, like this

grid = initial[:]
id(initial) == id(grid)
>>> False

This will not work in your case though. It would create a new outer list that will hold the same interior lists.

id(initial[0]) == id(grid[0])
>>> True

What you need is a deepcopy to get copies of the interior lists as well.

import copy

grid = copy.deepcopy(initial)

then everything is copied

id(initial) == id(grid)
>>> False
id(initial[0]) == id(grid[0])
>>> False

edited May 22, 2014 at 21:45

answered May 22, 2014 at 21:28

cmd

5,88819 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Zavec Over a year ago

Thank you! Is there a similar method for copying arrays in javascript? I'm currently in the process of learning JS, and built this in python to see if the problem was with the algorithm itself or with my implementation.

Collectives™ on Stack Overflow

Python continuously updating array

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related