Understanding How Python Generates Lists

While working on a Python project, I encountered a bug related to list initialization that caused me some frustration. Here’s a breakdown of how I discovered the issue and solved it.

The Program

Here’s a simple program I was working on to check if a 9x9 Sudoku board is valid:

def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [0] * 9 
        columns = [0] * 9
        boxes = [[0] * 3] * 3

        for i in range(9):
            for j in range(9):
                if board[i][j] == '.': continue
                val  = int(board[i][j]) - 1

                if ((1 << val) & rows[i]):  
                    return False
                if ((1 << val) & columns[j]): 
                    return False
                if ((1 << val) & boxes[i//3][j//3]): 
                    return False

                rows[i] |= (1 << val)
                columns[j] |= (1 << val)
                boxes[i//3][j//3] |= (1 << val)
        
        return True

In this program, I use bitwise operations to track the values in each row, column, and 3x3 box on the Sudoku board. I initialize the rows and columns as 1D lists of bitmasks (using the [0] * 9 method), and the boxes variable is intended to store bitmasks for each 3x3 square in the board.

However, I ran into an unexpected problem.

The issue

The problem occurred when I modified a specific element in the boxes list (representing one of the 3x3 boxes). To my surprise, when I changed a value in one sublist, it also changed the other sublists in the same boxes list. For example:

boxes[0][0] = 82
print(boxes)

Output:

[[82, 0, 0], [82, 0, 0], [82, 0, 0]]

However, when I modified the rows or columns lists, they worked as expected:

rows = [0] * 9 
rows[0] = 82
print(rows)

Output:

[82, 0, 0, 0, 0, 0, 0, 0, 0]

This made me curious about how Python handles list initialization. I started investigating to understand what was happening and why my boxes list was behaving differently.

What I Learned About List Initialization

To investigate further, I reviewed how lists are initialized in Python. Let’s start with the basics.

1. Creating an Empty List

To create an empty list, you can simply use square brackets:

my_list = []

Python also provides a built-in function list():

my_list = list()

2. Creating a List with Predefined Elements

Creating a list with some elements is straightforward. For example, to create a list containing "apple", "banana", and "coke", you can do the following:

my_list = ["apple", "banana", "coke"]

3. Creating a List with Default Values

To create a list with multiple elements of the same value (e.g., a list of three 0s), you can use the multiplication operator:

my_list = [0]*3

print(my_list)

Output

[0, 0, 0]

Back to Our problem

Creating a List with Multiple Lists Inside

Now, let’s focus on creating a list with multiple lists inside it. For instance, how would we create a list that contains three lists, each initialized with [0, 0, 0]? Here's the code I used:

my_list = [[0] * 3] * 3

Let’s check what happens when we modify the first element of the first sublist:

my_list = [[0] * 3] * 3
my_list[0][0] = 82
print(my_list)

Output

[[82, 0, 0], [82, 0, 0], [82, 0, 0]]

As you can see, modifying one sublist changes all of them. This was the exact issue I encountered with my boxes list. After investigating, I realized why this happens:

• The expression [[0] * 3] creates a list containing three zeros [0, 0, 0].
• When you use [[0] * 3] * 3, you're creating three references to the same list [0, 0, 0], instead of creating three independent lists.
• As a result, when you modify one element (e.g., my_list[0][0] = 82), it affects all the sublists because they all point to the same list object in memory.

Why It Didn’t Happen to the List of Zeros?

The list [0] * 3 creates a list with three elements, and each of these elements is the same immutable value (0). Since integers are immutable types in Python, modifying one element does not affect the others.

However, when the elements inside the list are mutable objects (like lists themselves), they refer to the same object. That’s why modifying one sublist in the case of [[0] * 3] * 3 results in all sublists being modified.

How to Fix This

To ensure that each sublist is independent (i.e., each list can be modified independently), you need to create the sublists separately. You can do this using a list comprehension:

my_list = [[0] * 3 for _ in range(3)]

This creates three independent lists, each initialized with [0, 0, 0]. Now, modifying one list will not affect the others.

Conclusion

When you use [0] * 3, the list is created, and its elements are independent in terms of their values (in this case, all set to 0). However, when you use [0] * 3 to create a list of references to mutable objects (like lists), all the elements inside the list will refer to the same object. This leads to unexpected behavior: modifying one element will affect all other elements that reference the same object.

If you need independent lists or objects, especially when dealing with mutable types, use a method like list comprehension ([[0] * 3 for _ in range(3)]) to create separate instances for each sublist.

Understanding how different data types are handled in a programming language is crucial when working with lists and other complex data structures. This knowledge will help me avoid subtle bugs and ensure my code behaves as expected.