Un rompecabezas Survo es una especie de rompecabezas lógico presentado (en abril de 2006) y estudiado por Seppo Mustonen. [1] El nombre del rompecabezas está asociado con el sistema Survo de Mustonen, que es un entorno general para la informática estadística y áreas relacionadas. [2]
En un rompecabezas Survo, la tarea es llenar una tabla m × n con números enteros 1, 2, ..., m · n de modo que cada uno de estos números aparezca solo una vez y las sumas de sus filas y columnas sean iguales a los números enteros dados en la tabla. parte inferior y derecha de la mesa. A menudo, algunos de los números enteros se dan fácilmente en la tabla para garantizar la unicidad de la solución y/o facilitar la tarea. [2]
Hasta cierto punto, los rompecabezas de Survo se parecen a los de Sudoku y Kakuro . Sin embargo, los números utilizados en la solución no se limitan a 1, 2,..., 9 y el tamaño de la cuadrícula del rompecabezas suele ser muy pequeño. Resolver acertijos de Survo también está relacionado con la creación de cuadrados mágicos . [3]
El grado de dificultad para resolver los acertijos de Survo varía mucho. Los acertijos fáciles, destinados a niños en edad escolar, son puros ejercicios de suma y resta, mientras que los más exigentes también requieren un buen razonamiento lógico. Los acertijos más difíciles de Survo no se pueden resolver sin computadoras. [4]
Ciertas propiedades del sistema Survo, como la informática editorial y la operación COMB, que crean, por ejemplo, particiones enteras restringidas , permiten resolver los acertijos de Survo.
Los acertijos Survo se publican periódicamente en Finlandia por Ilta-Sanomat y la revista científica de la Universidad de Helsinki desde septiembre de 2006. La resolución de acertijos Survo fue uno de los tres temas principales en el examen de ingreso nacional de las universidades finlandesas en informática (2009). ). [5]
Aquí hay un simple rompecabezas de Survo con 3 filas y 4 columnas:
Los números 3, 6 y 8 se dan fácilmente. La tarea consiste en colocar los números restantes del 1 al 12 (3×4=12) en sus lugares para que las sumas sean correctas.
El rompecabezas tiene una solución única que se encuentra paso a paso de la siguiente manera: Los números que faltan son 1,2,4,5,7,9,10,11,12. Por lo general, es mejor comenzar desde una fila o columna con la menor cantidad de números faltantes. En este caso las columnas A, B y C son tales.
La columna A no es favorable ya que la suma 19 de los números faltantes se puede presentar según las reglas de varias maneras (por ejemplo, 19 = 7 + 12 = 12 + 7 = 9 + 10 = 10 + 9). En la columna B la suma de los números faltantes es 10 teniendo solo una partición 10 = 1 + 9 ya que las otras alternativas 10 = 2 + 8 = 3 + 7 = 4 + 6 no son aceptadas debido a números ya presentes en la tabla. El número 9 no se puede poner en la fila 2 ya que entonces la suma de esta fila excedería el valor 18. Por lo tanto, la única opción es comenzar la solución por
Ahora la columna A tiene solo una alternativa 27 - 8 = 19 = 7 + 12 = 12 + 7. El número 7 no puede estar en la fila 1 porque la suma de los números que faltan en esa fila sería 30 - 7 - 6 = 17 y esto no permite ninguna partición permitida. Así tenemos
implicando que el último número de la última fila será 30 - 7 - 9 -3 = 11:
En la primera fila la suma de los números que faltan es 30 - 12 - 6 = 12. Su única partición posible es 12 = 2 + 10 y así ese número 2 estará en la columna C; 10 en esta posición es demasiado para la suma de la columna.
Luego, la solución se completa fácilmente como
Por lo tanto, la aritmética básica y el razonamiento simple son suficientes para resolver acertijos sencillos de Survo como este.
Las reglas de los acertijos Survo son más simples que las del Sudoku . La cuadrícula es siempre rectangular o cuadrada y normalmente mucho más pequeña que en el Sudoku y el Kakuro . [6]
Las estrategias de resolución varían según la dificultad del rompecabezas. [6] En su forma más simple, como en el siguiente caso 2 × 3 (grado de dificultad 0)
Los Survo Puzzles son ejercicios adecuados de suma y resta. [6]
El rompecabezas abierto Survo 3×4 (grado de dificultad 150)
donde no se dan fácilmente ninguno de los números, es mucho más difícil. Además tiene una sola solución.
El problema se puede simplificar dando algunos de los números fácilmente, por ejemplo, como
lo que hace que la tarea sea casi trivial (grado de dificultad 0). [6]
La medición del grado de dificultad se basa en el número de "mutaciones" necesarias para el primer programa de resolución creado por Mustonen en abril de 2006. Este programa funciona utilizando un algoritmo parcialmente aleatorio. [7]
El programa comienza insertando los números que faltan aleatoriamente en la tabla y luego intenta que las sumas calculadas de filas y columnas se acerquen lo más posible a las verdaderas intercambiando elementos en la tabla sistemáticamente. Esta prueba conduce a una solución correcta o (como en la mayoría de los casos) a un callejón sin salida donde la discrepancia entre las sumas calculadas y las verdaderas no puede reducirse sistemáticamente. En este último caso se realiza una 'mutación' intercambiando dos o más números al azar. A partir de entonces se repite el procedimiento sistemático más la mutación hasta que se encuentre una solución verdadera. En la mayoría de los casos, el número medio de mutaciones funciona como una medida aproximada del nivel de dificultad para resolver un rompecabezas Survo. Esta medida (MD) se calcula como el número medio de mutaciones cuando el rompecabezas se resuelve 1000 veces partiendo de una tabla aleatoria. La distribución del número de mutaciones se acerca a una distribución geométrica.
Estos valores numéricos a menudo se convierten a una escala de 5 estrellas de la siguiente manera: [8]
Maryland
El grado de dificultad dado como valor MD es bastante inexacto y puede incluso ser engañoso cuando la solución se encuentra mediante deducciones inteligentes o conjeturas creativas. Esta medida funciona mejor cuando se requiere que el solucionador también demuestre que la solución es única.
Un rompecabezas Survo se llama abierto si se dan simplemente sumas marginales. Dos rompecabezas abiertos de m × n se consideran esencialmente diferentes si uno de ellos no puede convertirse en otro intercambiando filas y columnas o transponiendo cuando m = n . En estos acertijos las sumas de filas y columnas son distintas. El número de acertijos de Survo m × n esencialmente diferentes y con solución única se denota por S ( m , n ). [7]
Reijo Sund fue el primero en prestar atención a la enumeración de acertijos abiertos de Survo. ¡Calculó S (3,3) = 38 estudiando los 9! = 362880 tablas 3 × 3 posibles mediante los módulos de programa de manejo de datos y combinatoria estándar de Survo. A partir de entonces, Mustonen encontró S (3,4)=583 partiendo de todas las particiones posibles de sumas marginales y utilizando el primer programa de resolución. Petteri Kaski calculó S (4,4) = 5327 convirtiendo la tarea en un problema de cobertura exacta .
Mustonen creó en el verano de 2007 un nuevo programa de resolución que confirma los resultados anteriores. Los siguientes valores S ( m , n ) han sido determinados por este nuevo programa: [9]
El cálculo de S (5,5) ya parece ser una tarea muy difícil según los conocimientos actuales.
El método de intercambio para la solución de acertijos Survo se creó combinando la idea del programa de resolución original con la observación de que los productos de las sumas marginales indican de manera cruda las posiciones de los números correctos en la solución final. [10] El procedimiento se inicia llenando la tabla original con los números 1,2,...,m·n según los tamaños de estos productos y calculando las sumas de filas y columnas de acuerdo con esta configuración inicial. Dependiendo de cómo estas sumas se desvían de las sumas reales, se intenta mejorar la solución intercambiando dos números a la vez. Cuando se utiliza el método de intercambio, la naturaleza de la resolución de los acertijos de Survo se vuelve algo similar a la de los problemas de ajedrez. Con este método es casi imposible verificar la unicidad de la solución.
Por ejemplo, un rompecabezas 4 × 4 bastante exigente (MD=2050)
se resuelve con 5 intercambios. La configuración inicial es
y la solución se encuentra mediante los intercambios (7,9) (10,12) (10,11) (15,16) (1,2). En el sistema Survo, un sucro /SP_SWAP se encarga de la contabilidad necesaria en el método de intercambio.
Resolver un difícil rompecabezas de Survo puede llevar varias horas. Resolver acertijos de Survo como juegos rápidos ofrece otro tipo de desafíos. [4] La forma más exigente de juego rápido está disponible en la red como un subprograma de Java. [11] En este juego rápido, los acertijos abiertos de 5 × 5 se resuelven seleccionando (o adivinando) los números mediante clics del mouse. Una elección equivocada evoca un intervalo musical melódico. Su alcance y dirección indican la calidad y la cantidad del error. El objetivo es alcanzar la puntuación más alta posible. La puntuación aumenta con las decisiones correctas y disminuye con las incorrectas y con el tiempo empleado en encontrar la solución final.
Hay una versión 4x4 disponible para dispositivos iOS como "Hot Box". [12]