Optimisation algorithme bactracking

Bonjour,

A Noël j’ai un vu un jeu de pentominos, n’ayant pas trouvé de solution à la main, je me suis dis ca doit ce résoudre par du bactracking.

J’ai donc réalisé un programme qui fonctionne mais qui n’est vraiment pas efficace, si il trouve une solution pour les modèles 0,1,2 et 4, le modèle 2 prend déjà beaucoup de temps à résoudre et j’ai interrompu le prog avant de voir une solution pour le 3. (les modèles sont des config pour les quels il existe des solutions).

1. Je ne vois pas bien comment optimiser le programme, peut être chercher à chaque pieces si je crée une zone dans la quelle je ne pourrais plus poser de pieces, mais cela risque aussi de prendre du temps.

2. Si je parviens à l’optimiser suffisamment, j’aimerais pourvoir obtenir toutes les solutions possibles.

3. De plus je me demande pourquoi le même programme lancé dans 2 environnements different ne donne pas le même résultats, je pense que c’est du à la récursion , mais sans vraiment comprendre.

Dans le terminal de Spyder:

Une solution en 38727 cycles, hier pour ce modèle javais une solution 73 cycles.

In [36]: b = Board(4)

In [37]: resoud(b,0,'')
╔═════════════╗╔═══════╗
╚═════════════╝╚═════╗ ║
╔═╗╔══════════╗╔════╗║ ║
║ ║╚═════╗ ╔══╝╚══╗ ║║ ║
║ ╚══╗╔═╗║ ║╔═╗╔═╗║ ║║ ║
╚══╗ ║╚═╝╚═╝║ ║╚═╝║ ║╚═╝
╔═╗║ ╚══╗╔══╝ ╚══╗║ ╚══╗
║ ║╚════╝╚══╗ ╔══╝╚════╝
║ ╚═════╗╔═╗║ ║╔════╗╔═╗
╚══╗ ╔══╝║ ║╚═╝╚══╗ ║║ ║
╔═╗║ ║╔═╗║ ║╔═╗╔═╗║ ║║ ║
║ ║╚═╝╚═╝║ ║║ ║╚═╝║ ║║ ║
║ ╚══╗╔══╝ ║║ ║╔══╝ ║║ ║
║    ║║ ╔══╝║ ║╚════╝║ ║
║    ║║ ║╔══╝ ╚══╗╔══╝ ║
╚════╝╚═╝╚═══════╝╚════╝
38727
Out[37]: True

Dans un onglet Ipython du terminal Konsole:

Une autre solution en 12834 cycles.

In [11]: b = Board(4)

In [12]: resoud(b,0,'')
╔═╗╔════╗╔═╗╔═══════╗╔═╗
║ ║║ ╔══╝║ ║╚══╗    ║║ ║
║ ║║ ║╔══╝ ╚══╗║    ║║ ║
║ ║║ ║╚══╗ ╔══╝╚════╝║ ║
║ ║║ ║╔═╗║ ║╔═╗╔═╗╔══╝ ║
║ ║║ ║╚═╝╚═╝║ ║╚═╝║ ╔══╝
║ ║║ ║╔═════╝ ║╔═╗║ ║╔═╗
║ ║╚═╝╚═════╗ ║║ ║╚═╝║ ║
║ ║╔════╗╔═╗║ ║║ ╚═══╝ ║
╚═╝║ ╔══╝║ ║╚═╝╚═══════╝
╔══╝ ║╔═╗║ ╚══╗╔═╗╔═╗╔═╗
║ ╔══╝╚═╝║ ╔══╝╚═╝║ ║║ ║
║ ║╔═╗╔══╝ ║╔═════╝ ║║ ║
╚═╝║ ║╚════╝║ ╔═════╝║ ║
╔══╝ ╚═════╗║ ║╔═════╝ ║
╚══════════╝╚═╝╚═══════╝
12834
Out[12]: True

Code python :

s_pieces = """@@@@@

@@@@
@

@@@
@
@

 @
@@@
 @

@@
@
@@

@
@@@
@

@@@
  @@

@
@@
 @@

@@
 @@
 @

@@@
@@

@@
 @
 @@

@@@@
 @"""


pieces = {}
for np,p in zip('ILVXUTNWFPZY',s_pieces.split('\n\n')):
    pieces[np]=[]
    print(np,'--\n',p,sep='')
    l = max(map(len,p.split('\n')))
    for r in p.split('\n'):
        pieces[np].append(r.ljust(l))

def coord(piece):
    ans = []
    for y,r in enumerate(piece.split('\n')):
        for x,c in enumerate(r):
            if c=='@':
                ans.append((y,x))
    y,x = min(ans)
    ans = sorted((r-y,c-x) for r,c in ans)
    return ans


def transfo(piece):
    ans = set()
    for p in (piece,piece[::-1]):
        for _ in range(4):
            p = [''.join(r[::-1]) for r in zip(*p)]
            a = '\n'.join(p)
            #print(a,'\n---')
            ans.add(a)
    return ans


def toutes_pieces(pieces):
    ans = {}
    for i,p in pieces.items():
        ans[i] = list(map(coord,transfo(p)))
    return ans


class Board:        
    def __init__(self,modele=0):
        if modele<4:
            c,r = [(10,6),(12,5),(15,4),(20,3)][modele]
            self.grid = [[' ']*c for i in range(r)]
        else:
            c = r = 8
            self.grid = [[' ']*c for i in range(r)]
            for x,y in ((2,2),(2,5),(5,2),(5,5)):
                self.grid[y][x] = '#'
        
        self.X, self.Y, self.S = c, r, c*r
        self.tests = 0

PIECES = toutes_pieces(pieces)
# PIECES est un dictionnaire avec une entrée pour chaque piece 
# et la liste des rotations/ reflection possibles de chaque pentomino
board = Board(5)

ed = '║ ╚ ╗ ╔ ═ ╝'
"""
 0
1X2
 3
"""
edges = {
    (0,0,0,0):('   ','   ','   '),
    (0,0,0,1):('   ','   ','═══'),
    (0,0,1,0):('  ║','  ║','  ║'),
    (0,0,1,1):('  ║','  ║','══╝'),
    (0,1,0,0):('║  ','║  ','║  '),
    (0,1,0,1):('║  ','║  ','╚══'),
    (0,1,1,0):('║ ║','║ ║','║ ║'),
    (0,1,1,1):('║ ║','║ ║','╚═╝'),
    (1,0,0,0):('═══','   ','   '),
    (1,0,0,1):('═══','   ','═══'),    
    (1,0,1,0):('══╗','  ║','  ║'),
    (1,0,1,1):('══╗','  ║','══╝'),
    (1,1,0,0):('╔══','║  ','║  '),    
    (1,1,0,1):('╔══','║  ','╚══'),
    (1,1,1,0):('╔═╗','║ ║','║ ║'),
    (1,1,1,1):('╔═╗','║ ║','╚═╝'),
       
    }
def nbg(board,x,y):
    r = []
    for dx,dy in [(0,-1),(-1,0),(1,0),(0,1)]:
        nx, ny = x+dx, y+dy
        c = board.grid[y][x]
        v = 0 if board.X>nx>=0<=ny<board.Y and board.grid[ny][nx]==c else 1
        r.append(v)
    return tuple(r)

def affb(board):
    g = [['']*(3*board.X) for _ in range(2*board.Y)]
    for y in range(board.Y):
        for x in range(board.X):
            e = edges[nbg(board,x,y)][::2]
            for dy,row in enumerate(e):
                for dx,c in enumerate(row):
                    g[y*2+dy][x*3+dx] = c
    gy, gx = len(g), len(g[0])
    for y in range(gy):
        for x in range(gx):
            c = g[y][x]
            if c!=' ':continue
            if x>0 and y>0 and g[y][x-1]=='═' and g[y-1][x]=='║':
                c = '╝'
            if x<gx-1 and y>0 and g[y][x+1]=='═' and g[y-1][x]=='║':
                c = '╚'
            if x>0 and y<gy-1 and g[y][x-1]=='═' and g[y+1][x]=='║':
                c = '╗'
            if x<gx-1 and y<gy-1 and g[y][x+1]=='═' and g[y+1][x]=='║':
                c = '╔'
            g[y][x] = c
        print(''.join(g[y]))


def affb0(board):
    print( '+'+'-'*board.X+'+')
    for row in board.grid:
        print('|'+''.join(row)+'|')
    print( '+'+'-'*board.X+'+')


def next_pos(board,pos):
    while pos<board.S and board.grid[pos//board.X][pos%board.X]!=' ':
        pos += 1
    return pos


def valide(board,piece,pos):
    x,y = pos % board.X, pos // board.X
    return all(board.X>x+dx>=0<=y+dy<board.Y and board.grid[y+dy][x+dx]==' '
               for dy,dx in piece)


def place(board,piece,pos,symbol='@'):
    x, y = pos % board.X, pos // board.X
    for dy,dx in piece:
        board.grid[y+dy][x+dx] = symbol
    board.tests += 1


def efface(board,piece):
    for y,row in enumerate(board.grid):
        for x,c in enumerate(row):
            if c==piece:
                board.grid[y][x] = ' '
  

def resoud(board,pos,prec_pieces):
    npos = next_pos(board,pos)
    if npos == board.S:
        affb(board)
        print(board.tests)
        return True
    reste = [p for p in PIECES if p not in prec_pieces]
    for p in reste:
        for c in PIECES[p]:
            if valide(board,c,npos):
                place(board,c,npos,p)
                if resoud(board,npos,prec_pieces+p):
                    return True
    if prec_pieces:
        efface(board,prec_pieces[-1])
    return False

Salut,

Je n’ai pas regardé ton programme en détails ni vraiment compris le problème que tu cherches à résoudre (a priori tu veux placer des pièces sur une planche, je ne sais pas quelles sont les règles au-delà de ça).
Mais une stratégie souvent utile dans les algorithmes de backtracking est la mise en cache : tu gardes en mémoire les situations que tu as déjà croisées et tu évites de les parcourir à nouveau.

La règle du jeu : Il y a 12 pièces avec 12 formes différentes (description dans le lien donné par kayou) ; chaque pièce occupe 5 petits carreaux, donc classiquement, on essaye de disposer ces 12 pièces dans un rectangle 6x10, ou 5x12 ou 4x15 …

Ici, c’est une variante, on a un carré 8x8, et il y a 4 cases interdites (les cases c3, f3, c6, f6 si on reprend les notations classiques du jeu d’échecs). Il reste donc 60 carreaux pour poser nos 12 pièces.

Dans ton dessin, tu t’embêtes beaucoup ; ça aurait été plus simple de dessiner ainsi (ton premier dessin) :

I I I I I V V V
W Y Y Y Y Z Z V
W W . Y X . Z V
F W W X X X Z Z
F F F N X U U L
P F . N T . U L
P P N N T U U L
P P N T T T L L 

Comme le dis @elegance , il y 12 pieces différentes, chaque piece n’est utilisable qu’une seule fois mais elle elle peut être tournée ou symétrisée. Pour la représentation j’avais fait en 1er avec uniquement les lettre mais je ne trouvais pas ca très lisible.

J’ai essayé d’utiliser lru_cache, mais cela ne retourne plus le bon résultat, je pense que c’est du aux paramètres de la fonction resoud: board est une liste qui est modifiée à chaque cycles, pos la position de placement de la piece et prec_piece qui sert à mémoriser l’ordre de pieces utilisées mais la même piece peut être utilisée dans 2 à 8 configs différentes (rotation ou réflexion) pour une résultat different, je vais remplacer ce paramètre par une liste et voir ce que ca donne.

@lru_cache(maxsize=1024)
def resoud(board,pos,prec_pieces):
    npos = next_pos(board,pos)
    if npos == board.S:
        affb(board)
        print(board.tests)
        return True
    reste = [p for p in PIECES if p not in prec_pieces]
    for p in reste:
        for c in PIECES[p]:
            if valide(board,c,npos):
                place(board,c,npos,p)
                if resoud(board,npos,prec_pieces+p):
                    return True
    if prec_pieces:
        efface(board,prec_pieces[-1])
    return False

Pour le parcours du dictionnaire, je suis sur une version 3.11 dans les 2 environnements donc le parcours devrait se faire de la même façon.

Apres moodif du code, le cache fonctionne mais comme le dis @Berdes, cela n’apporte rien en lui même, par contre j’ai du optimisé un peu le programme pour fonctionner avec le cache et cela m’a déja permis de gagner 15 à 20% du temps.

Avant de revoir la représentation du problème, je vais lister les postions interdites , les rotations et réflexions de pieces sont déjà calculées en debut de programme en passant par un set (fonction transfo).

Avant de revoir la représentation du problème, je vais lister les postions interdites , les rotations et réflexions de pieces sont déjà calculées en debut de programme en passant par un set (fonction transfo).

À ta place, je reverrais la représentation du problème avant d’implémenter quoique ce soit d’autre. Manipuler des chaines de caractères, des listes, et des boucles explicites en Python est rarement une bonne idée quand on cherche des performances. Quand on veut faire un calcul en Python avec des performances correctes, en général la stratégie la plus payante est d’écrire le moins de Python possible en reléguant les boucles et les calculs à une bibliothèque implémentée en C ou similaire. Typiquement, utiliser des arrays numpy et les opérations définies sur ces objets au lieu de boucles manuelles devrait déjà aider pas mal.

Vu que tu n’as pas besoin de savoir quel pièce occupe quel espace (c’est quelque chose uniquement utile pour l’affichage), tu peux simplement stocker une liste de booléens qui indique quel cellule est occupé ou non. Ici, une liste de booléens peut être vu comme la représentation binaire d’un nombre, ce qui te permet de faire tes opérations (bouger une pièce à une position donné, tester si une pièce peut être placé, etc) avec de simples opérations bits à bits (voir par exemple https://realpython.com/python-bitwise-operators/ pour plus d’explications).

Mouais, les opérations bit-à-bits peuvent être très intéressantes quand on manipule des entiers de taille fixe (pour avoir les opérations bit-à-bit comme des instructions processeurs), qui sont typiquement sur la pile, voire dans un L-cache, voire dans des registres, et qu’on travaille avec un langage compilé en langage machine. Ici on parle de Python où les "entiers" sont des objets sur le tas de taille variable, les opérations "bit-à-bit" n’ont alors plus grand chose de spécial qui les rendraient plus rapides. La seule chose qui joue ici est qu’utiliser un entier comme tableau de booléens nous donne un tableau contiguë en mémoire. On a ça de manière beaucoup moins détournée et beaucoup plus flexible en utilisant des tableaux numpy, surtout avec les types primitifs de numpy à taille fixe.