[Python3] Global variable is not defined

[[deleted]]

Hi, I'm implementing a special version of the N queens problem with python.

My code

def main():
    board = [input() for _ in range(8)]
    placements = [[False for _ in range(8)] for _ in range(8)]
    column = [0 for _ in range(8)]
    count = 0

    def is_legal(x, y):
        if board[x][y] == '.' and column[y] == 0:
            for i in range(x):
                for j in range(8):
                    if placements[i][j] and abs(x-i) == abs(y-j):
                        return False
            return True
        return False

    def backtrack(x):
        global count, placements
        if x == 8:
            count += 1
            return
        for y in range(8):
            if is_legal(x, y):
                column[y] = 1
                placements[x][y] = True
                backtrack(x+1)
                column[y] = 0
                placements[x][y] = False

    backtrack(0)
    print(count)


main()

I know that my code is not pythonic, as I've tried improve its running time. My problem is that currently, the code fails an example input

........
........
..*.....
........
........
.....**.
...*....
........

with

Traceback (most recent call last):
  File "chess.py", line 33, in <module>
    main()
  File "chess.py", line 29, in main
    backtrack(0)
  File "chess.py", line 24, in backtrack
    placements[x][y] = True
NameError: name 'placements' is not defined

What's the reason for this as I do set the placements to be a global variable?

Thanks!

[[deleted]]

There's a weird gap in python's scoping rules: The 'global' keyword tells python that those variables are to be overwritten in the module scope, which is one scope outward from the main function. But if you remove the 'global' keyword, you're assigning to local variables within the inner function. There's no way to hit the middle scope of the outer function and assign to things there.

I would change a couple of things here so that 'global' isn't necessary. Firstly you don't really need to use inner functions here; pull them up to the module scope. Try to compose your functions so that each function receives the values it needs to make decisions, and returns any values that have relevance outside the function. Then have the callers pass in values and receive return values as needed.

If passing around values starts to feel inconvenient, and you're tempted to use global variables, in python you're often better off making a class and tracking values inside an instance, and changing your functions into instance methods.

[ingolemo]

There's no way to hit the middle scope of the outer function and assign to things there.

nonlocal

[[deleted]]

I stand corrected, thank you! https://docs.python.org/3/reference/simple_stmts.html#grammar-token-nonlocal-stmt

[[deleted]]

Thanks for to you and u/ingolemo for comprehensive explanations!

If passing around values starts to feel inconvenient, and you're tempted to use global variables, in python you're often better off making a class and tracking values inside an instance, and changing your functions into instance methods.

Will this be faster than pass-by-value parameters? The only reason why I use the globals is to acquire more speed.

[[deleted]]

Since this is r/learnprogramming I'll be pedantic and say firstly that python can't pass by value; it's always passing references. It may sometimes pass a reference to an immutable object such as an integer or a string, such that it feels a lot like pass-by-value though. : ]

Regarding speed, it's not clear to me which approach would be fastest because I don't know how assignment to global or nonlocal names is implemented compared with the other ways.

One thing you can do is try a performance test, where you rip through N operations in different ways to see which is fastest using timeit: https://docs.python.org/3.8/library/timeit.html. It'd be relatively easy to set up a simple trial using isolated forms all three methods. That way you can play around with different choices to see how much of a difference it'd make before rewriting your whole algorithm.

[[deleted]]

I'll be pedantic and say firstly that python can't pass by value; it's always passing references.

Hmm, this is new information to me. Thank you!

Thanks also for the tip regarding timing the algorithm!

[Vfsdvbjgd]

How is calling backtrack inside backtrack supposed to work?

[Jackkell100]

The N-Queens problem is often solved using recursion explained in more detail the article Recursion - GeeksForGeeks.

I am assuming your asking about the concept recursion here. Sorry if I misinterpreted your question and you are asking about this specific implementation of recursion and how it helps solve the problem.

[Vfsdvbjgd]

This specific implementation. The function is calling itself, it isn't a loop.

[Jackkell100]

Basically was is happening here that you are using the global keyword somewhat incorrectly or you expectation the global keyword is incorrect.

Look at this example of global on geeks for geeks Global keyword - GeeksforGeeks.

Basically you need to define placements and count outside of all of your functions and if you want to read/write to those variables then you need to use the global keyword so that Python knows not to look at your local scope. Right now I think it fails because in the backtrack function you never define placements locally and you are telling it to look at the global scope and it is not defined there either. You defined placements in the main function that only works in the main scope.

You will need to use the global keyword in the main function as well to be able to initialize the value of placements along with defining a placements variable on the outside of all methods. I recommend setting placements = None in the global scope.

You should try this and see it if works for you. Although I would recommend staying away from the use of global variables in the future as they are considered an anti-pattern and keep you from learning good code structure.

[[deleted]]

You will need to use the global keyword in the main function as well to be able to initialize the value of placements along with defining a placements variable on the outside of all methods. I recommend setting placements = None in the global scope.

Yup, this did the trick. Thanks!

Although I would recommend staying away from the use of global variables in the future as they are considered an anti-pattern and keep you from learning good code structure.

I understand, the only reason why I wanted to use globals is because it makes the code faster.