J'apprends le backtracking et la récursivité et je ne comprends pas (ou ne peux pas visualiser dans ma tête) pourquoi mon algorithme initial réimprime la carte dans son état d'origine, au lieu d'imprimer la solution.

Voici ma première tentative pour résoudre le problème :


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


def print_grid(grid):
    rows = len(grid)
    cols = len(grid[0])

    for y in range(rows):
        if y % 3 == 0 and y != 0:
            print("- " * (cols + 3))
        for x in range(cols):
            if x % 3 == 0 and x != 0:
                print(" | ", end="")
            if x == 8:
                print(grid[y][x])
            else:
                print(str(grid[y][x]) + " ", end="")

def find_empty(grid):
    for y in range(9):
        for x in range(9):
            if grid[y][x] == 0:
                return (y, x)


def possible(grid, y, x, n):
    # check rows
    for i in range(9):
        if grid[i][x] == n:
            return False

    # check cols
    for i in range(9):
        if grid[y][i] == n:
            return False

    # check subgrid
    y0 = (y // 3) * 3
    x0 = (x // 3) * 3
    for i in range(3):
        for j in range(3):
            if grid[y0+i][x0+j] == n:
                return False
    return True

def solve(grid):    
    empty = find_empty(grid)
    if not empty:
        return True
    y, x = empty
    for n in range(1, 10):
        if possible(grid, y, x, n):
            grid[y][x] = n
            solve(grid)
            grid[y][x] = 0

solve(grid)
print_grid(grid)

Après avoir modifié la fonction solve pour le code ci-dessous, j'ai obtenu le résultat attendu.

def solve(grid):    
    empty = find_empty(grid)
    if not empty:
        return True
    y, x = empty
    for n in range(1, 10):
        if possible(grid, y, x, n):
            grid[y][x] = n
            # changed this part
            if solve(grid):
                return True
            grid[y][x] = 0

Le premier point de sortie de la fonction "si non vide" ne suffirait-il pas ?

0
Agv 19 févr. 2020 à 03:13

1 réponse

Meilleure réponse

J'ai aussi eu du mal à comprendre toutes ces récursions folles, mais j'ai en quelque sorte réussi à comprendre. Votre erreur est due à la ligne

grid[y][x] = 0

Car cela écrase en fait la carte correcte (essayez d'ajouter print_grid(grid) à l'intérieur de la condition if not empty:) une fois qu'elle est résolue.

Je pense qu'il est plus rapide de comprendre le code correct au lieu de comprendre pourquoi le code d'origine n'a pas fonctionné. J'ai ajouté quelques lignes d'impression pour que ce soit plus facile à comprendre.

def solve(grid):
    empty = find_empty(grid)
    if not empty:
        print("board completed")
        return True
    y, x = empty
    for n in range(1, 10):
        if possible(grid, y, x, n):
            grid[y][x] = n
            if solve(grid):
                print("board is completed! do not reset anymore")
                return True
            print((y,x), " is not", n, " !!! reset this!!!")
            grid[y][x] = 0

Qui imprime:

(0, 4)  is not 9  !!! reset this!!!
(0, 2)  is not 3  !!! reset this!!!
(2, 1)  is not 9  !!! reset this!!!
(2, 0)  is not 3  !!! reset this!!!
(2, 1)  is not 3  !!! reset this!!!
(3, 5)  is not 8  !!! reset this!!!
(3, 3)  is not 1  !!! reset this!!!
(4, 3)  is not 7  !!! reset this!!!
(4, 1)  is not 6  !!! reset this!!!
(4, 0)  is not 2  !!! reset this!!!
(4, 8)  is not 4  !!! reset this!!!
(4, 5)  is not 2  !!! reset this!!!
(4, 3)  is not 7  !!! reset this!!!
(4, 1)  is not 6  !!! reset this!!!
(4, 0)  is not 8  !!! reset this!!!
(3, 8)  is not 1  !!! reset this!!!
(3, 5)  is not 8  !!! reset this!!!
(3, 3)  is not 9  !!! reset this!!!
(3, 1)  is not 5  !!! reset this!!!
(3, 0)  is not 3  !!! reset this!!!
(3, 5)  is not 8  !!! reset this!!!
(3, 3)  is not 1  !!! reset this!!!
(4, 3)  is not 7  !!! reset this!!!
(4, 1)  is not 6  !!! reset this!!!
(4, 0)  is not 2  !!! reset this!!!
(4, 8)  is not 4  !!! reset this!!!
(4, 5)  is not 2  !!! reset this!!!
(4, 3)  is not 7  !!! reset this!!!
(4, 1)  is not 6  !!! reset this!!!
(4, 0)  is not 8  !!! reset this!!!
(3, 8)  is not 1  !!! reset this!!!
(3, 5)  is not 8  !!! reset this!!!
(3, 3)  is not 9  !!! reset this!!!
(3, 1)  is not 3  !!! reset this!!!
(3, 0)  is not 5  !!! reset this!!!
(3, 3)  is not 1  !!! reset this!!!
(3, 3)  is not 9  !!! reset this!!!
(3, 1)  is not 3  !!! reset this!!!
(3, 5)  is not 3  !!! reset this!!!
(3, 3)  is not 1  !!! reset this!!!
(6, 5)  is not 4  !!! reset this!!!
(6, 4)  is not 8  !!! reset this!!!
(7, 3)  is not 5  !!! reset this!!!
(7, 2)  is not 8  !!! reset this!!!
(6, 6)  is not 8  !!! reset this!!!
(6, 5)  is not 4  !!! reset this!!!
(6, 4)  is not 9  !!! reset this!!!
(6, 2)  is not 6  !!! reset this!!!
board completed

Fondamentalement, not empty ne sera vrai que lorsque le tableau est correctement rempli. Parce que si l'un des nombres est dans la mauvaise position, ce mauvais numéro finira par être réinitialisé par grid[y][x] = 0 et testé avec un autre numéro.

Si le tableau est terminé et que if not empty: return True a été exécuté, if solve(grid): saura qu'il ne doit plus réinitialiser le tableau, il renvoie donc True. Cela échappera à la fonction, ce qui signifie que la ligne grid[y][x] = 0 sera ignorée.

Si vous ne comprenez pas, essayez d'imprimer entre chaque ligne pour vous faire une idée de ce qui se passe. J'espère que cela a aidé :)

3
Kenta Nomoto 19 févr. 2020 à 06:43