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

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 python

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)