Wiki du LAMA (UMR 5127) - Contributions [fr]

VISI201 Backtracking (PICHENOT Simon)

2020-05-17T10:01:45Z

Spichenot :

=== 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.

[[Fichier:arbre_backtracking.png|200px]]

=== Résolution de sudoku ===
[[Fichier:sudoku.png]]

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 ====

<pre>
# 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)
</pre>

==== Sudoku avec réflexion ====

<pre>
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)
</pre>

VISI201 Backtracking (PICHENOT Simon)

2020-05-17T09:54:19Z

Spichenot : /* Algorithme basique */

=== 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.

[[Fichier:arbre_backtracking.png|200px]]

=== Résolution de sudoku ===
[[Fichier:sudoku.png]]

Le Backtracking fonctionne bien pour les résolutions de casse tête comme le sudoku. Car on peut facilement tester les cases une par une avec a chaque fois les valeurs entre 1 et 9.

==== 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 ====

=== Algorithme python ===

Voici les algorithme que j'ai fait durant le projet.

==== Sudoku basique ====

<pre>
# 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)
</pre>

==== Sudoku avec réflexion ====

<pre>
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)
</pre>

VISI201 Backtracking (PICHENOT Simon)

2020-05-17T09:52:41Z

Spichenot : /* Algorithme python */

=== 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.

[[Fichier:arbre_backtracking.png|200px]]

=== Résolution de sudoku ===
[[Fichier:sudoku.png]]

Le Backtracking fonctionne bien pour les résolutions de casse tête comme le sudoku. Car on peut facilement tester les cases une par une avec a chaque fois les valeurs entre 1 et 9.

==== 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.

==== Algorithme avec réflexion ====

=== Algorithme python ===

Voici les algorithme que j'ai fait durant le projet.

==== Sudoku basique ====

<pre>
# 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)
</pre>

==== Sudoku avec réflexion ====

<pre>
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)
</pre>

VISI201 Backtracking (PICHENOT Simon)

2020-05-17T09:51:45Z

Spichenot :

=== 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.

[[Fichier:arbre_backtracking.png|200px]]

=== Résolution de sudoku ===
[[Fichier:sudoku.png]]

Le Backtracking fonctionne bien pour les résolutions de casse tête comme le sudoku. Car on peut facilement tester les cases une par une avec a chaque fois les valeurs entre 1 et 9.

==== 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.

==== Algorithme avec réflexion ====

=== Algorithme python ===

==== Sudoku basique ====

<pre>
# 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)
</pre>

==== Sudoku avec réflexion ====

<pre>
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)
</pre>

VISI201 Backtracking (PICHENOT Simon)

2020-05-17T09:42:30Z

Spichenot :

=== 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.

[[Fichier:arbre_backtracking.png|200px]]

=== Résolution de sudoku ===
[[Fichier:sudoku.png]]

Le Backtracking fonctionne bien pour les résolutions de casse tête comme le sudoku. Car on peut facilement tester les cases une par une avec a chaque fois les valeurs entre 1 et 9.

==== Algorithme basique ====
[[Sudoku 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.

==== Algorithme avec réflexion ====

=== Algorithme python ===

==== Sudoku basique ====

<pre>
# 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)
</pre>

==== Sudoku avec réflexion ====

<pre>
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)
</pre>

VISI201 Backtracking (PICHENOT Simon)

2020-05-17T09:41:47Z

Spichenot : /* Résolution de sudoku */

=== 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.

[[Fichier:arbre_backtracking.png|200px]]

=== Résolution de sudoku ===
[[Fichier:sudoku.png]]

Le Backtracking fonctionne bien pour les résolutions de casse tête comme le sudoku. Car on peut facilement tester les cases une par une avec a chaque fois les valeurs entre 1 et 9.

==== 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.

==== Algorithme avec réflexion ====

=== Algorithme python ===

==== Sudoku basique ====

<pre>
# 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)
</pre>

==== Sudoku avec réflexion ====

<pre>
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)
</pre>

VISI201 Backtracking (PICHENOT Simon)

2020-05-17T09:40:00Z

Spichenot : /* Résolution de sudoku */

=== 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.

[[Fichier:arbre_backtracking.png|200px]]

=== Résolution de sudoku ===
[[Fichier:sudoku.png]]

Le Backtracking fonctionne bien pour les résolutions de casse tête comme le sudoku.

==== 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.

==== Algorithme avec réflexion ====

=== Algorithme python ===

==== Sudoku basique ====

<pre>
# 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)
</pre>

==== Sudoku avec réflexion ====

<pre>
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)
</pre>

Fichier:Sudoku.png

2020-05-17T09:39:36Z

Spichenot :

VISI201 Backtracking (PICHENOT Simon)

2020-05-17T09:39:08Z

Spichenot : /* Résolution de sudoku */

=== 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.

[[Fichier:arbre_backtracking.png|200px]]

=== Résolution de sudoku ===
[[Fichier:sudoku.png]]
Le Backtracking fonctionne bien pour les résolutions de casse tête comme le sudoku.

==== 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.

==== Algorithme avec réflexion ====

=== Algorithme python ===

==== Sudoku basique ====

<pre>
# 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)
</pre>

==== Sudoku avec réflexion ====

<pre>
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)
</pre>

VISI201 Backtracking (PICHENOT Simon)

2020-05-16T09:25:39Z

Spichenot :

=== 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.

[[Fichier:arbre_backtracking.png|200px]]

=== Résolution de sudoku ===

Le Backtracking fonctionne bien pour les résolutions de casse tête comme le sudoku.

==== 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.

==== Algorithme avec réflexion ====

=== Algorithme python ===

==== Sudoku basique ====

<pre>
# 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)
</pre>

==== Sudoku avec réflexion ====

<pre>
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)
</pre>

VISI201 Backtracking (PICHENOT Simon)

2020-05-16T09:23:47Z

Spichenot :

VISI201 Backtracking (PICHENOT Simon)

2020-05-16T09:11:31Z

Spichenot :

VISI201 Backtracking (PICHENOT Simon)

2020-05-16T09:06:07Z

Spichenot :

VISI201 Backtracking (PICHENOT Simon)

2020-05-16T09:05:56Z

Spichenot :

VISI201 Backtracking (PICHENOT Simon)

2020-05-16T09:05:37Z

Spichenot :

Fichier:Arbre backtracking.png

2020-05-16T09:04:41Z

Spichenot :

VISI201 Backtracking (PICHENOT Simon)

2020-05-16T09:03:14Z

Spichenot :

VISI201 Backtracking (PICHENOT Simon)

2020-05-16T09:00:27Z

Spichenot :

VISI201 Backtracking (PICHENOT Simon)

2020-05-16T08:56:46Z

Spichenot :

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.

=== Principe du backtracking ===

=== Résolution de sudoku ===

==== Algorithme basique ====

==== Algorithme avec réflexion ====

VISI201 Backtracking (PICHENOT Simon)

2020-05-16T08:54:29Z

Spichenot :

VISI201 Backtracking (PICHENOT Simon)

2020-05-16T08:50:45Z

Spichenot : Page créée avec « 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 va... »