CODEWITHSUNDEEP
pythoncopyparameter-passing
jokoon
jokoon

Reputation: 6633

python copy() but list seems to be passed by copy

I found this bit of code here https://brilliant.org/wiki/recursive-backtracking/

from itertools import *
from copy import copy

def is_distinct( list ):
    '''Auxiliary function to is_solved
    checks if all elements in a list are distinct
    (ignores 0s though)
    '''
    used = []
    for i in list:
        if i == 0:
            continue
        if i in used:
            return False
        used.append(i)
    return True


def is_valid( brd ):
    '''Checks if a 3x3 mini-Sudoku is valid.'''
    for i in range(3):
        row = [brd[i][0],brd[i][1],brd[i][2]]
        if not is_distinct(row):
            return False
        col = [brd[0][i],brd[1][i],brd[2][i]]
        if not is_distinct(col):
            return False
    return True

def solve( brd , empties = 9):
    '''
      Solves a mini-Sudoku
      brd is the board
      empty is the number of empty cells
    '''

    if empties == 0:
        #Base case
        return is_valid( brd )
    for row,col in product(range(3),repeat=2):
        #Run through every cell
        cell = brd[row][col]
        if cell != 0:
            #If its not empty jump
            continue
        brd2 = copy( brd )
        for test in [1,2,3]:
            brd2[row][col] = test
            if is_valid(brd2) and solve(brd2,empties-1):
                return True
            #BackTrack
            brd2[row][col] = 0
    return False

Board = [ [ 0 , 0 , 0 ],
          [ 1 , 0 , 0 ],
          [ 0 , 3 , 1 ] ]
solve( Board , 9 - 3 )


for row in Board:#Prints a solution
    print row

It returns the correct result, meaning the solved board.

What I don't understand, is that that the solved() recursive function modified the Board list, but that function never writes to brd, it only writes to brd2, which is a copy.

However, when the list is printed at the end, it shows that it was written to.

So I'm a little confused by this bit of code, I know python functions pass lists by reference, but this example explicitly uses copy(). I'm either confused about copy or am missing something.

Upvotes: 2

Views: 67

Answers (2)

Amir Hossein Baghernezad
Amir Hossein Baghernezad

Reputation: 4085

You are creating a shallow copy.
Shallow copy is like when you have an object and it has references to other objects.
So if you copy the main object, you have not copied its inner references. It is still pointing to the same objects as the before main object.

Read more on HERE

The difference between shallow and deep copying is only relevant for compound objects (objects that contain other objects, like lists or class instances):

  • A shallow copy constructs a new compound object and then (to the extent possible) inserts references into it to the objects found in the original.

  • A deep copy constructs a new compound object and then, recursively, inserts copies into it of the objects found in the original.

Upvotes: 0

MSeifert
MSeifert

Reputation: 152677

copy.copy makes a shallow copy. In your case you have a list of lists and a shallow copy just creates a new lists but all elements (the inner lists) still refer to the old lists:

>>> a = [[1,2,3], [2,3,1], [3,1,2]]
>>> b = copy(a)
>>> b[0][0] = 100
>>> a
[[100, 2, 3], [2, 3, 1], [3, 1, 2]]
>>> b 
[[100, 2, 3], [2, 3, 1], [3, 1, 2]])

In this case it even works if you don't copy at all, e.g.

brd2 = brd

Generally you can solve this using deepcopy without backtracking or with backtracking but without copy. But combining copy and backtracking seems a bit wasteful.

Upvotes: 2

Related Questions