Pentominos : jouer en 2D

03 décembre 2009 - Mots-clés : Pentominos Python

Si l'on veut assembler les 12 pièces, il faudra un terrain constitué de 60 carrés. Parmi tous les rectangles possibles, il y en a 4 rectangulaires :

  • 3x20: 2 solutions. Exemple:
  • 4x15: 368 solutions. Exemple:
  • 5x12: 1010 solutions. Exemple:
  • 6x10: 2339 solutions. Exemple:

On peut les assembler dans tout type de forme à 60 carrés. Par exemple un rectangle 8*8 dans lequel 4 carrés resteront inoccupés, à disposer où bon vous semble: contiguës, séparés, au centre ou dans les coins. Les formes possibles sont inombrables. On en trouvera des exemples dans d'autres pages.

Le problème de la triplication: il s'agit d'assembler 9 pentominos pour reconstituer un pentomino à l'échelle 3:1, d'où le nom du problème. Chaque carré du pentomino à reconstituer est constitué d'un carré de 3*3. Un pentomino étant constitué de 5 carrés cela fait 3*3*5=45 carrés à remplir avec les pentominos de base. Voici un exemple avec le pentomino W :

Programme

Je vous propose un programme qui recherche toutes les solutions des problèmes en 2 dimensions pour les 4 rectangles à 60 cases.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
#!/usr/bin/python
# -*- coding: ISO8859-15 -*-

""" Recherche des positions du jeu de pentomino
Auteur : Franck Barbenoire
License : GPL
"""

import sys
import getopt
import string
from copy import deepcopy

#===============================================================================

class Piece(object):

    def __init_rotation(self):
        "Initialiser le dico de rotation de 90 degres dans le sens horaire"
        liste_rotation_avant = []
        for i in range(5):
            liste_rotation_avant.append(range(i*11,i*11+5))
        liste_rotation_apres = []
        for i in range(5):
            rang = []
            for j in range(5):
                rang.append(liste_rotation_avant[4-j][i])
            liste_rotation_apres.append(rang)
        self.__dico_rotation = {}
        for i in range(5):
            for j in range(5):
                self.__dico_rotation[liste_rotation_apres[i][j]] = liste_rotation_avant[i][j]
    #end def

    def __init_symetrie(self):
        "Initialiser le dico de symetrie"
        liste_symetrie_avant = []
        for i in range(5):
            liste_symetrie_avant.append(range(i*11,i*11+5))
        liste_symetrie_apres = deepcopy(liste_symetrie_avant)
        liste_symetrie_apres.reverse()
        self.__dico_symetrie = {}
        for i in range(5):
            for j in range(5):
                self.__dico_symetrie[liste_symetrie_apres[i][j]] = liste_symetrie_avant[i][j]
    #end def

    def __init_haut(self):
        "Initialiser le dico de translation vers le haut"
        liste_haut_avant = []
        for i in range(5):
            liste_haut_avant.append(range(i*11,i*11+5))
        liste_haut_apres = deepcopy(liste_haut_avant)
        del liste_haut_apres[0]
        self.__dico_haut = {}
        for i in range(4):
            for j in range(5):
                self.__dico_haut[liste_haut_apres[i][j]] = liste_haut_avant[i][j]
    #end def

    def __init_gauche(self):
        "Initialiser le dico de translation vers la gauche"
        liste_gauche_avant = []
        for i in range(5):
            liste_gauche_avant.append(range(i*11,i*11+5))
        liste_gauche_apres = deepcopy(liste_gauche_avant)
        for i in range(5):
            del liste_gauche_apres[i][0]
        self.__dico_gauche = {}
        for i in range(5):
            for j in range(4):
                self.__dico_gauche[liste_gauche_apres[i][j]] = liste_gauche_avant[i][j]
    #end def

    def __teste_ligne(self, position, ligne):
        "Teste la présence d'une case dans une ligne"
        for i in ligne:
            if i in position:
                return False
        return True
    #end def

    def __transforme(self, position, dico):
        "Effectue la transformation de la position dictée par le dictionnaire"
        new_position = []
        for c in position:
            new_position.append(dico[c])
        new_position.sort()
        # coller dans le coin haut gauche
        while self.__teste_ligne(new_position, self.__LIGNE_HAUT):
            new_position = self.__transforme(new_position, self.__dico_haut)
        while self.__teste_ligne(new_position, self.__LIGNE_GAUCHE):
            new_position = self.__transforme(new_position, self.__dico_gauche)
        return new_position
    #end def

    def __init__(self, identite, position):
        self.identite = identite

        self.__init_rotation()
        self.__init_symetrie()
        self.__init_haut()
        self.__init_gauche()

        self.__LIGNE_HAUT = range(5)
        self.__LIGNE_GAUCHE = [0, 11, 22, 33, 44]

        # Calculer toutes les positions de cette pièce
        self.positions = []
        self.positions.append(position)
        for i in range(3):
            position = self.__transforme(position, self.__dico_rotation)
            if position not in self.positions:
                self.positions.append(position)
        position = self.__transforme(position, self.__dico_symetrie)
        if position not in self.positions:
            self.positions.append(position)
        for i in range(3):
            position = self.__transforme(position, self.__dico_rotation)
            if position not in self.positions:
                self.positions.append(position)
        self.nbr_positions = len(self.positions)

        self.num_position = 0
        self.decalage = 0
        self.indice = 0
        self.curseur = 0
    #end def
#end class

#===============================================================================

class Terrain(object):

    def __init__(self, hauteur, largeur, pieces):
        self.__hauteur = hauteur
        self.__largeur = largeur
        self.__TAILLE_TERRAIN = 275

        self.__pieces = pieces
        self.__nbr_pieces = len(self.__pieces)
    #end def

    #===========================================================================

    def __cherche_place(self, curseur):
        """Recherche une place disponible dans le terrain et retourne son indice"""

        while self.__terrain[curseur] != ' ':
            curseur += 1
        return curseur
    #end def

    #===========================================================================

    def __cherche_piece(self, indice):
        """Recherche une pièce disponible"""

        indice += 1
        while (indice < self.__nbr_pieces) and (self.__pieces[indice] in self.__pieces_placees):
            indice += 1
        return indice
    #end def

    #===========================================================================

    def __enleve_piece(self, piece_a_enlever):
        """Enleve une piece du terrain"""

        num_position = piece_a_enlever.num_position
        decalage = piece_a_enlever.decalage
        for pos_case in piece_a_enlever.positions[num_position]:
            self.__terrain[decalage + pos_case] = ' '
    #end def

    #===========================================================================

    def __place_piece(self, piece_a_placer):
        """Place un piece dans le terrain"""

        num_position = piece_a_placer.num_position
        decalage = piece_a_placer.decalage
        for pos_case in piece_a_placer.positions[num_position]:
            self.__terrain[decalage + pos_case] = piece_a_placer.identite
    #end def

    #===========================================================================

    def __teste_piece(self, piece_a_tester):
        """Teste si une piece tient dans le terrain"""

        num_position = piece_a_tester.num_position
        decalage = piece_a_tester.decalage
        return self.__terrain[decalage + piece_a_tester.positions[num_position][1]] == ' ' and \
                   self.__terrain[decalage + piece_a_tester.positions[num_position][2]] == ' ' and \
                   self.__terrain[decalage + piece_a_tester.positions[num_position][3]] == ' ' and \
                   self.__terrain[decalage + piece_a_tester.positions[num_position][4]] == ' '
    #end def

    #===========================================================================

    def __affiche_terrain(self):
        """Affichage du terrain"""

        for i in range(self.__hauteur):
            ligne = ""
            for j in range(self.__largeur):
                ligne += self.__terrain[i*11 + 12 + j]
            print ligne
        print
    #end def

    #===========================================================================

    def cherche_solutions(self):
        """Recherche toutes les solutions correspondant a la forme du terrain avec
        les pièces dont on dispose"""

        #initailiser le terrain
        self.__terrain = ['='] * self.__TAILLE_TERRAIN
        for  i in range(self.__hauteur):
            for j in range(self.__largeur):
                self.__terrain[i*11 + j + 12] = ' '

        self.__pieces_placees = []

        indice = -1
        curseur = self.__cherche_place(0)
        nbr_solutions = 0

        while True:
            # chercher une piece
            while True:
                indice = self.__cherche_piece(indice)
                if indice == self.__nbr_pieces:
                    if len(self.__pieces_placees) == 0:
                        # on a fait le tour, c'est fini !
                        print "Nombre de solutions trouvees : %d" % nbr_solutions
                        return
                    # plus de piece disponible
                    piece = self.__pieces_placees.pop()
                    self.__enleve_piece(piece)
                    curseur = piece.curseur
                    decalage = piece.decalage
                    indice = piece.indice
                    if piece.num_position < piece.nbr_positions - 1:
                        # essayer la position suivante de la même pièce
                        piece.num_position += 1
                        break
                else:
                    piece = self.__pieces[indice]
                    piece.num_position = 0
                    break
                #end if
             #end while

            while True:
                piece.decalage = curseur - piece.positions[piece.num_position][0]
                if self.__teste_piece(piece):
                    # placer la piece sur le terrain
                    piece.curseur = curseur
                    piece.indice= indice
                    self.__pieces_placees.append(piece)
                    self.__place_piece( piece)
                    if len(self.__pieces_placees) < self.__nbr_pieces:
                        curseur = self.__cherche_place(curseur)
                    indice = -1
                    break
                else:
                    if piece.num_position < piece.nbr_positions - 1:
                        piece.num_position += 1
                    else:
                        break
                    #end if
                #end if
             #end while

            if len(self.__pieces_placees) == self.__nbr_pieces:
                self.__affiche_terrain()
                nbr_solutions += 1
            #end if
        #end while

        print "Nombre de solutions trouvees : %d" % nbr_solutions
        return
    #end def
#end class

#===============================================================================

def pento(hauteur, largeur):

    P = Piece( 'P', [0, 1, 2, 12, 13])
    F = Piece( 'F', [0, 11, 12, 13, 23])
    N = Piece( 'N', [0, 1, 12, 13, 14])
    L = Piece( 'L', [0, 11, 12, 13, 14])
    Y = Piece( 'Y', [1, 11, 12, 13, 14])
    W = Piece( 'W', [0, 11, 12, 23, 24])
    S = Piece( 'S', [0, 11, 12, 13, 24])
    V = Piece( 'V', [0, 11, 22, 23, 24])
    T = Piece( 'T', [1, 12, 22, 23, 24])
    U = Piece( 'U', [0, 2, 11, 12, 13])
    I = Piece( 'I', [0, 1, 2, 3, 4])
    X = Piece( 'X', [1, 11, 12, 13, 23])

    terrain = Terrain(hauteur, largeur, (P, F, N, L, Y, W, S, V,  T, U, I, X))
    terrain.cherche_solutions()
    return
#end def

#===============================================================================

class Usage(Exception):
    def __init__(self, msg):
            self.msg = msg
    #end def
#end class

def main(argv=None):
    """Première fonction appelée"""

    # options par défaut
    hauteur = 10
    largeur = 6

    if argv == None:
        argv = sys.argv[1:]

    try:
        # parse command line options
        try:
           opts, args = getopt.getopt(argv, 'h6543', ['help', '10x6', '12x5', '15x4', '20x3'])
        except getopt.error, msg:
            raise Usage(msg)

        # process options
        for o, a in opts:
            if o in ('-h', '--help'):
                print "pyPento.py [<options>]"
                print "    options:"
                print "        -h, --help : imprime cette aide"
                print "        -6, --10x6 : taille du terrain de jeu"
                print "        -5, --12x5 : taille du terrain de jeu"
                print "        -4, --15x4 : taille du terrain de jeu"
                print "        -3, --20x3 : taille du terrain de jeu"
                return 0
            if o in ('-6', '--10x6'):
                hauteur = 10
                largeur = 6
            if o in ('-5', '--12x5'):
                hauteur = 12
                largeur = 5
            if o in ('-4', '--15x4'):
                hauteur = 15
                largeur = 4
            if o in ('-3', '--20x3'):
                hauteur = 20
                largeur = 3

        # resolution du probleme
        pento(hauteur, largeur)

    except Usage, err:
        print >>sys.stderr, err.msg
        print >>sys.stderr, "Pour obtenir de l'aide, utilisez --help"
        return(2)
#end def

if __name__ == '__main__':
    sys.exit(main())

Comments