CODEWITHSUNDEEP
pythonbacktracking
tomer shavit
tomer shavit

Reputation: 81

Unable to create a copy of an instance variable (Python)

I created a Sudoku class in python, I want to solve the board and also keep an instance variable with the original board, but when I use the solve() method which uses the recursive backtracking algorithm self.board changes together with self.solved_board why is that, and how can I keep a variable with the original copy?

grid = [ [3, 0, 6, 5, 0, 8, 4, 0, 0], 
     [5, 2, 0, 0, 0, 0, 0, 0, 0], 
     [0, 8, 7, 0, 0, 0, 0, 3, 1], 
     [0, 0, 3, 0, 1, 0, 0, 8, 0], 
     [9, 0, 0, 8, 6, 3, 0, 0, 5], 
     [0, 5, 0, 0, 9, 0, 6, 0, 0], 
     [1, 3, 0, 0, 0, 0, 2, 5, 0], 
     [0, 0, 0, 0, 0, 0, 0, 7, 4], 
     [0, 0, 5, 2, 0, 6, 3, 0, 0] ]

class Sudoku:
    def __init__(self, board):
        self.board = board
        self.solved_board = board[:] #<--- I used the [:] because I thought this will create a new list

def get_board(self):
    return self.board

def set_board(self, board):
    self.board = board
    self.solved_board = board

def print_original_board(self):
    self.print(self.board)

def print_solved_board(self):
    self.print(self.solved_board)

def print(self, board):
    """Receiving a matrix and printing a board with seperation"""
    for i in range(len(board)):
        if i % 3 == 0 and i!=0:
            print('---------------------------------')
        
        for j in range(len(board[i])):
            if j%3==0 and j!=0:
                print(" | ", end='')
            print(" " + str(board[i][j]) + " ", end='')
        
        print('')


def find_empty(self,board):
    """Receiving a matrix, loops through it, and return a tuple 
    with the row and the column of the free stop in the matrix"""
    
    for i in range(len(board)):
        for j in range(len(board[i])):
            if board[i][j]==0:
                return (i,j)
    return None


def is_valid(self, board, num, pos):
    """Receiving matrix, a number we want to insert, and a tuple with the row and col
    and will check if the row, col, and box are valid so we can place the number 
    in the position"""

    # Check row
    for i in range(len(board[pos[0]])):
        if pos[0] != i and board[pos[0]][i] == num:
            return False
        
    # Check col
    for i in range(len(board)):
        if pos[1] != i and board[i][pos[1]] == num:
            return False

    pos_row = pos[0] // 3  
    pos_col = pos[1] // 3   
    
    for i in range(pos_row*3  ,pos_row*3 + 3):
        for j in range(pos_col * 3, pos_col*3 + 3):
            if (i,j) != pos and board[i][j] == num:
                return False
    
    return True


def solve(self):
    """Using backtracking algorithm to solve the solved_board variable"""
    find = self.find_empty(self.solved_board)

    if not find:
        return True
    else:
        row, col = find 
    
    for i in range(1,10):
        if(self.is_valid(self.solved_board, i, (row, col))):
            self.solved_board[row][col] = i

            if self.solve():
                return self.solved_board
        
        self.solved_board[row][col] = 0
        
    return False


sudoku = Sudoku(grid)
sudoku.print_original_board()
print(" ")
sudoku.solve()
sudoku.print_original_board() # <---- This prints the solved board

Upvotes: 2

Views: 44

Answers (3)

Robin
Robin

Reputation: 159

Try deepcopy method

 from copy import deepcopy
    def __init__(self, board):
       self.board = board
       self.solved_board = deepcopy(board)

Upvotes: 0

timgeb
timgeb

Reputation: 78760

self.solved_board = board[:] does indeed create a new list, but it references the same inner lists as board. You need to go one level deeper:

self.solved_board = [row[:] for row in board]

Upvotes: 1

phipsgabler
phipsgabler

Reputation: 20960

Yeah, board[:] does create a new list -- of all those old inner lists:

In [23]: board = [[1], [2]]

In [24]: board2 = board[:]

In [25]: board2[0] is board[0]
Out[25]: True

In [26]: board2[0][0] += 10

In [28]: board
Out[28]: [[11], [2]]

You'd need to deepcopy it; e.g.,

solved_board = [row[:] for row in board]

Upvotes: 1

Related Questions