El solucionador de Sudoku en una sola línea de Arthur Whitney (2011)

Algoritmo de resolución de Sudoku

• Descripción del problema de Sudoku

  • El rompecabezas de Sudoku está compuesto por cajas de 3×3 dentro de una cuadrícula de 3×3, y cada celda está vacía o contiene un número del 1 al 9.
  • Cada caja de 3×3, las 9 filas y las 9 columnas deben contener los 9 números sin duplicados.
  • Se proporcionan un problema de ejemplo y un método de resolución.

• Resumen del algoritmo

  • La matriz se procesa como un vector y las filas, columnas y regiones del Sudoku se representan con vectores de índices.
  • Se realiza una verificación básica del rompecabezas y se encuentra la solución filtrando los elementos posibles.
  • Si una celda está vacía, se pasa a la siguiente lista, y si una celda contiene varios números, se elige desde el grupo más restringido y se agrega a la lista.
  • Cuando todas las celdas contienen un solo número, se ha encontrado la solución.

• Notas técnicas

  • Es una solución proporcionada por Veli-Matti Jantunen, y se puede usar ⍺ para representar rectángulos de Sudoku.
  • El resultado devuelve un vector de todas las soluciones, ⍬ si no hay ninguna, y '' si hay un error.
  • El algoritmo es simple: procesa la matriz como un vector y encuentra la solución filtrando los elementos posibles.

• Otros enfoques

  • Se presentan codificaciones alternativas de David Crossley y Arthur Whitney.
  • Se describen distintos estilos de programación y enfoques.

• Ejemplos y usos

  • Se ofrecen varios ejemplos para resolver problemas de Sudoku.
  • También se incluye una función para separar las cajas internas y facilitar la lectura del Sudoku.

Resumen de GN⁺

• Se presentan varios algoritmos y estilos de programación para resolver Sudoku.
• Los rompecabezas de Sudoku son útiles para mejorar el pensamiento lógico y la capacidad de resolver problemas.
• Distintos enfoques pueden aumentar la flexibilidad al resolver problemas.
• Como rompecabezas con funciones similares al Sudoku, se recomiendan Kakuro y KenKen.

[GN⁺]

Comentarios en Hacker News

• K es un lenguaje creado por Arthur Whitney a partir de APL y Scheme, con énfasis en la velocidad, el manejo de arreglos y una sintaxis expresiva
• Al medir la complejidad del código, se comparan la cantidad de líneas y el grado de compresión
  • El código APL se siente como datos binarios comprimidos, y causa admiración la gente que puede entenderlo
• La cantidad de líneas de código no es una buena métrica, ya que se usa de forma distinta según el lenguaje
  • Una mejor forma de medir sería considerar la cantidad de nodos del árbol sintáctico, su profundidad y los factores de ramificación
• La claridad del problema es importante, e idiomas iversonianos (incluyendo J y K) se diferencian de otros lenguajes
  • Una solución de una sola línea es sorprendente y útil para describir y ejecutar arreglos de manera eficiente
• Hay quien opina que los programas en K deberían terminar con QED, y se pregunta por su relación con KQED
  • KQED es una afiliada de PBS en el Área de la Bahía
• Se preguntan si lenguajes como APL/k ayudan a pensar los problemas de forma más eficiente
• Aprender APL y lenguajes de arreglos ayudó con otros lenguajes, pero dejaron de usarse en el día a día
  • En APL, si no conoces una forma específica de resolver cierto tipo de problema, resulta difícil resolverlo
• Hay soluciones mejores que algunas soluciones ineficientes vistas en ciertos manuales de diseño de algoritmos
  • En 2015 se escribió una entrada de blog sobre esto
• La solución de Sudoku usando Scryer Prolog es fácil de leer y potente, con excelentes capacidades de resolución por restricciones
  • Scryer Prolog es un Prolog moderno, de alto rendimiento y compatible con ISO