Buscador de sudoku único

19

Desafío:

Dado un tablero de Sudoku en la entrada estándar, encuentre el número mínimo de números agregados para que el tablero sea único.

Detalles / Reglas:

  • La entrada tiene el siguiente formato (todo el espacio en blanco es significativo)

    516|827|943
    278|394|615
    349|615|872
    ---+---+---
    98 |4 2|156
    465|189|237
    12 |5 6|489
    ---+---+---
    892|743|561
    634|951|728
    751|268|394
    
  • La salida está formateada con un número por línea, formateada como (x,y):z: x e y comienzan desde uno en la parte superior izquierda y aumentan hacia abajo y hacia la derecha; z es el número que se agregará.

    • En este caso, éstos serían todas las salidas válidas: (3,4):3, (3,4):7, (5,4):3, (5,4):7, (3,6):3, (3,6):7, (5,6):3, y (5,6):7, como cualquiera de éstas permitiría a la junta que hay que resolver.
  • Si se ingresa un tablero de Sudoku único / resuelto, el programa no debe imprimir nada, ni siquiera una nueva línea.
  • El programa debería ejecutarse en menos de una hora para cualquier tablero (sugiero probar usando un tablero completamente en blanco, o un tablero con un número aleatorio en él ...).

Puntuación:

  • Tome el tamaño total del código (en golf) en caracteres, incluidos todos los espacios en blanco ...

Bonificaciones:

Tamaño de código 1/2 : si el programa imprime un solo signo de exclamación y se detiene al tener un tablero sin soluciones ingresadas.

Tamaño de código 1/2 : si el programa imprime dos signos de exclamación y se detiene al ingresar un tablero con una contradicción interna (dos números iguales en la misma fila / columna / cuadrado).

Root Infinity
fuente
3
Aburrido y probablemente difícil :(
Oleh Prypin
66
Abucheo. 'No imprimir nada, ni siquiera una nueva línea' descarta GolfScript.
Peter Taylor
1
un solucionador de sudokus que nunca se tiene que dar marcha atrás / suposición de que se necesita una solución completa para esto, (y cada vez que se necesita una "conjetura" salida de ella)
monstruo de trinquete
3
No veo la razón para rechazar esto. Se hizo un gran esfuerzo para mostrar un bonito rompecabezas; Es muy claro y está bien establecido. Es demasiado grande para mi gusto, pero eso es demasiado subjetivo como para rechazarlo, ¿no?
usuario desconocido

Respuestas:

10

Brachylog , 245 bytes / 2 = 122.5

@n:1a:"-"x:7fF:3a$\:3a@3:4a,Fc~bCh[0:0:0]gO,Co~c[V:O:T]h:F:6f:10ao:ba(h:11a;!);"!!"w!
h"-".|:"|"x:2f.
e(~m["0123456789":.]`;0<.<=9)
:ha#d.
:@3az:ca:5a.
:3a.
hs.:=a,?t:9ac:=fl1
:Im:8f:[[I]]z:ca.
:Jm:J.
:ha.
lg:?c.
b:+a[X:Y],?h:Y:Xr:"(~d,~d):~d
"w

(Tenga en cuenta que debe usar la versión del idioma a partir de esta confirmación . Este código necesitaría algunos pequeños cambios para que funcione correctamente en las siguientes versiones de Brachylog)

Esto se imprime "!!"si la placa dada tiene contradicciones internas (esto lleva unos segundos en ese caso, sin embargo, en TIO, así que sea paciente).

No estoy seguro de entender el primer bono correctamente, así que no lo estoy abordando.

Obviamente, esto no es competitivo ya que el lenguaje es mucho más reciente que el desafío, sin embargo, dado que no hay otras respuestas, no estoy seguro de que esto importe mucho ...

Explicación

  • Predicado principal:

    @n                Split the input on line breaks
    :1a:"-"x          Transform into a list of lists, each sublist contains a line's values
    :7fF              Transform so that cells are [Value:X:Y]
    :3a               All values on lines must be different
    $\:3a             All values on columns must be different (by transposition)
    @3:4a,            All 3*3 block values must be different
    Fc~bCh[0:0:0]gO,  Append a fake cell [0:0:0]
    Co~c[V:O:T]       Sort the board, the blank cells V will be those before O ([0:0:0])
    h:F:6f            Find all subsets of blank cells with specific values for which 
                          the board has only one solution
    :10ao             Sort the subsets by lengths
    :ba               Discard the lengths
    (                 
      h:11a             Print the first subset = an answer
    ;                 Or (board is already fully determined)
      !                 Terminate
    )          
    ;                 Or (Some values don't respect the constraints)
    "!!"w!            Print "!!" and terminate
    
  • Predicado 1: elimine todos los " |" en líneas, transforme el ---+---+---en -para eliminarlos después

    h"-".    If the first char is "-", then Output is "-"
    |        Or
    :"|"x    Remove all occurences of "|" from the input
    :2f.     Output is the result of all outputs of predicate 2 on the filtered string
    
  • Predicado 2: Convierta un carácter en un entero o, si está en blanco, en una variable entre 1 y 9.

    e                      Take a char of the input string
    (
      ~m["0123456789":.]     Output is the index of the char in "0123456789"
      `                      Discard the choice point caused by the ;
    ;                      Or
      0<.<=9                 Output is an integer between 1 and 9
    )
    
  • Predicado 3: Imponga que todos los valores de la lista de celdas de entrada deben ser distintos

    :ha    Retrieve the head of each cell (i.e. the value) in the input 
    #d.    Apply a constraint of distinctness to those values
    
  • Predicado 4: aplique la restricción de distinción a los valores en bloques de 3 * 3

    :@3a            Split 3 lines of the board in 3 parts
        z           Zip them together
         :ca:5a.    Concatenate each element of the zip, apply predicate 5 to that
    
  • Predicado 5:

    :3a.    Apply predicate 3 to each element of the input
    
  • Predicado 6: Asigne valores que satisfagan las restricciones a un subconjunto de celdas en blanco, luego con esos valores solo hay una solución para el tablero.

    hs.       Output is a subset of the blank cells
    :=a,      Assign values to those cells
    ?t:9ac    Concatenate the values of all cells of the board
    :=f       Find all solved boards
    l1        There is only 1 such solved board
    
  • Predicado 7: transforma el tablero de modo que cada celda ahora sea en [V:X:Y]lugar de solo V(el valor).

    :Im       Take the Ith line of the board
    :8f       Transform all elements of the line using predicate 8
    :[[I]]z   Zip the result with [I]
    :ca.      Concatenate each element of the zip
    
  • Predicado 8: transforma una línea tal que cada celda es ahora [V:X].

    :Jm    Take the Jth element of the line
    :J.    Output is [That element:J]
    
  • Predicado 9: recupera los valores de las celdas

    :ha.   Take the head of each element of the input
    
  • Predicado 10: agregue la longitud de un subconjunto al comienzo

    lg     Put the length of the input in a list
    :?c.   Concatenate it with the input
    
  • Predicado 11: Imprimir una celda

    b:+a[X:Y],        Increment coordinates by 1 to get X and Y
    ?h:Y:Xr:          Build the list [X:Y:Value]
    "(~d,~d):~d\n"w   Format that list as "('X','Y'):'Value'\n" to STDOUT
    
Fatalizar
fuente
2
¿No puedes expandir esto a una respuesta de Prolog? ¡Entonces estaría compitiendo! (Podría publicarlo por separado). No estoy seguro de cuán directa es la asignación entre Brachylog y Prolog.
Lynn
@ Lynn Sí, podría, incluso podría publicar el código de Prolog que se genera por el transpilador de Brachylog (que obviamente sería muy poco golfista). Sin embargo, no lo haré porque estoy bastante seguro de que el póster del desafío nunca volverá a aceptar una respuesta de todos modos: p
Fatalize