I'm working on a backtracking algorithm and it works fine but I have issues with outputs i need to display the result. The code first imports a .txt file with a sudoku board in this format (underscores as empty cases)(line breaks are here because it would display it on a single line on the forum, there isn't line breaks in the file):
729___3
_1__6_8
___4__6
96___41_8
_487_5_96
__56_8__3
It then transform it in a Python array with 0 in lieu of underscores.
After that I created a class SudokuSolver (the code comes from here: text. This class solves the board with the methodsolve() and print it with the method print_board():
from termcolor import colored
def fileToArray(inputFile):
createdBoard = []
with open(inputFile, "r", encoding='utf-8') as fichier:
for line in fichier:
createdBoard.append(line.rstrip())
for i in range(len(createdBoard)):
createdBoard[i] = list(createdBoard[i].replace(u'_',u'0').strip())
for i in range(len(createdBoard)):
for j in range(len(createdBoard[i])):
createdBoard[i][j] = int(createdBoard[i][j])
return createdBoard
print(createdBoard)
array1 = fileToArray("/home/dennis/Dev/PythonDev/Divers/grilles_sudoku/sudoku2.txt")
print(array1)
class SudokuSolver:
"""
Cette classe résout une grille de sudoku et l'affiche dans le terminal
avec les chiffres de la grille initiale en couleur
"""
def __init__(self,input_array):
self.input_array = input_array
self.unsolved1 = self.input_array.copy()
self.unsolved2 = self.input_array[:]
self.unsolved3 = copy.deepcopy(self.input_array)
def print_board(self,x):
"""
La méthode print_board se charge de l'affichage de la solution.
En vert les chiffres de la grille initiale, en blanc les chiffres trouvés pour la solution.
"""
for i in range(0, 9):
for j in range(0, 9):
print(str(x[i][j]) if self.unsolved1[i][j] == 0 else colored(str(self.unsolved1[i][j]), 'green'), end=" ")
print()
for i in range(0, 9):
for j in range(0, 9):
print(str(x[i][j]) if self.unsolved2[i][j] == 0 else colored(str(self.unsolved2[i][j]), 'green'), end=" ")
print()
for i in range(0, 9):
for j in range(0, 9):
print(str(x[i][j]) if self.unsolved3[i][j] == 0 else colored(str(self.unsolved3[i][j]), 'green'), end=" ")
print()
def isPossible(self,board, row, col, val):
for j in range(0, 9):
if board[row][j] == val:
return False
for i in range(0, 9):
if board[i][col] == val:
return False
startRow = (row // 3) * 3
startCol = (col // 3) * 3
for i in range(0, 3):
for j in range(0, 3):
if board[startRow+i][startCol+j] == val:
return False
return True
def solve(self):
self.board = self.input_array
for i in range(0, 9):
for j in range(0, 9):
if self.board[i][j] == 0:
for val in range(1, 10):
if self.isPossible(self.board, i, j, val):
self.board[i][j] = val
self.solve()
# Bad choice, make it blank and check again
self.board[i][j] = 0
return self.board
#putting return self.board here the lopp dosen't stop
# return self.board
self.print_board(self.board)
a = SudokuSolver(array1)
b = a.solve()
#when I call the "solve" method and try to print it it prints the initial unsolved board
print("a.solve :", b)
In this state the program works, it solves the board and print it. In order to display the result with the initial ciphers in color, I want to retrieve the solved board.
If I place the return in the end of the solve() method, out of the loops, the program doesn't stop. As placed like here, it works with the print_board method using it outside the loop (thing I don't understand).
When writing this program, at first I placed the import function in the class, but when I call the input_array it is modified and I retrieve a solve board. The fact is that I face the same problem. So an auxiliary question to the return problem is: how to store a copy of an array in the program while another is modified ? Even I tried to declare a variable like self.unsolved_array = input_array in the init, just under the self.input_array, but it was modified to when I called it. After searching and trying a few things my mind is a little messy now.
EDIT
I tried the solution proposed by Nolann Boyere and @colidyre and only the deepcopy() worked. If I understood the problem, with a copy or a slice the 2nd list still points to the adress of the list 1, yes ?
With a deepcopy(), a new adress is created to the list 2 object, yes ?
I'm able now to make my program work as I wish but I'm still confuse with the return indentation problem if someone would like to enlighten me on that.
When you do list_2 = list_1, you don't say you're creating a new list called list_2 with the contents of list_1. You're actually linking list_2 to the object that list_1 points to. As a result, modifying one will modify the other. Here's an example:
list_1 = [1,2,3]
list_2 = list_1
list_1.append(4)
print(list_2) # [1,2,3,4]
Instead, you can use the slice list_1[:] operator to select the contents of the list :
list_1 = [1,2,3]
list_2 = list_1[:]
list_1.append(4)
print(list_2) # [1,2,3]
Doing list_1[:] is the same as doing list_1[0:len(list_1)], so selecting contents from the start to the end of the list.