python-online

backtracking

Deutsch English Français

BACKTRACKING (RETOUR SUR TRACE)

STRATÉGIE DANS UN LABYRINTHE

Un extraterrestre doit trouver la sortie d'un labyrinthe. Ce problème peut être résolu à l'aide d'un algorithme de backtracking (retour sur trace). Dans cet exemple, tu utilises un petit labyrinthe aléatoire de 11 × 11 cellules. Le labyrinthe est créé à l'aide de la classe GGMaze, disponible dans WebTigerPython.

À chaque exécution, un nouveau labyrinthe aléatoire est généré, avec une entrée en haut à gauche et une sortie en bas à droite. La méthode isWall(loc) permet de vérifier si la cellule située à la position loc est un mur.

Dans ton programme, tu détermines les cellules voisines en sélectionnant, parmi les quatre cellules adjacentes, celles qui ne se trouvent ni sur un mur ni à l'extérieur de la grille.

Programme:

#Labyrinth.py
from gamegrid import *

def createMaze():
    global maze
    maze = GGMaze(11, 11)
    for x in range(11):
        for y in range(11):
            loc = Location(x, y)
            if maze.isWall(loc):
                getBg().fillCell(loc, Color(0, 50, 0))
            else:    
                getBg().fillCell(loc, Color(255, 228, 196))
    refresh()

def getNeighbours(node):
    neighbours = []
    for loc in node.getNeighbourLocations(0.5):
        if isInGrid(loc) and not maze.isWall(loc):
           neighbours.append(loc)
    return neighbours
    
def search(node):
    global targetFound, manual
    if targetFound:
        return
    visited.append(node)  # push
    alien.setLocation(node)
    refresh()
    delay(500)    

    # Check for termination
    if node == exitLocation:
        targetFound = True
        
    for neighbour in getNeighbours(node):
        if neighbour not in visited:
            backSteps = [node]
            backStepsList.append(backSteps)
            backSteps.append(neighbour)
            search(neighbour) # recursive call
            backSteps.reverse()
            if not targetFound:
                for loc in backSteps[1:]:
                    setTitle("Must go back...")
                    alien.setLocation(loc)
                    refresh()
                    delay(500)
                if manual:    
                    setTitle("Went back...")
                else:
                    setTitle("Went back. Find target...")
            backStepsList.pop()
    visited.pop() # pop

manual = True
targetFound = False
visited = []
backStepsList = []
makeGameGrid(11, 11, 40, False)
setTitle("Labyrinth")
show()
createMaze()
startLocation = maze.getStartLocation()
exitLocation = maze.getExitLocation()
alien = Actor("sprites/alieng.png")
addActor(alien, startLocation)
search(startLocation)
setTitle("Target found")

#Labytinth.py
from gamegrid import *

def createMaze():
    global maze
    maze = GGMaze(11, 11)
    for x in range(11):
        for y in range(11):
            loc = Location(x, y)
            if maze.isWall(loc):
                getBg().fillCell(loc, Color(0, 50, 0))
            else:    
                getBg().fillCell(loc, Color(255, 228, 196))
    refresh()

def getNeighbours(node):
    neighbours = []
    for loc in node.getNeighbourLocations(0.5):
        if isInGrid(loc) and not maze.isWall(loc):
           neighbours.append(loc)
    return neighbours
    
def search(node):
    global targetFound, manual
    if targetFound:
        return
    visited.append(node)  # push
    alien.setLocation(node)
    refresh()
    delay(500)

# Check for termination
    if node == exitLocation:
        targetFound = True
        
    for neighbour in getNeighbours(node):
        if neighbour not in visited:
            backSteps = [node]
            backStepsList.append(backSteps)
            backSteps.append(neighbour)
            search(neighbour) # recursive call
            backSteps.reverse()
            if not targetFound:
                for loc in backSteps[1:]:
                    setTitle("Must go back...")
                    alien.setLocation(loc)
                    refresh()
                    delay(500)
                if manual:    
                    setTitle("Went back...")
                else:
                    setTitle("Went back. Find target...")
            backStepsList.pop()
    visited.pop() # pop

manual = True
targetFound = False
visited = []
backStepsList = []
makeGameGrid(11, 11, 40, False)
setTitle("Labyrinth")
show()
createMaze()
startLocation = maze.getStartLocation()
exitLocation = maze.getExitLocation()
alien = Actor("sprites/alieng.png")
addActor(alien, startLocation)
search(startLocation)
setTitle("Target found")

► Copy to clipboard

À RETENIR...

Il est intéressant de comparer la stratégie utilisée par un être humain avec celle d'un ordinateur pour résoudre un labyrinthe. Un joueur humain peut reconnaître d'un seul coup d'œil la situation dans son ensemble et en déduire une stratégie pour atteindre la sortie le plus rapidement possible. Il utilise ainsi une vision globale, caractéristique de la perception humaine, dont ton programme informatique ne dispose pas. Le programme, en revanche, n'analyse que la situation locale. Mais il se souvient très précisément des chemins déjà parcourus et explore de manière systématique de nouveaux chemins pour atteindre son objectif.

La situation devient toutefois plus favorable à l'ordinateur lorsque l'être humain ne dispose plus d'une vue d'ensemble, par exemple lorsqu'il se trouve lui-même à l'intérieur du labyrinthe ou lorsque le nombre de cellules augmente considérablement.

LE PROBLÈME DES 8 DAMES

Sur un échiquier de 8 × 8 cases, il faut placer 8 dames de manière qu'aucune d'elles ne puisse en attaquer une autre selon les règles des échecs. Une dame peut se déplacer horizontalement, verticalement et en diagonale.

Le problème des huit dames est un exemple classique d'application du backtracking. L'algorithme place les dames les unes après les autres sur l'échiquier, de manière que chaque nouvelle dame ne soit pas en conflit avec celles qui sont déjà placées. Lorsqu'il n'est plus possible de placer une dame supplémentaire, la dernière dame placée est déplacée vers une autre position. Si nécessaire, l'avant-dernière dame est également repositionnée, et ainsi de suite.

Ton algorithme s'arrête dès qu'il a trouvé la première solution. Il existe 92 solutions différentes au problème des huit dames.

Selon les performances de l'ordinateur ou de l'éditeur Web, la recherche d'une solution peut prendre de quelques secondes à quelques minutes.

Programme:

#Quenns.py
from gamegrid import *

n = 8 # number of queens

def getNeighbours(node):
    squares = [] # list of occupied squares
    for i in range(n):
        if node[i] != -1:
           squares.append(Location(node[i], i))

    forbidden = [] # list of forbidden squares
    for location in squares:
        a = location.x 
        b = location.y
        for x in range(n):
            forbidden.append(Location(x, b))  # same row
        for y in range(n):
            forbidden.append(Location(a, y))  # same column
        for loc in getDiagonalLocations(location, True):#diagonal up
            forbidden.append(loc)
        for loc in getDiagonalLocations(location, False):#diagonal down
            forbidden.append(loc)

    allowed = [] # list of all allowed squares = all - forbidden
    for i in range(n):
        for k in range(n):
            loc = Location(i, k)
            if not loc in forbidden:
                allowed.append(loc)

    neighbourNodes = [] 
    for loc in allowed:
        neighbourNode = node[:]
        i = loc.y # row
        k = loc.x # col
        neighbourNode[i] = k 
        neighbourNodes.append(neighbourNode)
    return neighbourNodes        

def search(node):
    global found
    if found or isDisposed(): 
        return
    visited.append(node)  # node marked as visited

    # Check for solution
    if not -1 in node: 
        found = True
        drawNode(node)
        
    for s in getNeighbours(node):
        search(s)
    visited.pop()

def drawBoard():
    for i in range(n):
        for k in range(n):
            if (i + k) % 2 == 0:
                getBg().fillCell(Location(i, k), Color.white)

def drawNode(node):
    removeAllActors()
    for i in range(n):
        addActorNoRefresh(Actor("sprites/chesswhite_1.png"),
                   Location(node[i],i))
    refresh()

makeGameGrid(n, n, 600 // n, False)
setBgColor(Color.darkGray)
drawBoard()
show()
setTitle("Searching. Please wait..." )

visited = []
found = False
startNode = [-1] * n  # all squares empty
search(startNode)
setTitle("Search complete. ")

#Quenns.py
from gamegrid import *

n = 8 # number of queens

def getNeighbours(node):
    squares = [] # list of occupied squares
    for i in range(n):
        if node[i] != -1:
           squares.append(Location(node[i], i))

forbidden = [] # list of forbidden squares
    for location in squares:
        a = location.x 
        b = location.y
        for x in range(n):
            forbidden.append(Location(x, b))  # same row
        for y in range(n):
            forbidden.append(Location(a, y))  # same column
        for loc in getDiagonalLocations(location, True):   #diagonal up
            forbidden.append(loc)
        for loc in getDiagonalLocations(location, False):  #diagonal down
            forbidden.append(loc)

allowed = [] # list of all allowed squares = all - forbidden
    for i in range(n):
        for k in range(n):
            loc = Location(i, k)
            if not loc in forbidden:
                allowed.append(loc)

neighbourNodes = [] 
    for loc in allowed:
        neighbourNode = node[:]
        i = loc.y # row
        k = loc.x # col
        neighbourNode[i] = k 
        neighbourNodes.append(neighbourNode)
    return neighbourNodes

def search(node):
    global found
    if found or isDisposed(): 
        return
    visited.append(node)  # node marked as visited

# Check for solution
    if not -1 in node: 
        found = True
        drawNode(node)
        
    for s in getNeighbours(node):
        search(s)
    visited.pop()

def drawBoard():
    for i in range(n):
        for k in range(n):
            if (i + k) % 2 == 0:
                getBg().fillCell(Location(i, k), Color.white)

def drawNode(node):
    removeAllActors()
    for i in range(n):
        addActorNoRefresh(Actor("sprites/chesswhite_1.png"),Location(node[i],i))
    refresh()

makeGameGrid(n, n, 600 // n, False)
setBgColor(Color.darkGray)
drawBoard()
show()
setTitle("Searching. Please wait..." )

visited = []
found = False
startNode = [-1] * n  # all squares empty
search(startNode)
setTitle("Search complete. ")

► Copy to clipboard