Robot resuelve sudoku en papel

El sudoku es una excelente manera de pasar el tiempo, especialmente en un vuelo largo. Sin embargo, no creemos que las aerolíneas se vayan [Sanahm] a bordo con su robot de solución sudok. La máquina base parece un plotter 2D hecho con una protuberancia de aluminio, con la adición de una Raspberry Pi y una cámara. La máquina puede leer un sudoku, resolverlo y luego completarlo con un bolígrafo. A diferencia de las personas, nunca debería acabar con su trabajo.

El software utiliza OpenCV para procesar los datos de la cámara, encontrar la cuadrícula y las celdas proporcionadas por el rompecabezas. TensorFlow reconoce los números. A partir de ahí, todo es matemático para resolver el rompecabezas. Después de una solución, la parte de trazado del robot se hace cargo y llena los huecos. Después de todo, esta parece la parte fácil.

No hay video, pero la publicación original tiene una imagen de la máquina haciendo lo suyo. El repositorio tiene toda la información sobre electrónica, construcción mecánica y firmware.

Recordamos un proyecto similar realizado con Lego Mindstorms. Si necesita ayuda para obtener OpenCV en la Raspberry Pi, también hemos hablado de eso antes.

  • Raza dice:

    ¡Oh, no! ¡El robot está haciendo sudoku!

  • Justin Nesselrotte dice:

    Sería genial mirarlo en el orden en que descubre las cosas, en lugar de resolver todo el rompecabezas y luego completarlos todos.

    • Darrell R Harriman dice:

      Ese fue exactamente mi primer pensamiento. Sería mucho más interesante.

  • TheRegnirps. dice:

    Esto está muy bien. Tengo un Hi-Plot original de Houston Instruments (pasos X e Y y un solenoide de bolígrafo en un recipiente agradable, literalmente) sentado aquí y esta es una aplicación perfecta.

    Además, en mi campaña insuficiente para volver a poner a la gente en METS, debo señalar que “los sudoku son acertijos digitales que las computadoras pueden resolver automáticamente porque obedecen algunas reglas matemáticas simples”. Quiero decir, dice que las computadoras obedecen a reglas simples, mientras que en mi contexto te refieres a que el Sudoku obedece a reglas simples. Alguien desarrolló el algoritmo y escribió el programa. Creo que para los piratas informáticos este proceso de creación del motor de búsqueda de soluciones es más interesante que la mecanización.

    En esa línea, ¿no es justo decir que la persona que escribió el programa resolvió todos los posibles acertijos de sudoku? ¿Siempre que exista prueba de que el programa es correcto?

    • ESTOLA dice:

      lol ¡Solo hazlo!

      El programa de solución de Sudoku es uno de los códigos más divertidos porque tiene un momento DUH real.

      Mi primer código imitaba más o menos cómo yo personalmente hago el rompecabezas, y fue muy prolijo y tedioso.

      Para mí, el momento DUH fue cuando me di cuenta de que las 3 reglas de posición se pueden convertir en reglas de simetría y transferencia como el cubo de Rubik. Una vez que se dé cuenta de que puede comenzar con un simple rompecabezas resuelto y mapear la mesa con los elementos conocidos del rompecabezas real usando las reglas anteriores y al hacerlo, terminará mapeando los elementos desconocidos también.

      Para obtener puntos extra, puede transformar todo el código en una única función recursiva.

      • FredTheRanger dice:

        O simplemente podría escribir un algoritmo de fuerza bruta que simplemente pruebe ciegamente todas las combinaciones, aplique las reglas y explote cuando se aprueben.

      • seanrhinehart dice:

        El plan que describió es elegante, pero solo funciona en bases de datos de entrada de alta calidad (como rompecabezas publicados) que tienen exactamente una solución.

        Si la entrada es incompleta (sub-limitada, con muchas soluciones), este enfoque parecería encontrar solo una de ellas.
        Considere el fragmento del rompecabezas a continuación, donde solo la fila superior y la cuadrícula superior izquierda se llenan como se muestra:

        123456789
        456
        789

        Esta tabla parcial (sublimitada) tiene miles de soluciones.

        Escribí una función de solución recursiva de Sudoka que funciona en dos fases.

        La primera fase aplica una deducción simple para determinar qué celdas vacías tienen solo un valor posible, después de eliminar los otros valores que ya aparecen en las regiones (fila, columna, cuadrícula 3 × 3) que incluyen la celda.
        Esta primera fase es suficiente para resolver acertijos más simples.

        La segunda fase utiliza un enfoque de fuerza bruta. Cuando todas las celdas vacías restantes tengan muchos valores candidatos posibles, guarde la tabla actual como un punto de “bifurcación”, seleccione una celda con el número mínimo de opciones candidatas y asigne temporalmente el siguiente valor candidato a la celda. Luego (recursivamente) llame a Solve nuevamente, en profundidad primero el recorrido del árbol de opciones. La rama de un árbol termina cuando se alcanza una solución o no es posible seleccionar un dígito sin duplicarlo en una fila, columna o cuadrícula. Si la duplicación digital es inevitable, significa que una selección de bifurcación anterior (o la configuración inicial del rompecabezas en sí) fue incorrecta.

        • ESTOLA dice:

          Considera esto –
          456123789
          123
          789

          Si traduzco 123 por 456, entonces es lo mismo que en su ejemplo.

          De hecho, puede transponer y traducir para crear cada permutación a partir de una solución. es decir, como el cubo de Rubik es sólo una solución de la que proceden todos los demás estados. Sin embargo, con este rompecabezas también hay una transposición, que es como quitar todas las pegatinas de un cubo de Rubik y luego volver a ensamblarlas con un solo color por lado. Técnicamente, el cubo difiere, pero de acuerdo con la simetría de su lógica, sigue siendo el mismo.

          Cuando codifiqué el caso anterior, el código se ejecutó en paralelo, aunque se realizó de forma secuencial en función del procesador (VHDL sería completamente paralelo). Debido a su naturaleza paralela, no existe una “primera” solución, por lo que en el caso de una matriz sub delimitada, simplemente devolverá algunos elementos como “indefinidos”.

          Considera esto –
          123456789
          456789123
          789123456
          234567891
          567891234
          891234567
          345678912
          678912345
          912345678

          Simplemente intercambiando filas y columnas puede crear cualquier otra permutación posible. En la memoria, lo he reducido a menos funciones de intercambio y el resultado es que los números conocidos forman un mapa de Karnaugh de los intercambios necesarios para completar el rompecabezas.

          • seanrhinehart dice:

            Entiendo cómo se puede crear cualquier posible permutación de un solo rompecabezas resuelto. Mi problema era que no veía cómo este enfoque le permitiría calcular todas las soluciones posibles, para el caso (ciertamente degenerado) de acertijos que tienen múltiples soluciones.

          • ESTOLA dice:

            Mi código también era hacer rompecabezas.

            Aunque es posible devolver una fórmula booleana para muchas soluciones, no me molesté, porque cualquier rompecabezas con más de una solución se considera un rompecabezas inválido.

  • pete dice:

    Estoy pensando en reconocer el marco de una vieja impresora 3D ABC, porque lo inútil que encontré la máquina en la impresión 3D parece ser la primera adaptación útil del dispositivo que he visto. Buena suerte.

  • Yarr dice:

    “El sudoku es una excelente manera de pasar el tiempo, especialmente en un vuelo largo”.

    Eres un hombre según mi propio corazón, A. Cada vuelo que he tomado en los últimos 10 años, mi primera parada después de experimentar la seguridad, es la tienda de revistas de libros estereotipada que existe en cada aeropuerto, para obtener la última revista de Sudoku y su variante de Sudoku y un paquete de lápices.

  • Betty-Swollox dice:

    muy imponente para ser justos. Para algo más difícil, ¿qué tal si conseguimos una computadora para resolver el crucigrama del Times (el apropiado y críptico)?

Ricardo Prieto
Ricardo Prieto

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *