Candy Crush es un fenómeno, como lo fue Angry Birds en su momento. Parece ser un juego simple pero considerando el número de descargas que el juego ha tenido, es claro que cae en la categoría de adictivo. Sin ir muy lejos, he visto gente en el transporte público jugando dicho juego. La razón por la cual lo es, dicen los matemáticos, es que es un problema NP-Difícil
Toby Walsh, de la Universidad de New South Wales, en Australia, tiene una prueba que pone a Candy Crush en ese sitio e incluso sugiere formas de hacer el juego mejor. Candy Crush lo juegan un estimado de quinientos millones de personas en Facebook, iOS o Android. Es una variante del juego clásico de tres en línea. El juego que se analizó no tiene un tamaño fijo, pero en el fondo es el mismo juego: el tablero se llena con una selección de dulces que vienen en seis diferentes colores. El resto es intercambiar los dulces en las vecindades para crear tres del mismo color. Cuando esta meta se logra, desaparecen y caen de la parte superior nuevos dulces para reemplazarlos. Se obtienen puntos por cada tres dulces que desaparecen. El reto es lograr cierta puntuación S en K intercambios.
Es bastante fácil probar que el problema es NP (ver aquí si quieres saber qué significa en términos comunes esta expresión NP). Si se da un conjunto K de intercambios, que dan como puntuación S, entonces se puede checar que si esto pasa en un tiempo polinomial, entonces el problema es NP.
En su artículo, Walsh explica cómo mapear el juego en un problema que se conoce como NP-Completo, esto lleva a probar al autor que Candy Crush es NP-Difícil. Este tipo de problemas son, por decir lo menos, tan difíciles como los problemas más difíciles NP. La demostración de Walsh se hace convirtiendo el juego en un conjunto de funciones booleanas.
A partir de esto, el artículo considera algunas modificaciones para hacer que los últimos niveles en Candy Crush sean NP-Difíciles, por ejemplo, cubriéndolos con capas. Estos son igualmente problemas NP-Difíciles. El autor se pregunta si Candy Crush (presumiblemente en cada nivel) tiene siempre una solución óptima. Parece el autor probar que no, parece ser que hay muchas soluciones y esto es también NP-Difícil.
Referencias: