Informática e IAPrepublicaciónTeoría4 min de lectura

UNA CONSTANTE DE 10⁴⁰ REDUCIDA A 30,5 PARA LOS CUBOS DE RUBIK GIGANTES

El cubo de Rubik, que acaba de cumplir 50 años, es quizá el rompecabezas más conocido del mundo, y una de sus preguntas centrales es fácil de enunciar: en el peor de los casos, ¿cuántos movimientos hacen falta para resolverlo? Para el cubo clásico de 3×3×3, la respuesta se conoce con exactitud: 20 movimientos, un resultado publicado en 2014 por un equipo del que formaba parte Tomas Rokicki, uno de los autores de este nuevo artículo.

Para cubos más grandes, con n capas a lo largo de cada arista, la respuesta exacta está fuera de alcance: resolver de forma óptima un cubo n×n×n dado es incluso NP-completo. Pero en 2011, Erik Demaine y sus colegas mostraron cómo crece el peor caso: en proporción a n² / lg n, donde lg es el logaritmo en base 2. Es un factor logarítmico mejor que los métodos estándar, que resuelven las piezas esencialmente de una en una.

Una demostración con una constante absurda

Había una trampa. El resultado de 2011 garantizaba el ritmo de crecimiento, no el número que lo multiplica. Al desarrollar ese algoritmo, los autores encuentran que su constante es de unos 1,01 × 10⁴⁰. El culpable es una comprobación por ordenador que demostró que ciertos movimientos podían alcanzar todas las disposiciones de un grupo de 24 piezas, sin decir con qué rapidez. La única cota segura para esa longitud era el tamaño de ese grupo de disposiciones, unos 3,1 × 10²³ pasos, y la fórmula acaba usando el enorme número 24! (1 × 2 × … × 24, unos 6,2 × 10²³) en dos lugares. En cambio, la cota inferior —el número de movimientos que necesita casi cualquier cubo desordenado— tiene una constante modesta de unos 12,88. Por eso, muchos en la comunidad creían que un algoritmo así nunca podría ser práctico para tamaños razonables.

Jeremy Mrzyglocki, Tomas Rokicki, Maxine Perroni-Scharf y Erik Demaine, del MIT, la TU de Múnich y Palo Alto, han logrado ahora que esa constante sea explícita y pequeña.

Redes de ordenación para las piezas del cubo

En un cubo grande dominan las piezas centrales: su número crece como n², mientras que las esquinas y las aristas solo añaden términos proporcionales a n. Las piezas centrales se reparten en familias de 24 que solo pueden intercambiarse entre sí. La herramienta básica es el conmutador, una secuencia de la forma A B A′ B′ que deja casi todo en su sitio y permuta solo tres piezas de una familia. El equipo encontró secuencias de movimientos para los 4.000 intercambios utilizables de tres piezas, cada una de 12 movimientos como máximo.

Dos ideas hacen bajar la cuenta. Primero, el mismo conmutador puede aplicarse a muchas familias a la vez, a lo largo de grupos enteros de filas y columnas. Segundo, en lugar de resolver cada familia por separado, todas las familias siguen una misma secuencia universal fija de intercambios, y simplemente se saltan los que no necesitan. Un lema lo une todo: una secuencia universal de L etapas da una constante principal de L/2.

Para acortar esa secuencia se toman prestadas herramientas de las redes de ordenación (sorting networks) de la informática, patrones fijos de comparaciones que ordenan cualquier entrada. Una red de ordenación óptima de seis entradas da 96 etapas, y por tanto una constante de 48. Unas redes que dividen las 24 posiciones en grupos de 12 y luego de 4, halladas mediante búsqueda por ordenador, la llevan a 72 etapas (36). Por último, permitir movimientos que barajan más de tres piezas a la vez y dividir las posiciones de otro modo la lleva a 61 etapas.

Treinta coma cinco

El teorema: cualquier cubo n×n×n puede resolverse en como máximo 30,5 n²/lg n movimientos, más términos que se vuelven despreciables para n grande. La constante mejora en un factor de más de 3,30 × 10³⁸, y queda a un factor de 2,37 de la cota inferior (30,5 / 12,88). Para la versión plana n×n×1, usada como calentamiento, la constante baja de 12 o 18 a 1,5.

Ocho fotogramas de la resolución de un cubo de 256 capas, mostrado como caras desplegadas y como pequeños cubos, del ruido desordenado a los colores uniformes.

Ocho fotogramas equiespaciados de la resolución de un cubo de 256 capas por lado: las caras desordenadas se convierten en colores uniformes. — Figura 1.1, Mrzyglocki et al. (2026), arXiv:2611.11018.

El algoritmo se ejecuta en un tiempo proporcional al número de piezas, y los autores ofrecen un resolvedor de código abierto, con scripts que comprueban exhaustivamente cada red en la que se apoya. Su propia comparación lo sitúa por delante de los resolvedores existentes a partir de aproximadamente n = 840; han renderizado resoluciones de cubos con 256 y 65.536 capas por lado.

El 2,37 es un enunciado asintótico: los términos menores de la fórmula no están determinados, así que no da un recuento exacto para un cubo concreto. Las mejoras futuras, sugieren los autores, podrían venir de otras formas de agrupar las piezas en redes de ordenación y de mejores intercambios de tres piezas; y la misma maquinaria podría abordar otros rompecabezas gigantes, o hipercubos de cuatro y cinco dimensiones.