Why is "list()" necessary in this 8 queens algorithm?

Question

I don't understand why "list()" is needed in result.append(list(bd)) ? I know that it is necessary because I read it here but I don't understand why. Why does adding list change the content of bd?

def share_diagonal(x0, y0, x1, y1):
        """ Is (x0, y0) on a shared diagonal with (x1, y1)? """
        dy = abs(y1 - y0)        # Calc the absolute y distance
        dx = abs(x1 - x0)        # CXalc the absolute x distance
        return dx == dy          # They clash if dx == dy
    

def col_clashes(bs, c):
    """ Return True if the queen at column c clashes
         with any queen to its left.
    """
    for i in range(c):     # Look at all columns to the left of c
          if share_diagonal(i, bs[i], c, bs[c]):
              return True

    return False           # No clashes - col c has a safe placement.

def has_clashes(the_board):
    """ Determine whether we have any queens clashing on the diagonals.
        We're assuming here that the_board is a permutation of column
        numbers, so we're not explicitly checking row or column clashes.
    """
    for col in range(1,len(the_board)):
        if col_clashes(the_board, col):
            return True
    return False


def main():
    import random
    rng = random.Random()   # Instantiate a generator

    bd = list(range(8))     # Generate the initial permutation
    num_found = 0
    tries = 0
    result = []
    while num_found < 92:
        rng.shuffle(bd)
        tries += 1
        if not has_clashes(bd) and bd not in result:
            print("Found solution {0} in {1} tries.".format(bd, tries))
            tries = 0
            result.append(list(bd))
            num_found += 1
    print(result)
main()

It's making a copy of `bd` because `bd` is being shuffled each iteration. — khelwood, Aug 21 '20 at 20:52
`list(bd)` creates a new list with the current content of `bd` — khelwood, Aug 21 '20 at 20:54
Because, as explained, `list(bd)` returns a **copy** of `bd` — Thierry Lathuille, Aug 21 '20 at 20:54
[This reference](https://stackoverflow.com/questions/2612802/list-changes-unexpectedly-after-assignment-how-do-i-clone-or-copy-it-to-prevent) may help you to understand what's going on — Brad Figueroa, Aug 21 '20 at 20:58

jreiss1923 · Accepted Answer · 2020-08-21T20:56:54.413

The reason your code is continuing to run right now is because it only found 92 solutions, at least when I tried running it. Your code is getting stuck at 92 and can't find any more solutions, at least for a while, resulting in your while loop continuing to loop.

https://en.wikipedia.org/wiki/Eight_queens_puzzle

As the Wikipedia article states, there are only 92 solutions to the Queen's Problem, which means your code works but literally can't find any more! To fix this, you just have to make your while loop be < 92, not < 93. I just ran it and it works.

    while num_found < 92:
        rng.shuffle(bd)
        tries += 1
        if not has_clashes(bd) and bd not in result:
            print("Found solution {0} in {1} tries.".format(bd, tries))
            tries = 0
            result.append(list(bd))
            num_found += 1

The reason list() is needed is because it makes a shallow copy of bd, copying the elements into a new list that points to a different space in memory. Just adding bd to your list of results would mean that every time one gets manipulated, all of them get changed in the same way. Using list() avoids this problem.

Why is "list()" necessary in this 8 queens algorithm?

1 Answers1