¿Es finito el número de rompecabezas únicos de sudoku que se pueden resolver?

Answer 1

Voy a dar una respuesta contraria. No, no es finito. Otros respondedores han hecho dos suposiciones: que los rompecabezas de Sudoku son 9 × 9 y solo usan números. Tampoco es verdad.

La gran mayoría de los rompecabezas de Sudoku son de 9 × 9, pero he visto rompecabezas tan pequeños como 4 × 4 (sí, son bastante tontos) y tan grandes como 25 × 25. No hay límite para el tamaño de un Sudoku, por lo que no hay límite para el número de rompecabezas de tamaño arbitrario.

Hay otro factor. Hay rompecabezas de sudoku que no usan números. Wordoku, Colordoku, Symdoku. Mi compañía, Puzzazz, ha publicado rompecabezas de Wordoku y Symdoku, y no hay límites para la cantidad de símbolos diferentes que uno podría usar en un rompecabezas de Symdoku. Creamos un conjunto de símbolos en el que cada símbolo tenía una cantidad de puntos entre 1 y 9, pero se podían usar formas arbitrarias, frutas, gatos e incluso fotografías arquitectónicas. Realmente no hay límite.

Dicho esto, hay un límite práctico para el tamaño del rompecabezas que puede caber en una hoja de papel o en una pantalla, y dos rompecabezas que son isomórficos entre sí (es decir, los rompecabezas son equivalentes pero con diferentes símbolos) podrían considerarse ser el mismo rompecabezas

Entonces, la respuesta es que hay un número infinito de acertijos potenciales, pero, prácticamente hablando, hay un número finito (aunque increíblemente grande) que puede tener.

Para los rompecabezas de Sudoku 9 × 9, hay 6.670.903.752.021.072.936.960 cuadrículas aparentemente únicas. Cuando se tienen en cuenta las cuadrículas de solución equivalentes, solo hay 5.472.730.538 cuadrículas de respuesta únicas. Estas cuadrículas de respuestas se pueden representar en una variedad de acertijos diferentes. Ese número es extremadamente difícil de calcular, pero el número si los rompecabezas mínimos de Sudoku (lo que significa que eliminar un dado lo hace insoluble) es del orden de 10 ^ 25. El número total de acertijos presentados de forma única, descontando cuadrículas equivalentes) es del orden de 10 ^ 44.

Answer 2

Sí, es finito. Olvidemos las reglas de Sudoku por un minuto, ahora, supongamos que tuviera que llenar una cuadrícula de 9 × 9 con 10 símbolos (1 a 9 y un espacio en blanco), el total de configuraciones posibles que podría generar es finito (ejercicio). Si no permitiera que esas configuraciones que no están permitidas por las recetas de Sudoku sean un “rompecabezas de sudoku único y solucionable”, este número solo puede reducirse y, por lo tanto, ser finito. QED

Answer 3

Bueno, el juego presenta un número finito de cuadros (81) y una selección finita de números que pueden ir en esos cuadros (ya sea un número o un espacio en blanco; por ejemplo, podemos considerar el espacio en blanco como un 0, por lo que tenemos 10 posibilidades para cada caja).

Esto lleva a un número finito de combinaciones en el tablero de Sudoku, de las cuales una parte más pequeña es solucionable. Desafortunadamente, no puedo ayudarte con la cantidad de combinaciones solucionables, pero estoy seguro de que alguien más puede hacerlo. 🙂

Answer 4

Suponiendo un rompecabezas de Sudoku estándar de 9 × 9 lleno de dígitos 1–9, solo hay un número finito de rompecabezas.

Considera un rompecabezas. Cada celda contiene uno de los 9 dígitos o está en blanco. Hay 10 posibilidades para cada celda. Eleve eso a la potencia 81 (hay 81 celdas en la cuadrícula), para obtener cuadrículas [matemáticas] 10 ^ {81} [/ matemáticas] que probablemente puedan ser rompecabezas.

Cualquier rompecabezas debe estar entre estas cuadrículas [matemática] 10 ^ {81} [/ matemática], aunque muchas de estas cuadrículas no son acertijos de Sudoku válidos (ya sea porque tiene una contradicción (incluidas las cuadrículas donde ya tiene dos dígitos idénticos en la misma fila / columna / cuadro), o tiene múltiples soluciones). El número de acertijos está limitado anteriormente por [matemáticas] 10 ^ {81} [/ matemáticas], por lo que sin duda es finito, si es grande.

---

Ahora, hay varias variaciones de Sudoku. Puede tener una cuadrícula más pequeña / más grande. Si no limita el tamaño de la cuadrícula, entonces hay claramente infinitos rompecabezas: para una cuadrícula [matemática] n ^ 2 \ veces n ^ 2 [/ matemática], llénela a una solución de Sudoku (puede probar que siempre es posible), y luego elimine un número. Ahora tienes un rompecabezas, aunque sea trivial. Pero tiene un rompecabezas para cada [matemática] n [/ matemática], por lo que hay infinitos rompecabezas (porque hay infinitamente [matemática] n [/ matemática]). También puede reemplazar los símbolos por otra cosa (letras / símbolos / imágenes / lo que sea), aunque diría que esto es la mayoría de las veces solo una alteración estúpida.

También hay variaciones reales de Sudoku. Para mencionar algunos de ellos: Regiones irregulares (las regiones no son necesariamente cuadros de 3 × 3), Diagonal (cada diagonal también debe tener 1–9 una vez cada una), Asesino (hay “jaulas” que dan la suma de números en ellas —Esta es una de las razones por las que el Sudoku con números es más popular, porque es más fácil hacer variaciones a partir de ellos), Mayor que (hay signos de desigualdad que deben obedecerse) …

Siempre que se nos ocurran variaciones, obtenemos nuevos acertijos. Por supuesto, no son acertijos de Sudoku adecuados porque hay nuevas reglas. Pero si considera el Sudoku y las variaciones, es probable que tenga un número infinito de ellas; siempre que pueda encontrar variaciones, obtendrá rompecabezas.