VISI201 Backtracking (PICHENOT Simon)
Principe du backtracking
Le backtracking est une catégorie d’algorithme qui permet de résoudre des problèmes en explorant toutes les possibilités. Pour cela le principe est de choisir une variable du problème, et pour chaque affectation possible de cette variable tester si il y a une solution possible. Si aucune solution n'est trouvée, l'algorithme abandonne et revient sur l'affectation précédente.
Résolution de sudoku
Durant ce projet j'ai réalisé 2 programme qui permettent de résoudre des sudoku avec du backtracking.
Algorithme basique
Ce premier algorithme teste toutes les branches de l'arbre de possibilité de la grille de sudoku. Pour ce faire l’algorithme commence par prendre une case vide. Il lui fait prendre les valeur de 1 à 9. Si la valeur de cette case est juste il passe à la case suivante sinon il revient à la case précédente.
Cette méthode fonctionne mais l'algorithme fait environ 5000 backtracking pour des grilles de niveau facile. Cela vient du fait que le programme ne peut pas savoir que la branche qu'il explore est juste ou fausse tant qu'il n'est pas arrivé au bout.
Pour l'algorithme voir algorithme python, sudoku basique
Algorithme avec réflexion
Ce deuxième algorithme ressemble au premier, sauf que celui ci commence par enlever toutes les branches de l'arbre qui ne sont pas des solutions. Pour cela le programme regarde les valeurs possibles pour chaque case et donc élimine toutes les valeurs impossible. De ce fait l’algorithme parcours moins de branche de l'arbre ce qui diminue le nombre de backtracking. Par exemple pour une grille de niveau difficile le programme fait environ 5 backtracking. il peut ne même pas en faire sur des grilles assez simple.
Algorithme python
Voici les algorithme que j'ai fait durant le projet.
Sudoku basique
# affiche la grille
def print_grid(arr):
affiche=""
for i in range(9):
for j in range(9):
affiche+=str(arr[i][j])
affiche+='\n'
print(affiche)
# trouver zone vide
def find_empty_location(arr,l):
for row in range(9):
for col in range(9):
if(arr[row][col]==0):
l[0]=row
l[1]=col
return True
return False
# verifier ligne
def used_in_row(arr,row,num):
for i in range(9):
if(arr[row][i] == num):
return True
return False
# verifier colonne
def used_in_col(arr,col,num):
for i in range(9):
if(arr[i][col] == num):
return True
return False
# verifier carré
def used_in_box(arr,row,col,num):
for i in range(3):
for j in range(3):
if(arr[i+row][j+col] == num):
return True
return False
# verifie validiter case
def check_location_is_safe(arr,row,col,num):
return not used_in_row(arr,row,num) and not used_in_col(arr,col,num) and not used_in_box(arr,row - row%3,col - col%3,num)
def solve_sudoku(arr):
l=[0,0]
if(not find_empty_location(arr,l)):
return True
global counter_back
row=l[0]
col=l[1]
for num in range(1,10):
if(check_location_is_safe(arr,row,col,num)):
arr[row][col]=num
if(solve_sudoku(arr)):
# if solution+=1 print(grid)
return True
# return un entier nombre de solution
arr[row][col] = 0
else:
counter_back+=1
return False
#return counter
counter_back = 0
if __name__=="__main__":
grid=[[0 for x in range(9)]for y in range(9)]
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]]
if(solve_sudoku(grid)):
print_grid(grid)
print(counter_back)
else:
print("No solution exists")
print(counter_back)
Sudoku avec réflexion
def location_possiblity(arr,row,col):
possibility = []
for i in range(1,10):
if not(used_in_row(arr,row,i)) and not(used_in_col(arr,col,i)) and not(used_in_box(arr,row - row%3,col - col%3,i)):
possibility += [i]
return possibility
# affiche la grille
def print_grid(arr):
affiche=""
for i in range(9):
for j in range(9):
affiche+=str(arr[i][j])
affiche+='\n'
print(affiche)
# trouver zone vide
def find_empty_location(arr,l):
for row in range(9):
for col in range(9):
if(arr[row][col]==0):
l[0]=row
l[1]=col
return True
return False
# verifier ligne
def used_in_row(arr,row,num):
for i in range(9):
if(arr[row][i] == num):
return True
return False
# verifier colonne
def used_in_col(arr,col,num):
for i in range(9):
if(arr[i][col] == num):
return True
return False
# verifier carré
def used_in_box(arr,row,col,num):
for i in range(3):
for j in range(3):
if(arr[i+row][j+col] == num):
return True
return False
# verifie validiter case
def check_location_is_safe(arr,row,col,num):
return not used_in_row(arr,row,num) and not used_in_col(arr,col,num) and not used_in_box(arr,row - row%3,col - col%3,num)
def solve_sudoku(arr):
l=[0,0]
if(not find_empty_location(arr,l)):
return True
global counter_back
row=l[0]
col=l[1]
for num in location_possiblity(arr,row,col):
if(check_location_is_safe(arr,row,col,num)):
arr[row][col]=num
if(solve_sudoku(arr)):
# if solution+=1 print(grid)
return True
# return un entier nombre de solution
arr[row][col] = 0
else:
counter_back+=1
return False
#return counter
counter_back = 0
if __name__=="__main__":
grid=[[0 for x in range(9)]for y in range(9)]
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]]
if(solve_sudoku(grid)):
print_grid(grid)
print(counter_back)
else:
print("No solution exists")
print(counter_back)