How to store matrix list data in recursive python function?-CodePudding

I am trying to solve the N_Queen problem with recursive function. My codes are shown below. The problemm is that I cannot store the acceptable solution in a list. I can see that all the right answers appeared while debuging, but those answers cannot store in a list outside the recursive function. I hope the acceptable solution could be stored in a list and keep on recursion for the next right answer. But the appended solution are always changing.

By importing copy and deepcopy, I have solved the problem, yet it is still confusing. It seems that others can store pure list result without deepcopy, but my matrix list is unacceptable.

THX.

def NQueens(self, n: int) -> int:
    res = []
    board = [['.' for _ in range(n)] for _ in range(n)]

    def backtrack(board,row):
        if row == n:
            res.append(board) # **this is the confusing part**
            return
        for col in range(n):
            if not isvalid(board,row,col):
                continue
            board[row][col] = 'Q'
            backtrack(board,row 1)
            board[row][col] = '.'

    def isvalid(board,row,col):
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        for i in range(1,row 1):
            if col - i >= 0 and board[row - i][col - i] == 'Q':
                return False
        for i in range(1,row 1):
            if col   i < n and board[row - i][col   i] == 'Q':
                return False
        return True

    backtrack(board,0)
    return res

CodePudding user response：

The problem is not that you can't save it, the problem is that after saving it you change the values of the board and they are linked so they both change so, when you finally return res, you end up returning the last state of board x times over, x beeing the times you appended it

I currently don't know hot to solve this but when i find out i'll edit or comment on this

CodePudding user response：

i finally found the problem, sorry for the wait.

In the line board[row][col] = '.' there were no conditions for that, what i mean is that it will alwas happen so when you put a queen after backtracking you'll remove it without exceptions.

I changed it so it will make a return true statement if achived to place all the queens so when backtracking it will not delete them if it found a solution.

I'll leave the working code, commenting what i changed, here:

def NQueens(n: int) -> int:
    board = [['.' for _ in range(n)] for _ in range(n)]

    def backtrack(board,row):
        #If all queens are placed then return true
        if row >= n:
            return True
        
        for col in range(n):
            #if it is valid place the queen and try to place the next queen on the next row
            if isvalid(board,row,col):
                board[row][col] = 'Q'
                if backtrack(board,row 1) == True:
                    return True
                
                #if placing the queen was not the way to the solution remove the queen
                board[row][col] = '.'
        #if the queen can't be placed in any column in this row return false 
        return False

    def isvalid(board,row,col):
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        for i in range(1,row 1):
            if col - i >= 0 and board[row - i][col - i] == 'Q':
                return False
        for i in range(1,row 1):
            if col   i < n and board[row - i][col   i] == 'Q':
                return False
        return True

    backtrack(board,0)
    return board #directly return board, res was innecesary