algorithme Python pour résoudre triomines puzzle avec retours en arrière

Question

Disons que j'ai un conseil d'administration comme celui-ci

. . x . . . 
. . . . . . 
. . x . . x 

x est utilisé boîte et « » sont libres. J'ai besoin de mettre des triomines pour remplir toute la zone, donc il n'y aura pas de cellules libres. Les triomines sont en forme de L, et je marque le même triomino avec le même nombre.

Donc, la solution pourrait ressembler à ceci:

1 1 x 3 5 5 
1 2 3 3 4 5 
2 2 x 4 4 x 

Qu'est-ce que l'algorithme de python possible de retours en arrière peut-être?

Answer 1

algorithme est assez simple, d'abord nous obtenons une liste des cellules disponibles dans cette configuration de la carte, en gros, liste toutes les cellules possibles moins les interdites.

puis nous faisons une étape de solution en itérant sur la liste de cellules disponibles et en essayant d'insérer une pièce triomino dans cette position de cellule particulière, en utilisant 4 orientations possibles (la cellule disponible est le coin, nous avons 4 orientations pour la rotation).

Si la pièce s'adapte, augmentez le pas, enlevez les cellules occupées de la liste et essayez à nouveau de résoudre, jusqu'à ce qu'il n'y ait plus de cellules disponibles - cela signifie que la totalité du plateau est couverte.

#!/usr/bin/env python 

solution = {} 

orientations = [(1,1),(1,-1),(-1,1),(-1,-1)] # 4 possible orientations 

def solve(avl, step) : 
    if not len(avl) : 
     print 'done!' 
     return True 

    for i,j in avl : 
     for oi,oj in orientations : 
      if (i+oi,j) in avl and (i,j+oj) in avl : 
       occupied = [(i,j),(i+oi,j),(i,j+oj)] 
       # remove occupied from available, increase step and keep solving 
       if solve([a for a in avl if a not in occupied], step + 1) : 
        for occ in occupied : 
         solution[occ] = step 
        return True 

# initial conditions for this configuration 
# 
# . . x . . . 
# . . . . . . 
# . . x . . x 

X_SIZE, Y_SIZE = 6, 3 
forbidden_cells = [(0,2),(2,2),(2,5)] 

if __name__ == '__main__' : 
    available = [] 

    # fill the available cells list 
    for i in range(Y_SIZE) : 
     for j in range(X_SIZE) : 
      if (i,j) not in forbidden_cells : 
       available.append((i,j)) 

    # print the original problem 
    for i in range(Y_SIZE) : 
     for j in range(X_SIZE) : 
      print '.' if (i,j) in available else 'x', 
     print 

    # solve away! 
    if solve(available, 1) : 
     for i in range(Y_SIZE) : 
      for j in range(X_SIZE) : 
       print solution[(i,j)] if (i,j) in available else 'x', 
      print 
    else : 
     print 'sorry, no solution found' 

La sortie est:

$ ./triomines.py 
. . x . . . 
. . . . . . 
. . x . . x 
done! 
1 1 x 3 2 2 
1 4 3 3 5 2 
4 4 x 5 5 x 
$