Investigador y creador de la web de referencia en coleccionismo de videojuegos RetroMaquinitas, Marçal Mora Cantallops publica ahora el libro Rompecabezas: Cinco décadas de videojuegos y puzles (Héroes de papel, 2017), un repaso a la historia del género pero también una aproximación teórica a sus claves formales. Charlamos con él para aprender más sobre este ¿género? tan indisociable del videojuego como frecuentemente ignorado.

¿Cuál era tu objetivo al escribir este libro?

Mi objetivo era doble; por un lado, me planteé, desde la humildad, la posibilidad de rellenar un hueco existente en la literatura alrededor del videojuego. Los libros sobre el medio llevan tiempo proliferando, especialmente desde la perspectiva fan, pero curiosamente el puzle es un género muy poco tratado. Cuando se toca es más por temas colaterales (como Portal) que por su esencia.

¿Y el segundo?

Era más bien una motivación: la posibilidad de unir uno de mis géneros favoritos (el puzle, obviamente) con una de mis pasiones (la historia del videojuego). Así, la esencia del libro consiste en intentar explicar la evolución del videojuego mediante la evolución de sus juegos de puzle.

¿Es el puzle un género o un elemento?

Es una pregunta importante. De hecho, a medida que escribía me daba cuenta que el puzle está lleno de contradicciones. Muchos autores, para empezar, le cuestionan incluso su carácter de juego. Si sigues, lo siguiente es plantearse si el puzle es un juego en el entorno del videojuego. Y claro, un paso más tarde te encuentras con otro dilema: ¿qué es un videojuego de puzle?

Entramos en el complicado asunto de las definiciones…

Los videojuegos tienen un problema, en el fondo, y es que en mi opinión no son juegos como tal, sino que son entornos generadores de juegos. Así, al ser relevantes elementos intangibles y difusos como la intención o la forma de jugar, es muy atrevido poner líneas y clasificaciones. Un buen ejemplo es Super Mario Bros., que si lo juego de la forma más habitual es un juego de plataformas solitario, pero si lo juego como un speedrunner se convierte en un problema (un puzle) de optimización, y si lo juego a medias con mi hermano pasa a ser, de alguna forma, cooperativo. Lo mismo pasa con el puzle. Reduciéndolo al mínimo, cualquier videojuego es un puzle. Como informático, me lo imagino como “tener que descifrar el código de inputs” para llegar al final del juego. Es el mismo concepto que explotan los TAS (Tool-Assisted Speedruns). Desde esta perspectiva, el puzle no sería ni un género ni un elemento; sería el todo.

Pero, en la práctica, acotamos más.

Volvamos a los artefactos en los que el puzle sobresale como elemento: las aventuras gráficas. No jugamos a Monkey Island o a Fate of Atlantis por sus puzles, por más que nos puedan gustar. Los jugamos porque algo nos impulsa a avanzar en sus hilos argumentales. Podemos considerar entonces que estos puzles son elementos del videojuego (y podríamos discutir si puede existir un videojuego sin puzles, entendidos en el sentido más amplio). ¿Pero qué pasa si ese elemento, el puzle, pasa a ser central en el videojuego? Sokoban, por ejemplo, va de nivel en nivel y cada nivel es un puzle, punto. Jugamos a Sokoban por masoquismo puzlero, no para ayudar al mozo de almacén. Entonces, diríamos que el género de puzle es ése en el que el elemento puzle es el hilo conductor, la principal motivación y el protagonista absoluto.

Como conceptualización resulta útil.

No es una clasificación clara y, como veremos, buena parte de los juegos caen en el limbo. Pero no está de más recordar que la propias definiciones de juego (Huizinga, Caillois y posteriores) y de videojuego (como las características de Juul) tienen a menudo más problemas y casos en la frontera que claridad. Pretender ser capaz de poner una cerca a la definición de puzle hubiese sido pretencioso, así que opté por adoptar un compromiso, explicarlo y seguir adelante con ello, aunque sea abiertamente debatible.

Rompecabezas Mora Puzle

Foto: Romuald Gallofré

¿Se relaciona el puzle con otros géneros históricos o supone una parcela aparte con su propia historia y lógicas?

Hay de todo. Y hay de todo porque, a menudo, depende de la forma del puzle. La historia de los tile-matching games que describe Juul, por ejemplo, está prácticamente excluida de otros géneros. Salvo mezclas improbables como Puzzle Quest, no se suele encontrar de forma consistente en otros géneros. El estilo de Sokoban o los acertijos y enigmas están, en cambio, omnipresentes. Cojamos un RPG o un juego de aventuras, como The Legend of Zelda. Es que si lo miramos con la lente del puzle podría ser un juego de puzle. Personajes que nos dan pistas crípticas (“Eastmost Peninsula has the secret”) o mazmorras laberínticas (y un laberinto es un rompecabezas) que además están llenas de sub-puzles de deslizar piezas, activar interruptores y hacer las acciones en determinado orden. Alundra, que reivindico, es más conocido por sus puzles de columnas de hielo que por su argumento. Los puzles de llave-cerradura son la esencia en los Metroidvanias. Las aventuras gráficas son sus puzles.

De nuevo, a veces el puzle está en el centro y a veces es un elemento más.

En general, diría que hay dos tendencias: los juegos de puzle tan esenciales que por sí solo tienen un relato que contar y los puzles que requieren algo más con lo que generar una simbiosis. Los primeros evolucionan según su propia lógica, mientras que los segundos lo hacen de la mano de sus asociados, a veces cogiendo más importancia, a veces incluso desapareciendo.

¿Es el puzle un nicho?

El puzle como género era un nicho hasta Tetris, dejó de serlo tras él, volvió a serlo con el polígono, dejó de serlo con la Nintendo DS y ha vuelto a serlo con la inundación del AAA. Creo que en su naturaleza está ser como la marea, que sube y baja, pero siempre está porque responde a una fuerza mayor que él mismo. Me ha quedado muy poético pero el punto es que creo que lo de ser mainstream o no depende más de las tendencias sociales e industriales que de la naturaleza del juego. El puzle requiere reflexión, pausa, inteligencia y paciencia, cualidades marginadas a día de hoy en favor de la acción, la velocidad, los reflejos y la inmediatez.

En el libro incluyes aventuras destacadas como Ghost Trick, Myst o Catherine. ¿Cuál es la relación entre puzle y aventuras?

Son los tres ejemplos borderline más marcados por su proximidad a la aventura, sin duda. Y los tres ilustran la tensión entre puzle y aventura de tres formas distintas. La aventura no puede existir sin el elemento rompecabezas. Aventura implica descubrir cosas desconocidas y lo desconocido es el enigma, es ese instinto del que habla Danesi. Una bifurcación es una decisión de puzle. Mover unas piedras o recoger un objeto (y usarlo en otro lado) es puzle. Visitar distintas localizaciones para recoger pistas, investigar… es puzle. Y aquí hay una transición interesante. Coge una aventura gráfica (Indiana Jones y la última cruzada) y sustituye los puzles por QTEs. ¿Qué tenemos? Una especie de película interactiva al estilo Dragon’s Lair. Elimina ahora los QTE (o haz la suposición de que todos los inputs son correctos siempre) y ¿qué ocurre? Que tenemos una película. Es decir, quizás el puzle es el componente que hace que un videojuego de aventuras no sea equivalente una película.

En esos tres juegos el puzle no se puede eliminar sin cambiarlos completamente.

Los casos de Myst, Ghost Trick y Catherine son particulares. Uno se pone una barrera mental entre videojuegos de puzle y puzles en videojuegos, pero hay juegos que caen en esa barrera. Myst, por ejemplo, es un puzle en sí mismo. No tiene un hilo conductor marcado como Monkey Island sino que sitúa al jugador, en primera persona, dentro de un puzle (que es la isla entera). Es un ejemplo extremo de videojuego que es puzle en sí mismo. Ghost Trick tiene algo distinto en particular y es que no hay prácticamente transiciones entre escenas y cada escena es un puzle. Además, es un puzle muy del estilo de The Incredible Machine, en el que el objetivo es conseguir la reacción en cadena deseada. Es que diría más, la propia mecánica del juego (vuelta atrás en el tiempo), pistas y diálogos empujan a tratarlo como un puzle. Y Catherine es paradigmático porque pone una fuerte separación entre su parte narrativa y su parte de puzle. Es como si fueran dos juegos en uno (tres si contamos la máquina recreativa, otro puzle) pero, aun siendo así, la integración de aventuras y puzle está más conseguida que en la inmensa mayoría de aventuras, que lo hacen de forma poco natural.

¿Qué hay de géneros como el RPG?

Hay lloros. Y los hay porque, como el puzle, son juegos que tradicionalmente ponían su peso en la paciencia y en la inteligencia. El RPG por turnos, que es una forma ligera de puzle (imaginemos la batalla contra un jefazo como un momento en el que hay que pensar la mejor estrategia, las debilidades y la secuencia de acciones óptima o suficiente para salir victorioso), prácticamente ha desaparecido. Murieron con la primera PlayStation, como quién dice.

¿Y el Tactic RPG?

Al TRPG (o incluso SRPG), mi otro género favorito, le pasa algo parecido, aunque sobreviviese un poco más, con grandes juegos en GBA y PSP. Pero también desaparece; incluso se han cargado un concepto híbrido como Valkyria Chronicles, que ahora ya es de “acción” en Revolution. Un Tactical RPG es también un puzle: ¿Cómo llevo mis unidades a la victoria u objetivo en esta disposición y en este tablero? Requiere paciencia y reflexión. Tiempo. Y, a menudo, tiene poca “rejugabilidad”, sea lo que sea esta palabra del demonio. Es también un ejercicio solitario, difícilmente da para un online entretenido. Así que no es difícil entender que nade en el mismo nicho que el puzle en la actualidad, pero con una diferencia importante: es mucho más caro y complicado de producir, en general, así que ni en los entornos indie es fácil encontrar Tactical RPG decentes, mientras que sí se encuentran juegos de puzle espectaculares.

Image result for catherine tower

Las torres de Catherine, juego que combina aventura y puzles

¿Tiene el puzle forma de encajar en la narrativa?

Ocurre un poco lo que comentábamos en la relación entre puzle y aventura, pero aquí la principal problemática es cómo encajarlo. No es en lo que me he centrado, así que seguro que hay mucha gente que sería capaz de analizarlo mejor que yo, pero se me ocurren tres casuísticas. La primera de ellas es la habitual: puzles que se “intercalan” en la narrativa y que a menudo conectan poco con ella. Las aventuras gráficas tradicionales, por más que nos gusten, suelen ser buen ejemplo de ello: es necesario resolver un obstáculo para seguir avanzando pero es difícil entender el motivo de ese obstáculo. Quizás tenga sentido que Guybrush tenga que realizar tres pruebas para convertirse en pirata, pero no sé si el famoso puzle de la cabra en Broken Sword tiene mucho sentido dentro de la narrativa del juego. Incluso El Profesor Layton es un pobre ejemplo de integración entre ambas. En la resolución de grandes misterios nos encontraremos ayudando a alguien a aparcar su coche, a identificar el hermano menor o a saber leer la hora. Se percibe la desconexión: en las aventuras gráficas se nota que el puzle está “impostado” para suponer un obstáculo y en Layton es la narrativa la que está “impostada” para conectar sus acertijos.

¿Y la segunda perspectiva?

La segunda perspectiva es la que admite que son mundos distintos pero aun así consigue buenos resultados. Como Catherine. La justificación del puzle es argumental (con las posibilidades de los sueños no se discute) y en un reino absolutamente separado de su narrativa a nivel de mecánica. Luego se conecta con la narrativa por los miedos del protagonista y todo tiene cierto (sólo cierto) sentido.

¿Cuál sería la tercera?

La tercera es la menos habitual y se da en casos como Braid, donde la integración se hace de tal forma que forman parte de una misma cosa, como en su nivel final. Es lo más difícil, claro, pero también lo más gratificante.

Hay géneros que surgen con un gran foco en los puzles y poco a poco lo abandonan, como el survival horror.

Aquí tienes un muy buen punto que creo que se debería analizar en más profundidad, porque se parece a otros casos como el del RPG comentado antes. Es verdad que el “survival horror” nace muy cercano a la aventura gráfica (Alone in the Dark da la sensación que se despega de ella) y, por lo tanto, entiende que el puzle es un elemento clave. El enigma combina bien, además, con sus aires de misterio y suspense. Pero la evolución de eso ha sido hacia la acción, hacia las esperas nulas (salvo cargas). La paciencia y las esperas se han devaluado y sólo queda espacio para la productividad industrial. No soy ni mucho menos aficionado al género y no puedo hablar del mismo con profundidad, pero sólo hace falta repasar Resident Evil para entender de lo que hablamos. ¿El motivo? No se me ocurre otro que no sea comercial y/o económico.

¿Qué tipo o modo de jugador necesita el puzle?

Cuando decidí incluir un pequeño capítulo dedicado al diseño de videojuegos de puzle, lo hice mediante las aportaciones de autores de referencia. Me gustó especialmente lo que decía Emilio Joyera en su cuenta de Twitter (y por eso lo añadí) porque entraba en esa doble dinámica, en ese pacto puzlero. “¿Qué debe cumplir un puzle para ser bueno?” es una pregunta interesante, pero quizás lo es más pensar “¿Qué debe cumplir un buen jugador de juegos de puzle?”. Y aquí está una de las gracias de este tema, porque aunque ciertas tipologías de jugador pueden ser más afines a un tipo u otro de juegos de puzle, lo que marca la diferencia es su actitud.

Una actitud que va más allá de las tipologías clásicas del jugador.

Si coges una tipología ya un poco gastada como la de Bartle seguro que la mayoría de enamorados del puzle se acercan al “explorador”, pero eso es simplificar el panorama. El puzle necesita un jugador que se enfrente al reto de cara, que le guste observar, entender su entorno, que se haga preguntas y se las cuestione, que las experimente, que pruebe y que acepte equivocarse como método de aprendizaje. Pero lo que más necesita son dos valores básicos: la superación de uno mismo y saber disfrutar del camino. En el puzle no hay atajos; cualquier trampa o truquillo rompe el espejismo rápidamente, mucho más que en cualquier juego de acción. El objetivo principal del puzle no es solucionarlo, porque una vez solucionado se termina; en su lugar hay que abrazar el proceso, el camino, y el aprendizaje que se deriva de ello. Quizás por eso el puzle está en declive hoy en día; no cabe en una sociedad cuyos individuos tienden a autoengañarse (o a vivir identidades ficticias) y cuyo principal objetivo es ser productivo.

El puzle, así, tendría que ver con los juegos de paciencia.

El puzle más puro lo tiene todo que ver, entendiendo paciencia como algo presente y necesario en el proceso de reflexión. Resolver algunos puzles en Sokoban o Adventures of Lolo puede llevar más de una sesión, más de un día. Hace falta paciencia para no desesperarse en el primer intento, como hace falta paciencia para entender que si la solución no sale hoy, quizás salga mañana. Hay que reivindicar la paciencia, porque sin paciencia no hay espera, y la espera es un mecanismo que el ser humano necesita como respirar. Crecer es esperar, aprender es esperar, incluso reproducirse es esperar.

Related image

Adventures of Lolo, uno de los juegos más destacados por el autor

En el libro haces referencia a la catalogación de problemas NP. ¿Cuál es la relación del puzle con las matemáticas?

Puzle y matemáticas van de la mano porque resolver un puzle es resolver un problema matemático. Es más, va todo de la mano con la informática en su vertiente más científica (y, por lo tanto, próxima a la parte matemática). El P, NP, NP-completo y NP-difícil es en parte filosofía pero es muy importante para entender la complejidad de los problemas y buscar formas de resolverlos*. Los problemas P no son interesantes para el jugador por su simpleza final (tienen “truco”, por así decirlo). Es como un laberinto: si sigues siempre la pared con la mano derecha siempre terminas saliendo. Tiene poca gracia. Los NP balancean reto (para solucionarlo) con caramelo (la solución es fácil de comprobar).

La complejidad equilibrada, entonces, está en no tener truco pero ser comprobable.

Los buenos puzles, en general, aparte de tener buen diseño encuentran sus principios matemáticos en NP. Y los que son más complejos que esto, lamentablemente, terminan por desorientar. Sokoban empieza bien pero más de uno me entenderá cuando digo que los niveles avanzados son un peñazo, y lo son porque hay un espacio demasiado grande de posibilidades para nuestro limitado cerebro.

Un puzle que requiere reflejos, ¿es un puzle?

Mira, esta pregunta me la hice al inicio porque el usuario medio piensa en puzle y piensa en Tetris y eso me parece entre fascinante y terrorífico. Terrorífico porque un juego que se basa en los reflejos es un juego de acción (o debería serlo) más que de puzle, y Tetris en general lo es. Fascinante porque Tetris es un icono global. Y la gente lo asocia a juego de pensar, lo asocia a ser más inteligente, lo asocia a rompecabezas. Es una contradicción en el núcleo del género y del libro, pero no cabía la posibilidad de obviarlo. Sucesores y derivados añadieron elementos mucho más estratégicos, como piezas de distinto color, y dificultan el debate.

¿Entonces Tetris no es un puzle?

si me pusiese exquisito diría que un juego como Tetris tiene elementos de puzle pero no es un juego de puzle. ¿Que por qué está en Rompecabezas? Porque sin Tetris no se puede explicar la historia del puzle.

Una de las cosas que se hacen manifiestas en el libro es la importancia de la estética kawaii (mona) en los puzles japoneses. ¿A qué crees que se debe?

No lo había pensado pero es cierto que lo “mono” está omnipresente en el mundo del puzle y yo quizás iría un poco más allá y diría que, en general, incluso el cuidado estético es clave. No los gráficos rompedores y el alto número de polígonos, no. La coherencia y el detalle. Y creo que se puede deber a lo que hemos visto antes, a su componente de paciencia. Un entorno agradable hace ese tiempo de reflexión mucho más llevadero. Puede ser que tenga incluso un elemento de contrapunto a la frustración de no encontrar la solución, de alegrar los corazones que el puzle rompe. Y esto, en Japón, se traduce en kawaii por todos lados.

Image result for boxboy

BoxBoy es, para Mora, uno de los mejores representantes del puzle en la actualidad

El puzle es un género poco dado al fotorrealismo: gran parte pueden considerarse juegos abstractos. 

Es que si todos los juegos representan un modelo, el extremo de los modelos es el puzle. Si una cosa hace que me gusten especialmente este tipo de juegos es que se despojan de la mayoría de cosas innecesarias, plantan la mecánica y la explotan. Son transparentes. No tan transparentes como un juego de mesa, claro, pero lo más transparentes posible.

¿Cómo crees que afecta esto a su aceptación y sus audiencias?

Eso hace que su audiencia se fije en dos cosas, su funcionamiento y su dinámica, por encima de la estética, la espectacularidad o la potencia bruta. Es una audiencia interesada en el juego en sí y poco interesada en, por ejemplo, la plataforma o las características técnicas. Es despreciado por otros por simple. ¿Consecuencia? El puzle vive en plataformas móviles diversas pero está poco presente en las consolas más deslumbrantes técnicamente, como la PS4 o la XBOX One.

En el libro mencionas la ausencia de reto en Monument Valley. ¿Puede que esta obra sea más bien un juguete digital, una suerte de caja de música? 

Con esta pregunta haces que me dé cuenta de esto. En juegos como Monument Valley, algo falla. Te gusta pero difícilmente lo calificaría como juego. Y quizás aquí esté el quid de la cuestión; quizás Monument Valley, como otros, sea más un juguete que un juego. Algo con lo que experimentar y deslumbrarse, parecido a algunos niveles de Captain Toad, por ejemplo (aunque no se me ocurriría, ni por asomo, ponerlos al mismo nivel: Captain Toad es un juego brillante). Por lo tanto, Monument Valley debería ser analizado como un juguete digital y no como un juego. Tiene sentido.

¿Qué relación tienen el juguete y el puzle?

La relación del juguete y el puzle es estrecha, pero diría que el juguete de puzle es sólo un subconjunto relativamente pequeño en la intersección del reino de los juguetes y el de los puzles. Es como la “condensación” física del puzle.

Imagino que después de publicar el libro te habrán llegado muchas recomendaciones (o quejas: “te has dejado X”). ¿Qué juegos has descubierto después que te hayan llamado la atención?

No paran de aparecer juegos, nuevos y antiguos. La selección era para ejemplificar tendencias y casos, pero, de base, ya era consciente que muchos los dejaba fuera (o me veía forzado a dejarlos fuera). Y debía haberlos jugado todos, así que las recomendaciones de último momento no pudieron entrar por tiempo. Pero lo de después ha sido genial, porque me han llegado recomendaciones de juegos que no conocía y que debería haber incluido, o he descubierto juegos que me han dejado alucinado y con los que no me topé durante mi búsqueda. Te voy a mencionar algunos que no están y que me vienen a la cabeza que he descubierto después (o me los han mencionado):

  • Cosmic Express: lo compré en Steam tras entregar el manuscrito y es un juego excelente de puzle, como el resto de juegos de su creador. Sokobond sí lo mencioné (pero no reseñé).
  • Toki Tori (y 2): no lo conocía y hubiese estado interesante incluirlo no sólo por ser un gran juego de puzle sino por su historia. El primero empieza en 2001 en GBC y a base de remakes y ports llega hasta nuestros días. El segundo es quizás mejor por el uso de sus recursos y es de 2013.
  • Snakebird: este me voló la cabeza. La complejidad que alcanza usando prácticamente recursos nulos es brutal. Eso sí, se vuelve muy difícil enseguida y diría que tengo la corazonada que es más difícil que NP-hard, así que desmotiva a menudo.
  • Koro Koro Puzzle – Happy Panechu!: es el primer juego de GBA que hizo uso del sensor de inclinación y es un ejemplo curioso que, además, no se puede jugar en emulador (y es complicado de jugar en las GBA que no sean la primera).
  • Nontan to Issho: Kuru Kuru Puzzle: este es de Super Famicom y es sencillo, pero tiene dos cosas que lo hacen especial. Lo diseñó Akira Kitamura (Rockman, Cocoron) tras salir de Takeru. Creo que es su último juego antes de desaparecer del sector. Es curioso porque las fichas giran en el eje de la Z.

Hay decenas más y no hay forma de dejar de comprar juegos de puzle, pero creo que con estos ya tienes unos buenos ejemplos.

Foto: Impact Game

Estás trabajando en tu tesis doctoral. Como académico, ¿qué te parece la investigación sobre puzles? ¿Lo han trabajado bien los Game Studies?

Creo que está muy poco trabajado. Juul hizo el único intento relevante con su clasificación de los juegos de conectar-3, pero incluso ese buen ejercicio (y soy poca cosa como para criticar a Juul) tiene sus lagunas, dejándose sin incluir pilares como Columns. Y, de nuevo, los juegos de conectar-3 tienen más de puzle que Tetris pero mucho menos que cualquier otro juego del género, así que incluso desde esa perspectiva los Game Studies sólo han rascado la superficie. Esto tiene varias justificaciones en mi opinión. Los Game Studies no dejan de ser una disciplina joven y que sigue enfrascada (nunca mejor dicho) en una discusión casi de identidad. Hace 20 años que se pregunta qué es el juego (o el videojuego) y cómo tratarlo. Y es una discusión necesaria, pero, mientras tanto, hay muchos temas que sólo se han rascado en su superficie, con suerte. Otra justificación para el caso del puzle es de fondo: el puzle se conecta tanto con la matemática y las ciencias de la computación que requiere una vocación mucho más transversal del perfil habitual. Si es difícil encontrar académicos matemáticos del área del puzle y es difícil encontrar académicos del videojuego, ¿cómo vamos a encontrar académicos en la intersección que, además, estén interesados en el ámbito? El puzle ha sido tratado medio en profundidad sólo por la matemática y la antropología. Queda mucho campo por recorrer.

¿Qué metodología de análisis es la más adecuada para entender un puzle?

Esta me supera, pero me recuerda a una anécdota que tengo grabada a fuego. Hace años acompañé a mi futura mujer a entrevistar a un pintor de relevancia en Barcelona. No me acuerdo cómo sucedió exactamente, pero en algún momento solté un ingenuo comentario sobre lo relativa que era la belleza de, por ejemplo, un cuadro. El pintor me respondió que eso eran tonterías. “Cuando miras un cuadro, sabes directamente si te gusta o no”. Personalmente, con los puzles me pasa parecido. Sólo debes jugarlo un rato para ver si hace clic o si no. Así que se pueden reseñar, se pueden describir, se pueden caracterizar, se pueden disfrutar… pero analizar un puzle (o un juego/videojuego por extensión) se me antoja como intentar descifrar la fórmula secreta de algo que, en realidad, es parcialmente mágico. En el puzle, además, toma especial importancia la sensación personal de reto, que es algo muy subjetivo y personal.

Para acabar, ¿cuál sería tu acertijo favorito?

Es difícil poner un favorito, pero siempre me había apasionado la mitología griega y romana, así que dejaré el mismo que cito en el libro, uno de los más antiguos documentados y probablemente el más famoso: “¿Quién es el ser, el único ser de entre todos los habitantes de la tierra, las aguas, el aire, que tiene una única naturaleza, pero posee dos pies, tres pies y cuatro pies, y es más débil cuantos más pies posee?”.

*BONUS: Vista la importancia de P/NP en el puzle, ¿podrías explicar mejor este concepto?

Cuando hablamos de P/NP, hablamos de problemas de decisión. Esto significa que, en general, estamos tratando con problemas de los que esperamos una respuesta binaria y booleana, sí o no, cierto o falso.

  • Los problemas de tipo P los podemos pensar como un subconjunto muy chiquitito del universo de los problemas, que son los que se pueden resolver en tiempo polinomial respecto a la entrada que reciben. Si cogemos un grafo, por ejemplo, y nos preguntamos si se puede pintar en dos colores y que dos nodos de colores distintos no se toquen, el algoritmo consiste en pintar un nodo de un color, pintar los adyacentes de otro y así recurrentemente hasta que o bien dos nodos de un mismo color se toquen o bien se terminen los nodos. El primer caso es “False”, el segundo es “True”. De hecho, es lo mismo que ver si el grafo es bipartido. Fíjate que si tenemos 10 nodos en la entrada, como mucho tendremos que hacer 10 “operaciones”. Si son 100, 100. Aunque no sea un problema de decisión, la multiplicación es un buen ejemplo. Multiplicar dos números de 4 cifras implica hacer 16 multiplicaciones y una suma. 4 al cuadrado. Multiplicar es cuadrático respecto a su entrada, por así decirlo, pero sigue siendo un polinomio. A nivel computacional, estos problemas son “fáciles”.
  • Los problemas de tipo NP es un conjunto más grande (y los P están contenidos en NP). Los problemas NP son verificables en tiempo polinomial pero no parecen ser resolubles en tiempo polinomial. Coge Sudoku, por ejemplo. Si yo te doy una solución, ¿es fácil de verificar? Tendrás que recorrer tres veces la cuadrícula, pero eso no es nada para una máquina de Turing. Pero si te doy un estado inicial, ¿es fácil decir si tiene o no solución? Fíjate que su complejidad incrementa exponencialmente si hacemos más grande el tablero. Sudoku está en NP (es fácil de comprobar) pero no en P (fácil de resolver).
  • Y entrando en terreno más complejo, los NP-completos son los problemas más “difíciles” de NP y que, por lo tanto, si fuésemos capaces de resolver fácilmente un problema NP-completo resolveríamos de golpe todo NP. Los NP-completos forman parte de otro conjunto llamado NP-difícil, con problemas que son, como mínimo, tan difíciles como los NP-completos. Los NP-difícil que no son NP-completos no tienen ni tan sólo forma fácil de verificación.

El gran problema de la informática es el saber si P es igual a NP o no, con recompensa millonaria para quien lo demuestre. Todo parece indicar que no, pero mientras no sea posible encontrar la demostración, el tema sigue abierto.

Pero tras este rollo, a lo que iba. Su relación con el puzle. Te lo resumo así:

  • Los puzles que se asemejan a los problemas P son, en general, poco interesantes. Si los puede resolver un algoritmo sencillo, también los puedes resolver tú siguiendo el mismo algoritmo. Es decir, es poco complejo sacar la solución.
  • Los puzles que se asemejan a problemas de tipo NP son mucho más interesantes, porque no es fácil computar la solución pero sí es fácil comprobarla. Buscaminas, sin ir más lejos, es NP-completo.
  • Los puzles NP-difíciles (o todavía más allá, PSPACE, que ya es otra historia) se van de las manos, para ser coloquiales. Sokoban es PSPACE.