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

 (dfns.dyalog.com)
1 puntos por GN⁺ 2024-10-07 | 1 comentarios | Compartir por WhatsApp
  • En Dyalog APL, sudoku devuelve todas las matrices solución posibles a partir de una matriz de rompecabezas donde los espacios vacíos se representan con 0, e implementa el mismo problema de varias maneras en estilo APL/K
  • El objetivo básico es un Sudoku de 9×9, donde cada bloque de 3×3, fila y columna debe contener los números del 1 al 9 sin repetición
  • La entrada prob contiene 1-9 en las celdas llenas y 0 en las vacías, y con el argumento izquierdo opcional shape también se pueden especificar bloques no cuadrados como 2×3 o 3×4
  • El algoritmo de solución de Veli-Matti Jantunen vectoriza la matriz, crea índices de fila, columna y bloque, reduce candidatos y expande primero desde el grupo más restringido
  • Los ejemplos s33 y s22 tienen 3 soluciones cada uno, y 3 4 sudoku s34 tiene 2 soluciones; también se presentan el one-liner de Arthur Whitney en K 5 y varias reimplementaciones en APL

Entrada de Sudoku y resultado de la función sudoku

  • Un rompecabezas de Sudoku es una cuadrícula con bloques de 3×3 dispuestos en una matriz de 3×3, y cada celda está vacía o contiene un número del 1 al 9
  • La solución debe satisfacer las tres condiciones de no repetición
    • Cada bloque de 3×3 contiene los números del 1 al 9 sin repetirse
    • Cada fila de 9 celdas contiene los números del 1 al 9 sin repetirse
    • Cada columna de 9 celdas contiene los números del 1 al 9 sin repetirse
  • La matriz prob usa los números 1-9 para las celdas llenas y 0 para las vacías
  • El argumento izquierdo opcional shape especifica la forma de los bloques para rompecabezas que no usan la forma cuadrada predeterminada
    • En una matriz de 6×6 con subregiones de 2×3, se llama con la forma 2 3 sudoku mat
  • El resultado es un vector que contiene todas las matrices solución
    • Si no hay solución, devuelve ⍬
    • Las situaciones de error pueden marcarse con '', y la documentación dice que es “algo que no debería ocurrir, pero podría pasar cuando el número de resultados es enorme”

Flujo de la solución de Veli-Matti Jantunen

  • El algoritmo trata la matriz de Sudoku como un vector y representa filas, columnas y regiones de Sudoku como vectores de índices
  • Tras pasar las comprobaciones básicas, examina una por una las alternativas de la lista de candidatos
  • En cada paso filtra los elementos posibles de todas las celdas
    • Si existe хотя бы una celda sin valores posibles, se descarta ese candidato de solución
    • Si una celda tiene dos o más números candidatos, se elige una celda del grupo más restringido y se agregan a la lista las combinaciones candidatas de esa celda
    • Si en todas las celdas queda un solo número, se considera una solución y se pasa al siguiente candidato
  • En la misma sección también se incluye la función Shuffle, que mezcla una cuadrícula de Sudoku existente para producir otra distinta

One-liner de Arthur Whitney e implementaciones alternativas

  • La implementación alternativa de sudoku de David Crossley acepta una configuración N×N como entrada y está pensada para casos donde el tamaño del bloque N*÷2 es entero
    • La entrada debe ser una disposición válida con números del 1 a N en algunas celdas y 0 en las demás
    • Cada fila, columna y bloque debe contener en el resultado todos los números del 1 a N
    • Dentro de la implementación hay funciones auxiliares como valid, search, rules, sole, singles, uniques, matches, NinN y setup
  • La solución de Arthur Whitney en K 5 se presenta como código de una sola línea
x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~* x
  • Phil Last ofrece una implementación de sudoku que traslada el código de Whitney a una D-function
  • La reescritura de Morten Kromberg define explícitamente algunos componentes de K para acercarse más al original
    • Como en la versión de K, recibe y devuelve un vector de 81 elementos en lugar de una matriz
  • La implementación Sudoku de Roger Hui es una forma más generalizada que también maneja rompecabezas no cuadrados
    • svec construye el vector de solución, y pvex y pvec despliegan las disposiciones posibles
    • avl crea la lista de números posibles, y emt encuentra los índices de fila y columna de las celdas vacías
    • rcb, box, cmap y CMAP construyen las relaciones de conflicto entre filas, columnas y bloques

Rompecabezas de ejemplo y número de soluciones

  • s33 es un problema de ejemplo de 9×9, y el resultado de sudoku s33 tiene 3 soluciones
  • La función sbox divide los bloques internos para mostrar la cuadrícula de Sudoku de forma más legible
    • Los 0 se muestran como puntos (·)
    • La salida tiene forma de matriz de caracteres con los bordes de los bloques dibujados
  • s22 es un problema de ejemplo de 4×4, y el resultado de sbox¨ sudoku s22 tiene 3 soluciones
  • s34 es un problema de ejemplo que usa bloques de 3×4
    • 3 4 sbox s34 muestra el problema con separación visual por bloques
    • El resultado de 3 4 sudoku s34 tiene 2 soluciones

Enlaces de referencia y elementos relacionados

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-10-07
Opiniones de Hacker News

  • Esa línea está escrita en K. K es un lenguaje creado por Arthur Whitney a partir de APL y Scheme.
    x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~*x

  • A veces estimo la complejidad del código comparando la cantidad de líneas de código con el resultado de abajo:
    tar -cf - . | gzip | base64 | wc -l
    Es decir, miro “¿qué tan bien se comprime?”. Cuando veo APL, me recuerda a cuando por accidente mandas la salida de gzip a la terminal.
    p←{(↑⍵)∘{(⍺∨.=⍵)/⍳n×n∘}¨,⍵},(n*÷2){⍵,⍺⊥⌊⍵÷⍺}'⍳n n←⍴⍵
    Me impresiona que haya gente que siga código así y hasta se pregunte “¿puedes encontrar el bug?”. Se siente como datos binarios comprimidos donde todos ya tienen el mismo diccionario.

    • Sinceramente me da curiosidad cómo piensan los programadores de APL sobre la mantenibilidad y la legibilidad. Me pregunto si comentan el código con muchísimo detalle o si hacen documentación aparte.
    • Si la pregunta es “¿puedes encontrar el bug?”, de inmediato se ven varias cosas. Hay errores de sintaxis, como una comilla simple sin cerrar y un ∘ sin operando derecho, y n n←⍴⍵ parece indicar que espera que ⍵ sea bidimensional al asignar n dos veces, aunque según la intención sería más natural _ n←⍴⍵ o n←⊃⌽⍴⍵.
      Además, ⊥ da error si ⍴⍵ no es un entero único o un vector vacío, así que al final no es distinto de n←⍴⍵ y solo confunde más. También se pueden eliminar varios , redundantes y ↑⍵, y toda la expresión en la práctica queda casi igual a p←(n+1)⍴⊂⍳n×n←⍴⍵, una estructura que devuelve n+1 vectores 1..n².
      Aunque a primera vista parezca raro, una vez que aprendes los símbolos y las operaciones básicas, APL es sorprendentemente directo. Eso sí, dominarlo toma tiempo, y cuando llegas a ese punto se siente como un superpoder.
    • Si pensamos que miles de millones de personas leen y escriben caracteres que no son ingleses, no sé si que haya gente que lea APL sea algo más especial o sorprendente.

  • Es cierto que quienes defienden el lenguaje destacan la velocidad, la facilidad para procesar arreglos y una sintaxis expresiva.
    https://en.m.wikipedia.org/wiki/K_(programming_language)

    • Pero no sé si la mantenibilidad también sea una ventaja.

  • La cantidad de líneas de código no es una buena métrica, porque cada lenguaje usa las líneas de manera distinta.
    Una mejor medida podría ser contar los nodos del árbol sintáctico según símbolos no terminales significativos, como “constantes” o “llamadas a funciones”. Mejor aún si además se considera la profundidad de ese árbol y su factor de ramificación.

    • Me cuesta estar de acuerdo con la idea de que solo importa la semántica. También importan la experiencia de uso del lenguaje, la claridad, la forma de pensar y la expresividad, y el tamaño visual del código influye en todo eso.
      Una solución de una sola línea casi no ocupa espacio en pantalla, lo cual es una gran ventaja al abordar problemas complejos. Mover los ojos dentro de la pantalla cuesta mucho menos que ir entre archivos y hacer scroll, y la carga cognitiva importa.
      Aunque no sepas K, si ves constantes alineadas una junto a otra, parece que se estuviera usando una representación directa de los datos del problema. Si la cultura de K fomenta este tipo de código y orienta el pensamiento hacia la inmediatez y la simplicidad, me gustaría llevar esa salsa especial a mi equipo.
    • Las funciones integradas y las API de bibliotecas del sistema arruinan este tipo de métrica. Por ejemplo, HQ9+ es bastante bueno, al menos para imprimir “Hello, world!”.
      https://cliffle.com/esoterica/hq9plus/
    • La métrica preferida para medir la cantidad de información es simplemente el número de bits, como en la teoría algorítmica de la información.
      https://en.wikipedia.org/wiki/Algorithmic_information_theory
    • Este código de una sola línea claramente fue hecho como broma, y nadie sostendría razonablemente que sea código fácil de leer. Discutir definiciones aquí es perder el punto. La idea es que “con K se puede escribir código extremadamente denso”.

  • A menudo me he preguntado si al usar lenguajes como APL/K los programadores realmente pueden pensar los problemas de forma más eficiente.

    • Como programador de kdb+/Q, creo que depende del tipo de problema. Cuando trabajas con arreglos de datos, definitivamente es más fácil pensar y escribir algo como avg a+b para sumar dos arreglos y luego sacar el promedio.
      En un lenguaje que no esté centrado en arreglos, probablemente necesitarías verificaciones de límites, un gran bucle for y variables temporales para guardar la suma y el conteo. Es la diferencia entre algo que en C tomaría unas 6 líneas y en Q se resuelve con 6 caracteres.
      Aun así, todos los lenguajes tienen características que ayudan a razonar mejor sobre ciertos problemas. Los lenguajes funcionales con tipos de datos algebraicos y pattern matching, como OCaml o F#, son mejores que un gran switch o una cadena de if-else-if, y los lenguajes con azúcar sintáctico como async/await tienen ventaja para manejar concurrencia.
    • En familias de problemas que se vectorizan fácilmente, los lenguajes centrados en arreglos hacen que el pensamiento y las soluciones sean más eficientes, porque permiten abstraer los detalles de las estructuras de datos y la iteración.
      Cuando trabajaba como quant, usé mucho kdb+/q durante más de 5 años para estrategias de frecuencia media, pero cuando me pasé a trading de alta frecuencia, con cálculos como el libro de órdenes que no se vectorizan fácil o eficientemente, seguir usando un lenguaje centrado en arreglos terminó haciendo más complejo razonar sobre el problema.
    • En una charla sobre Dyalog, un lenguaje moderno de la familia de APL, escuché el argumento de que esta notación permite reconocer con más facilidad ciertos modismos.
      https://youtu.be/PlM9BXfu7UY?si=ORtwI1qmfmzhJGZX&t=3598
      Esa parte era en el contexto de compiladores, pero la charla en general trata a Dyalog y APL como sistemas de notación matemática. El hilo central es que optimizar expresiones matemáticas puede ser más fácil que optimizar código convencional.
    • Hillel Wayne toca este tema de vez en cuando en su newsletter. Me convenció de que en verdad piensa mejor algunos problemas en lenguajes de arreglos, pero todavía no logro imaginar bien cómo se siente esa experiencia.
    • Lo bueno del estilo de los lenguajes de arreglos es que, al discutir variantes de un algoritmo, los fragmentos de código relevantes son de apenas unos caracteres y pueden ir directamente dentro del texto. En lenguajes tradicionales de orientación vertical, donde decir lo mismo requiere varias líneas o decenas de líneas, hay que estar mezclando constantemente bloques de código con explicaciones.

  • Una de las cosas más importantes aquí es que el generador de problemas de la parte superior es muy claro. Esa es la diferencia entre los lenguajes de notación al estilo Iverson, incluidos J y K, y otros lenguajes.
    No tiene la elegancia ni la potencia de la solución de una sola línea, pero es muy limpio y comprensible incluso sin comentarios estrictos. Aunque creo que lamp no es un buen símbolo de comentario.
    La solución de una sola línea es asombrosa, y la programación tácita es tan genial que te dobla la mente. La idea de usar la compresión única de los lenguajes basados en glifos para explicar y ejecutar programación funcional, y luego aplicarla a arreglos completos, es de genio.
    https://www.jsoftware.com/papers/fork.htm

    • Que puedas escribir todo en una sola línea sin espacios no significa que necesariamente debas hacerlo.
      Claro, si quitas esa capacidad puedes obligar a escribir código más verboso, pero entonces se reduce mucho su fortaleza como herramienta interactiva. Los lenguajes al estilo Iverson son útiles para el trabajo interactivo porque permiten escribir código muy corto. Ese código ni siquiera se guarda, así que de verdad es código write-only.
      Cuando escribes código que va a ir en un archivo, puedes elegir el estilo que quieras, y en ese caso recomendaría escribirlo de forma menos comprimida. Aun así, incluso escritos en un estilo verboso, los lenguajes al estilo Iverson ofrecen código mucho más corto que la mayoría de los lenguajes.

  • A la mayoría le echan para atrás los símbolos, pero mi problema no era ese.
    Me gustan APL y los lenguajes de arreglos, y lo que aprendí me ayudó mucho incluso al usar otros lenguajes. Pero no se convirtieron en herramientas de uso diario; no por los símbolos, sino porque, tras usarlos de forma intermitente durante unos 3 o 4 años, me topé con una pared que no pude superar.
    En otros lenguajes suele haber un enfoque general para ir resolviendo un problema, aunque sea de forma aproximada, y luego, si encuentras el “truco” del problema, puedes corregirlo para que sea más elegante y eficiente. En APL sentí que no existe ese rodeo provisional: o sabes el truco, o no lo sabes.
    No sé bien si realmente es así, si al aprender suficientes trucos se desarrolla una intuición para resolver problemas, si al final todo sigue siendo solo trucos, o si simplemente no leí algún documento clave de estrategia.

    • Esa sensación no está equivocada. Es muy fácil llevarse esa impresión al aprender lenguajes de arreglos. Alguien con mucha experiencia puede ver un problema y decir: “¿por qué lo resolviste de forma tan complicada, si basta con usar ⍸⍣¯1?”, pero es muy posible que nadie te haya contado que ⍸ tiene una operación inversa ni cómo se usa.
      Incluso ahora, después de años usando estos lenguajes, algunas paredes de código que producen ciertos programadores de arreglos me resultan un poco intimidantes. Entiendo por qué escriben así, pero personalmente prefiero que el código tenga algo de espacio en blanco.
      Estoy creando un lenguaje de arreglos basado en APL, y uno de los objetivos iniciales era no castigar a los principiantes por usar cosas como sentencias if, sino hacer que el estilo imperativo fuera ciudadano de primera clase. Veo este estilo como algo a medio camino entre el APL puro y los lenguajes imperativos comunes.
      https://codeberg.org/loke/array/src/branch/master/array/standard-lib/output3.kap
    • La pared que mencionas es un problema real en las rutas actuales de introducción a APL. El año pasado di una charla precisamente sobre este tema, y definitivamente no es culpa individual.
      Pero tampoco es una limitación del lenguaje en sí. En mi experiencia, el proceso de atravesar esa pared fue justamente el proceso de que el paradigma empezara a encajar. Solo después de pasar unas 500 horas hackeando durante un año un prototipo de parser de YAML, las piezas empezaron a encajar.
      La clave parece ser una combinación de principios de diseño guiado por datos, formas concretas de aprovechar en la arquitectura de software las características iversonianas de una buena notación, y familiarizarse con los modismos y con cómo expresan conceptos del dominio.
      https://dyalog.tv/Dyalog23/?v=J4cg6SV92C4
      https://www.jsoftware.com/papers/tot.htm

  • Hay un video sobre este tema.
    https://www.youtube.com/watch?v=DmT80OseAGs
    La solución se puede probar directamente en https://tryapl.org/.

  • Puede ser interesante comparar esta línea con soluciones de code golf en varios lenguajes de programación.
    https://codegolf.stackexchange.com/questions/tagged/sudoku?tab=Votes

    • Curiosamente, para un problema específico —resolver sudokus por fuerza bruta—, la solución en primer lugar es precisamente un fragmento de K. El segundo lugar es una solución en J hecha siguiendo la de K.
      https://codegolf.stackexchange.com/a/5030