Ganador encontrado
¡Parece que tenemos un ganador! A menos que alguien planee competir con el solucionador de Sudoku más rápido del mundo, el usuario 53x15 gana con el solucionador Tdoku asombrosamente rápido. Para cualquier persona que todavía trabaje en sus solucionadores, todavía haré pruebas comparativas de nuevos envíos cuando tenga tiempo.
El reto
El objetivo de un juego de Sudoku es llenar el tablero con los números 1-9, uno en cada celda, de tal manera que cada fila, columna y cuadro solo contenga cada número una vez. Un aspecto muy importante de un rompecabezas de Sudoku es que solo debe haber una solución válida.
El objetivo de este desafío es simple, debes resolver un conjunto de rompecabezas de Sudoku lo más rápido posible. Sin embargo, no solo resolverás cualquier Sudoku antiguo, sino que resolverás los rompecabezas de Sudoku más difíciles que existen, el Sudokus de 17 pistas. Aquí hay un ejemplo:
Reglas
Idioma
Eres libre de usar cualquier idioma. Si no tengo un compilador instalado para su idioma, debería poder proporcionar un conjunto de instrucciones de línea de comandos necesarias para instalar un entorno donde su script pueda ejecutarse en Linux .
Máquina de referencia
El punto de referencia se ejecutará en un Dell XPS 9560, Intel Core i7-7700HQ de 2,8 GHz (aumento de 3,8 GHz) 4 núcleos, 8 hilos, 16 GB de RAM. GTX 1050 4GB. La máquina ejecuta Ubuntu 19.04. Aquí está la uname
salida, para cualquier persona interesada.
Linux 5.0.0-25-generic #26-Ubuntu SMP Thu Aug 1 12:04:58 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
Entrada
La entrada se dará como un archivo. Se puede encontrar aquí . El archivo contiene 49151 rompecabezas de Sudoku. La primera línea del archivo es el número de rompecabezas, y cada línea posterior tiene 81 caracteres y representa un rompecabezas. Las células desconocidas son 0
, y las células conocidas son 1-9
.
Su programa debería poder tomar el nombre de archivo como argumento, o tener la entrada del archivo de STDIN , para facilitar la verificación manual de su solución. Incluya una instrucción sobre cómo su programa toma información.
Tiempo / puntuación
A partir de las discusiones en los comentarios y algunas reflexiones, los criterios de calificación se han cambiado para ser el momento de todo su programa. Su programa debe producir el archivo de salida con el hash correcto incluso durante la puntuación oficial. Esto no interfiere con ninguna solución existente, y no cambia la clasificación tal como está ahora. Cualquier idea sobre el sistema de puntuación es apreciada.
Si dos soluciones tienen puntajes similares para ejecuciones individuales, ejecutaré múltiples puntos de referencia y el tiempo promedio será el puntaje final. Si los puntajes promedio difieren en menos del 2%, lo consideraré un empate.
Si su solución tarda más de una hora en ejecutarse, no se puntuará oficialmente. En esos casos, usted es responsable de informar la máquina en la que se ejecutó y su puntaje. Para un solucionador optimizado, esto no debería ser un problema.
EDITAR : Me llamó la atención que si bien es difícil, el problema planteado no es el más difícil que existe. Si hay tiempo disponible, intentaré comparar las soluciones presentadas aquí con el conjunto de rompecabezas más difícil y agregar el puntaje a cada presentación. Sin embargo, esto no será un puntaje oficial, y es solo por diversión.
Verificación
Su solución será verificada por una suma de verificación MD5 / SHA256. Su script debería poder generar un archivo que contenga todos los rompecabezas y sus soluciones. Sin embargo, el archivo también se inspeccionará manualmente, así que no intente obtener una colisión hash. Su archivo de salida debe coincidir con:
MD5: 41704fd7d8fd0723a45ffbb2dbbfa488
SHA256:0bc8dda364db7b99f389b42383e37b411d9fa022204d124cb3c8959eba252f05
El archivo tendrá el formato:
<num_puzzles>
<unsolved_puzzle#1>,<solved_puzzle#1>
<unsolved_puzzle#2>,<solved_puzzle#2>
...
<unsolved_puzzle#n>,<solved_puzzle#n>
con una nueva línea final.
Lo que no está permitido
De ninguna manera está permitido codificar soluciones . Su algoritmo debe ser aplicable en cualquier conjunto de rompecabezas Sudoku, tanto Sudokus fácil como más difícil. Sin embargo, está completamente bien si su solución es lenta para acertijos más fáciles.
No se le permite tener un programa no determinista . Puede usar un generador de números aleatorios, pero la semilla del generador debe ser reparada. Esta regla es para garantizar que las mediciones sean más precisas y tengan menos varianza. (Gracias a Peter Taylor por el consejo)
No está autorizado a utilizar recursos externos o solicitudes web durante el tiempo de ejecución de su programa. Todo debe ser autónomo. Esto no se aplica a las bibliotecas y paquetes instalados, que están permitidos.
Otra información
Si desea otro conjunto de prueba para verificar su solución, aquí hay 10000 Sudokus más fáciles . Aquí están sus soluciones .
MD5: 3cb465ef6077c4fcab5bd6ae3bc50d62
SHA256:0bc8dda364db7b99f389b42383e37b411d9fa022204d124cb3c8959eba252f05
Si tiene alguna pregunta, no dude en preguntar, y trataré de aclarar cualquier malentendido.
Respuestas:
C ++ - puntaje oficial de 0.201s
El uso de Tdoku ( código ; diseño ; puntos de referencia ) da estos resultados:
Tdoku ha sido optimizado para instancias difíciles de Sudoku. Pero tenga en cuenta, contrariamente a la declaración del problema, que 17 acertijos clave están lejos de ser el Sudoku más difícil. En realidad, se encuentran entre los más fáciles, y la mayoría no requiere retroceder en absoluto. Vea algunos de los otros conjuntos de datos de referencia en el proyecto Tdoku para los rompecabezas que son realmente difíciles.
También tenga en cuenta que, si bien Tdoku es el solucionador más rápido que conozco para los rompecabezas difíciles, no es el más rápido para los rompecabezas de 17 pistas. Para estos, creo que el más rápido es este proyecto de óxido , un derivado de JCZSolve, que fue optimizado para 17 acertijos durante el desarrollo. Dependiendo de la plataforma, puede ser un 5-25% más rápido que Tdoku para estos acertijos.
fuente
Node.js ,
8.231s6.735s puntuación oficialToma el nombre del archivo como argumento. El archivo de entrada ya puede contener las soluciones en el formato descrito en el desafío, en cuyo caso el programa las comparará con sus propias soluciones.
Los resultados se guardan en 'sudoku.log' .
Código
Salida de ejemplo
Probado en un Intel Core i7 7500U @ 2.70 GHz.
fuente
Python 3 (con dlx ) 4min 46.870s puntaje oficial
(Single Core i7-3610QM aquí)
Obviamente superable con un lenguaje compilado como C, y haciendo uso de subprocesos, pero es un comienzo ...
sudoku
es un módulo que he colocado en github (copiado al pie de esta publicación) que se usadlx
debajo del capó.Uso
sudoku.py
algún lugar de su ruta (desde el enlace de git hub o cópielo desde abajo)testSolver.py
algún lugar de su rutaSalida de tubería como se requiere en la especificación de desafío a un archivo si es necesario:
sudoku.py (sí, hay características adicionales aquí además de resolver)
fuente
Python 3 + Z3 - 10min 45.657s puntuación oficial
alrededor de 1000 en mi computadora portátil.
Instalar dependencia
correr
No estoy seguro de cómo mejorar su rendimiento, ya que se resolvió mágicamente ...
fuente
C -
2.228s1.690s puntaje oficialbasado en @ Arnauld
compilar y ejecutar:
fuente
C - 12min 28.374s puntaje oficial
funciona durante unos
30m15m en mi i5-7200U y produce el hash md5 correctocompilar (preferiblemente con clang v6) y ejecutar:
fuente
memcpy
allí y algo de recursión. Intentaré verificarlo hoy.Java - puntuación oficial de 4.056s
La idea principal de esto es nunca asignar memoria cuando no es necesaria. La única excepción son las primitivas, que el compilador debe optimizar de todos modos. Todo lo demás se almacena como máscaras y conjuntos de operaciones realizadas en cada paso, que se pueden deshacer cuando se completa el paso de recursión.
Aproximadamente la mitad de todos los sudokus se resuelven por completo sin retroceder, pero si presiono ese número más alto, el tiempo general parece ser más lento. Estoy planeando reescribir esto en C ++ y optimizar aún más, pero este solucionador se está convirtiendo en un gigante.
Quería implementar el mayor almacenamiento en caché posible, lo que condujo a algunos problemas. Por ejemplo, si hay dos celdas en la misma fila que solo pueden tener el número 6, entonces hemos llegado a un caso imposible, y deberíamos volver al rastreo. Pero como calculé todas las opciones en un barrido y luego coloqué los números en las celdas con una sola posibilidad, no verifiqué que había colocado un número en la misma fila justo antes. Esto lleva a soluciones imposibles.
Con todo contenido en los arreglos definidos en la parte superior, el uso de memoria del solucionador real es de aproximadamente 216kB. La parte principal del uso de la memoria proviene de la matriz que contiene todos los rompecabezas y los controladores de E / S en Java.
EDITAR : Tengo una versión que está traducida a C ++ ahora, pero no es mucho más rápida. El tiempo oficial es de alrededor de 3,5 segundos, lo que no es una gran mejora. Creo que el problema principal con mi implementación es que mantengo mis máscaras como matrices en lugar de máscaras de bits. Intentaré analizar la solución de Arnauld para ver qué se puede hacer para mejorarla.
fuente
C ++ con Minisat (2.2.1-5) - puntaje oficial de 11.735
Esto no es tan rápido como un algoritmo especializado, pero es un enfoque diferente, un punto de referencia interesante y fácil de entender.
$ clang ++ -o resolver -lminisat solver_minisat.cc
fuente