How NOT to solve a sudoku - Cómo NO resolver un sudoku
English
Hi everyone!! Some years ago, when I began learning to code in the first course of university I remember myself thinking how easy could be to solve a sudoku with a computer. We were using MatLab back then and I wasn't particularly good with it so I had enough to worry about trying to pass that subject. I left my little sudoku project for the future. During my college time, we kept using MatLab a lot. Basically, we had at least one subject that required that program every year. When I finished my studies I had improved considerably. It's not that I had created something amazing with it but I felt comfortable using it for maths, graphics and some other different purposes. One afternoon I was doing a sudoku on my own when the idea of writing a script to solve it with the computer came to my mind again. I thought it would be something easy that would require one day or two of work. I was tremendously WRONG. (maybe someone who has studied computer science or has a deeper understanding about algorithms, competitive programming problems, puzzles,.. can do it in one day but that wasn't my case ;) )
My approach to code then was based on brute force. I thought that every time a computer solved a problem it was just a matter of trying all possible solutions and that was how I could write a program to solve any sudoku. But, how do you actually try all the solutions? Where do you start?
Let's consider the next sudoku:
We know that every row has to contain all the numbers from 1 to 9 so the first step could be to fill each row with the remaining numbers there:
All we have to do now is permute the added numbers in each row until we find the solution. For example, in the first row we've added: 1 - 3 - 5 - 6 - 7 - 9. One possible permutation is: 1 - 3 - 5 - 6 - 9 - 7. It doesn't seem so difficult, does it? But how long would it take to solve the sudoku with this approach? Let's see:
We know that all the possible permutations of n numbers is n!. n will be the number of empty spaces in each row. The total number of possibilities we would have to try would be the multiplication of all the permutations for each row:
In this case the result is:
If we consider that a modern computer can try 10^9 possibilities each second (this is a huge exaggeration by the way), it would take 30000 YEARS!!!! to solve the sudoku. This example is a very easy sudoku. If you try to solve it by hand, it shouldn't take longer than 5 minutes. I did this calculus with sudokus of different levels and it was interesting to find out that the level of a sudoku is not directly related to the amount of empty spaces it has. Although the results were different depending on each distribution, there was never a case that could be solved in reasonable time.
So that is the end of the story. After several days coding, I realized that my algorithm wasn't gonna solve anything and that coding, computers and problem solving weren't just about brute computational force. I had to come up with something different and maybe write a lot more code. If you want to see how I actually solved it, you can visit the link below. I uploaded it to my Mathworks Community Profile. I thought for a while to write an app (Android or iOS) for it but haven't found the time yet. Maybe one day I will do it but for now I prefer doing different projects rather than repeating myself.
https://es.mathworks.com/matlabcentral/profile/authors/9968167-rubén-soto
Let me know if you want me to write another article about the actual solution. If you liked this article you may also like this one:
https://www.curiousruben.com/2019/10/how-to-write-safer-passwords-como.html
Bye!
My approach to code then was based on brute force. I thought that every time a computer solved a problem it was just a matter of trying all possible solutions and that was how I could write a program to solve any sudoku. But, how do you actually try all the solutions? Where do you start?
Let's consider the next sudoku:
We know that every row has to contain all the numbers from 1 to 9 so the first step could be to fill each row with the remaining numbers there:
All we have to do now is permute the added numbers in each row until we find the solution. For example, in the first row we've added: 1 - 3 - 5 - 6 - 7 - 9. One possible permutation is: 1 - 3 - 5 - 6 - 9 - 7. It doesn't seem so difficult, does it? But how long would it take to solve the sudoku with this approach? Let's see:
We know that all the possible permutations of n numbers is n!. n will be the number of empty spaces in each row. The total number of possibilities we would have to try would be the multiplication of all the permutations for each row:
In this case the result is:
If we consider that a modern computer can try 10^9 possibilities each second (this is a huge exaggeration by the way), it would take 30000 YEARS!!!! to solve the sudoku. This example is a very easy sudoku. If you try to solve it by hand, it shouldn't take longer than 5 minutes. I did this calculus with sudokus of different levels and it was interesting to find out that the level of a sudoku is not directly related to the amount of empty spaces it has. Although the results were different depending on each distribution, there was never a case that could be solved in reasonable time.
So that is the end of the story. After several days coding, I realized that my algorithm wasn't gonna solve anything and that coding, computers and problem solving weren't just about brute computational force. I had to come up with something different and maybe write a lot more code. If you want to see how I actually solved it, you can visit the link below. I uploaded it to my Mathworks Community Profile. I thought for a while to write an app (Android or iOS) for it but haven't found the time yet. Maybe one day I will do it but for now I prefer doing different projects rather than repeating myself.
https://es.mathworks.com/matlabcentral/profile/authors/9968167-rubén-soto
Let me know if you want me to write another article about the actual solution. If you liked this article you may also like this one:
https://www.curiousruben.com/2019/10/how-to-write-safer-passwords-como.html
Bye!
Español
¡¡Hola a todos!! Hace unos años, cuando empecé a aprender a programar en el primer curso de universidad recuerdo que pensé que resolver un sudoku podría ser muy fácil usando un ordenador. Entonces usábamos MatLab y yo no era particularmente bueno así que bastante tenía con aprobar la asignatura. Dejé mi pequeño proyecto de sudoku para el futuro. Durante mi tiempo en la universidad, seguimos usando MatLab bastante. Básicamente, cada año teníamos al menos una asignatura que requería ese programa. Cuando acabé mis estudios había mejorado considerablemente. No era que hubiera creado algo alucinante pero al menos me sentía cómodo usando para cálculos matemáticos, gráficos otros usos. Una tarde estaba haciendo un sudoku por mi cuenta cuando la idea de escribir un script para resolverlo con el ordenador se me ocurrió otra vez. Pensé que sería algo fácil que requeriría un día o dos de trabajo. Estaba tremendamente equivocado. (quizá alguien que haya estudiado informática o tenga un conocimiento más profundo de algoritmos, competiciones de programación, puzzles,... sí pueda hacerlo en un día pero ese no era mi caso ;) )
Mi enfoque acerca de la programación en esa época se basaba en la fuerza bruta. Pensaba que cada vez que un ordenador resolvía un problema era simplemente cuestión de probar todas las diferentes soluciones y así era como podría escribir el programa para resolver los sudokus. Pero, ¿cómo pruebas realmente todas las soluciones? ¿Dónde empiezas?
Consideremos el siguiente sudoku:
Sabemos que cada fila debe contener todos los números del 1 al 9 así que el primer paso será rellenarla con los números que faltan:
Todo lo que tenemos hacer ahora es permutar los números añadidos hasta encontremos la solución. Por ejemplo, en la primera fila hemos añadido: 1 - 3 - 5 - 6 - 7 - 9. Una posible permutación es: 1 - 3 - 5 - 6 - 9 - 7. No parece difícil, ¿verdad? Pero, ¿cuánto se tardaría en resolver el sudoku con esta idea? Veamos:
Sabemos que todas las posibles permutaciones de n números es n!. n será el número de huecos en cada fila. El número total de posibilidades que tendríamos que probar sería la multiplicación de todas las permutaciones de cada fila:
En este caso el resultado es:
Si consideramos que un ordenador moderno puede probar 10^9 posibilidades por segundo (esto es una exageración enorme por cierto), tardaría ¡¡¡¡30000 AÑOS!!!! en resolver el sudoku. Este ejemplo es un sudoku muy fácil. Si se intenta resolver a mano, no debería llevar más de 5 minutos. Hice este cálculo con sudokus de diferente nivel y fue interesante comprobar que la dificultad del sudoku no está directamente relacionada con el número de espacios vacíos que tiene. Aunque los resultados eran diferentes dependiendo de cada distribución, no hubo ningún caso que pudiera ser resuelto en un tiempo razonable.
Y este es el final de la historia. Después de varios días escribiendo código, me di cuenta de que mi algoritmo no iba a resolver nada y de que la programación, los ordenadores y resolver problemas no era solo cuestión de pura fuerza computacional bruta. Tenía que pensar algo diferente y quizá escribir mucho más código. Si queréis ver cómo lo resolví de verdad podéis visitar el enlace de abajo. Lo subí a mi perfil de la comunidad de Mathworks. Pensé por un tiempo escribir una app (Android or iOS) para ello pero todavía no he encontrado tiempo. Quizá algún día lo haga pero por ahora prefiero hacer diferentes proyectos en lugar de estar repitiéndome.
https://es.mathworks.com/matlabcentral/profile/authors/9968167-rubén-soto
Dejadme saber si queréis que escriba otro artículo sobre la auténtica solución. Si os gustó este, puede que también os guste:
https://www.curiousruben.com/2019/10/how-to-write-safer-passwords-como.html
¡Adiós!
Mi enfoque acerca de la programación en esa época se basaba en la fuerza bruta. Pensaba que cada vez que un ordenador resolvía un problema era simplemente cuestión de probar todas las diferentes soluciones y así era como podría escribir el programa para resolver los sudokus. Pero, ¿cómo pruebas realmente todas las soluciones? ¿Dónde empiezas?
Consideremos el siguiente sudoku:
Sabemos que cada fila debe contener todos los números del 1 al 9 así que el primer paso será rellenarla con los números que faltan:
Todo lo que tenemos hacer ahora es permutar los números añadidos hasta encontremos la solución. Por ejemplo, en la primera fila hemos añadido: 1 - 3 - 5 - 6 - 7 - 9. Una posible permutación es: 1 - 3 - 5 - 6 - 9 - 7. No parece difícil, ¿verdad? Pero, ¿cuánto se tardaría en resolver el sudoku con esta idea? Veamos:
Sabemos que todas las posibles permutaciones de n números es n!. n será el número de huecos en cada fila. El número total de posibilidades que tendríamos que probar sería la multiplicación de todas las permutaciones de cada fila:
En este caso el resultado es:
Si consideramos que un ordenador moderno puede probar 10^9 posibilidades por segundo (esto es una exageración enorme por cierto), tardaría ¡¡¡¡30000 AÑOS!!!! en resolver el sudoku. Este ejemplo es un sudoku muy fácil. Si se intenta resolver a mano, no debería llevar más de 5 minutos. Hice este cálculo con sudokus de diferente nivel y fue interesante comprobar que la dificultad del sudoku no está directamente relacionada con el número de espacios vacíos que tiene. Aunque los resultados eran diferentes dependiendo de cada distribución, no hubo ningún caso que pudiera ser resuelto en un tiempo razonable.
Y este es el final de la historia. Después de varios días escribiendo código, me di cuenta de que mi algoritmo no iba a resolver nada y de que la programación, los ordenadores y resolver problemas no era solo cuestión de pura fuerza computacional bruta. Tenía que pensar algo diferente y quizá escribir mucho más código. Si queréis ver cómo lo resolví de verdad podéis visitar el enlace de abajo. Lo subí a mi perfil de la comunidad de Mathworks. Pensé por un tiempo escribir una app (Android or iOS) para ello pero todavía no he encontrado tiempo. Quizá algún día lo haga pero por ahora prefiero hacer diferentes proyectos en lugar de estar repitiéndome.
https://es.mathworks.com/matlabcentral/profile/authors/9968167-rubén-soto
Dejadme saber si queréis que escriba otro artículo sobre la auténtica solución. Si os gustó este, puede que también os guste:
https://www.curiousruben.com/2019/10/how-to-write-safer-passwords-como.html
¡Adiós!
Comments
Post a Comment