Pentominó
Un pentominó (en grec πέντε / pente), també denominat pentaminó, és una poliforma de la classe poliominó que consistix en una figura geomètrica composta per cinc quadrats units pels seus costats. Existixen dotze pentominós diferents, que es nomenen en diferents lletres del abecedari (F, I, L, N, P, T, O, V, W, X, I, Z). Els pentominós obtinguts a partir d'uns atres per simetria axial o per rotació no conten com un pentominó diferent. A la dreta es mostren les figures
Disposició
[editar | editar còdic]Si es tenen en conte els pentominós obtinguts per mig de simetria axial com pentominós diferents tindríem un total de 18. Els cridats T, V, I, X, O i W formen pentominós per simetria axial als que també es pot aplegar per rotació. Açò té importància en alguns jocs d'ordenador, tipo Tetris, en els que no es poden girar les figures per simetria. Al pentominó F també li'l coneix com pentominó R, en referència al joc de la vida de Conway.
És interessant senyalar les diferents variacions que poden obtindre's:
L, N, I, P i F poden orientar-se de 8 formes: 4 per rotació i 4 per simetria axial.
- Z pot orientar-se de 4 formes: 2 per rotació i 2 per simetria axial.
X solament pot orientar-se d'una forma.
Per eixemple, les 8 combinacions d'I serien:
Rompecabezas 2D
[editar | editar còdic]
Un rompecabezas 2D de pentominós consistix en reblir un rectàngul en els 12 pentominós distints sense deixar buits buits ni superponent quadrats. Cada u dels 12 pentominós ocupa un àrea de 5 quadros, per lo que el rectàngul deurà tindre una superfície de 60 quadrats. Les possibles dimensions són 6×10, 5×12, 4×15 i 3×20. Un jugador hàbil no tarda molt en trobar una solució vàlida. Una tasca més llarga seria contar quàntes possibles solucions existixen per a cada cas, lo que requerix l'us d'algoritmes de busca per computador.
El rectàngul de 6×10 va ser resolt per primera volta per John Fletcher[1] en 1965. Existixen exactament 2339 solucions, excloent les variacions obtingudes per rotació o simetria de tot el rectàngul, pero incloent les variacions aplicades a un subconjunt de pentominós (a voltes açò permet trobar fàcilment atres solucions).
El rectàngul de 5×12 té 1010 possibles solucions, el de 4×15, 368 solucions i el de 3×20 té solament 2.
Un rompecabezas un tant més senzill (més simètric) és el que consistix en reblir un rectàngul de 8×8 en un forat en el centre de 2×2, que va ser resolt per Dana Scott en 1958.[2] Per a esta variació existixen 65 solucions. l'algoritme de Scott va ser una de les primeres aplicacions d'ordenador de backtracking o 'regrés arrere'. Existixen variacions en les que es permet canviar de posició els quatre buits. Molts d'eixos models es poden solucionar, llevat aquell en el que se situa cada parell de buits prop de dos cantons del tauler de manera que abdós cantons solament puguen ser completades per un pentominó tipo P.
S'han escrit algoritmes eficients per a la resolució d'estos rompecabezas, com per eixemple el de Donald Knuth.[3] Usant-los en hardware modern, es poden trobar solucions en uns segons.
Vore també
[editar | editar còdic]Referències
[editar | editar còdic]- ↑ John G. Fletcher (1965). "A program to solve the pentominó problem by the recursive use of macros". Communications of the ACM 8, 621–623.
- ↑ Dana S. Scott (1958). "Programming a combinatorial puzle". Technical Report No. 1, Department of Electrical Engineering, Princeton University.
- ↑ Donald E. Knuth. "Dancing links" [1] archivat en Wayback Machine. (Postscript, 1.6 megabytes). Includes a summary of Scott's and Fletcher's articles.
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Pentominó» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.