Existe una variante del conocido problema de N-reinas que involucra a reinas y caballeros y se dice que es "considerablemente más difícil" ¹ . La declaración del problema es la siguiente:

Debes colocar un número igual de caballeros ♞ y reinas ♛ en un tablero de ajedrez de modo que ninguna pieza ataque a ninguna otra pieza. ¿Cuál es el número máximo de piezas que puede colocar en el tablero y de cuántas maneras diferentes puede hacerlo?

En este desafío de código de golf , se le dará una entrada n entre 3 y 32 (de la manera que sea más adecuada para su idioma). Para un n dado , puede haber cero o más soluciones al problema anterior. En caso de que no haya solución, debe generar / devolver nada ( nulo , cadena vacía , falso , ...). De lo contrario, debe dar dos resultados:

1. Un tablero de solución (ver más abajo) para el tamaño n donde no es posible agregar una pieza de ajedrez de reina o caballero sin tener ninguna pieza bajo ataque. Debe haber un número igual de reinas y caballeros .
2. La fuente de un programa a ejecutar que no acepta entradas y proporciona (i) otra solución (o nada ) para el mismo tamaño n , en el mismo formato, así como (ii) otro programa para la próxima solución (y así sucesivamente) ...)

Tenga en cuenta que:

• La secuencia de programas nunca debe devolver la misma placa dos veces, debe cubrir todas las soluciones posibles para el problema del tamaño n y, finalmente, tiene que terminar (sin producir ninguna salida).
• Puede devolver dos valores, devolver uno e imprimir el otro, o imprimir los dos valores devueltos.
• Sin embargo , si imprime tanto la placa como el siguiente programa, no se debe considerar que la placa forma parte del siguiente programa (recomendaría imprimir la placa en comentario, o utilizar tanto la salida estándar como las secuencias de error).
• El programa como valor de retorno debe ser una cadena, no un cierre.

Formato de tablero

• Un tablero es un cuadrado de tamaño n .
• Una celda de tablero puede estar vacía, una reina o un caballero.
• Debe elegir valores distintos para cada tipo de celdas (es decir, puede usar otros símbolos que Q, N al imprimir el tablero).
• Si devuelve un tablero sin cadenas, debe ser una colección ordenada de los n ² valores del tablero (por ejemplo, matriz, vector o lista en orden de fila / columna-mayor, ...).

• Si imprime el tablero, puede imprimirlo al cuadrado o como una línea. Por ejemplo, una placa de solución de tamaño 4 se puede imprimir de la siguiente manera (no se requieren espacios; símbolos a su discreción):

  Q - - -
  - - - -
  - - - -
  - - N -
  

  Si lo cree así, también puede generar:

  ♛ · · ·
  · · · ·
  · · · ·
  · · ♞ ·
  

  ... pero esto es suficiente:

  Q-------------N-
  

  No importa si recorre las celdas en un orden de fila mayor o columna mayor, porque hay soluciones simétricas. Por ejemplo, las soluciones para n = 4 son:

  Q------N--------
  Q----------N----
  Q------------N--
  Q-------------N-
  -Q----------N---
  -Q------------N-
  -Q-------------N
  --Q---------N---
  --Q----------N--
  --Q------------N
  ---QN-----------
  ---Q----N-------
  ---Q---------N--
  ---Q----------N-
  ---NQ-----------
  ----Q------N----
  ----Q----------N
  N------Q--------
  -------QN-------
  -------Q----N---
  ---N----Q-------
  -------NQ-------
  --------Q------N
  N----------Q----
  ----N------Q----
  -----------QN---
  -N----------Q---
  --N---------Q---
  -------N----Q---
  -----------NQ---
  N------------Q--
  --N----------Q--
  ---N---------Q--
  N-------------Q-
  -N------------Q-
  ---N----------Q-
  -N-------------Q
  --N------------Q
  ----N----------Q
  --------N------Q
  

También puede ver las soluciones para n = 5 como matrices ; los tableros contiene #, qy nsímbolos, que son células vacías de diferentes tipos (véase mi respuesta a continuación). Yo cuento 2836 tablas para n = 6 , al igual que en la respuesta de Sleafar (introduje un error cuando se reduce el recuento de bytes, pero se ha resuelto ahora).

Muchas gracias a Sleafar por encontrar no uno sino dos errores en mi código.

Puntuación

El código más corto en bytes gana.

Medimos el tamaño del primer programa, el que acepta n .

1 . Queens and Knights , por Roger KW Hui (¡cuidado! Contiene una solución)

Groovy, 515 bytes

X=0;Y="N="+args[0]+";M=N*N;S=[];def f(b,i,j,v){(i..<j).findAll{k->!(0..<M).any{l->w=b[l];r=(k.intdiv(N)-l.intdiv(N)).abs();c=(k%N-l%N).abs();s=v+w;w>0&&(k==l||(r==0||c==0||r==c?s<4:r<3&&c<3&&s>2))}}.collect{a=b.clone();a[it]=v;[it,a]}};def r(b,q,n){f(b,q,M,1).each{i->f(i[1],n,M,2).each{j->if(f(j[1],0,M,1).any{f(it[1],0,M,2)}){r(j[1],i[0],j[0])}else{S.add(j[1])}}}};r(new int[M],0,0);if(x<S.size()){sprintf('//%s%cX=%d;Y=%c%s%c;print(Eval.xy(X,Y,Y))',S[x].toString(),10,x+1,34,y,34)}else{''}";print(Eval.xy(X,Y,Y))

Pruebas

Proporcionar n como argumento de línea de comando:

groovy qak.groovy 4

La primera línea de la salida siempre es una solución como comentario (0 = vacío, 1 = reina, 2 = caballero), seguido del código en la segunda línea:

//[1, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0]
X=1;Y="N=4;M=N*N;S=[];def f(b,i,j,v){(i..<j).findAll{k->!(0..<M).any{l->w=b[l];r=(k.intdiv(N)-l.intdiv(N)).abs();c=(k%N-l%N).abs();s=v+w;w>0&&(k==l||(r==0||c==0||r==c?s<4:r<3&&c<3&&s>2))}}.collect{a=b.clone();a[it]=v;[it,a]}};def r(b,q,n){f(b,q,M,1).each{i->f(i[1],n,M,2).each{j->if(f(j[1],0,M,1).any{f(it[1],0,M,2)}){r(j[1],i[0],j[0])}else{S.add(j[1])}}}};r(new int[M],0,0);if(x<S.size()){sprintf('//%s%cX=%d;Y=%c%s%c;print(Eval.xy(X,Y,Y))',S[x].toString(),10,x+1,34,y,34)}else{''}";print(Eval.xy(X,Y,Y))

El siguiente script se puede usar para pruebas automatizadas (proporcione n como argumento nuevamente):

#!/bin/bash
set -e
test -n "$1"
groovy qak.groovy "$1" > t
while test -s t; do
    head -n1 t
    groovy t > t2
    mv t2 t
done

Porque traté de hacer la solución lo más pequeña posible, es muy lenta (ver más abajo para más detalles). Probé solo n = 4 con esta versión para ver si la quineificación funciona.

Resultados

n = 4: 40 soluciones ( formato convertido )
n = 5: 172 soluciones ( formato convertido )
n = 6: 2836 soluciones ( formato convertido )

Algoritmo

Esta es una versión no quine de la solución:

N=args[0] as int
M=N*N
S=[]

/**
 * Generate a list of valid posibilities to place a new piece.
 * @param b Starting board.
 * @param i Start of the index range to check (inclusive).
 * @param j End of the index range to check (exclusive).
 * @param v Value of the new piece (1=queen, 2=knight).
 * @return A pair with the index of the new piece and a corresponding board for each possibility.
 */
def f(b,i,j,v){
    (i..<j).findAll{k->
        !(0..<M).any{l->
            w=b[l]
            r=(k.intdiv(N)-l.intdiv(N)).abs()
            c=(k%N-l%N).abs()
            s=v+w
            w>0&&(k==l||(r==0||c==0||r==c?s<4:r<3&&c<3&&s>2))
        }
    }.collect{
        a=b.clone();a[it]=v;[it,a]
    }
}

/**
 * Recursively look for solutions.
 * @param b Starting board.
 * @param q Start of the index range to check for queens.
 * @param n Start of the index range to check for knights.
 */
def r(b,q,n){
    f(b,q,M,1).each{i->
        f(i[1],n,M,2).each{j->
            if(f(j[1],0,M,1).any{f(it[1],0,M,2)}){
                r(j[1],i[0],j[0])
            }else{
                S.add(j[1])
            }
        }
    }
}

r(new int[M],0,0)
S.each{println(it)}

Quineification

Utilicé un enfoque muy simple aquí para mantener bajo el tamaño del código.

X=0;Y="...";print(Eval.xy(X,Y,Y))

La variable X contiene el índice de la solución para imprimir a continuación. Y tiene una copia modificada del algoritmo anterior, que se utiliza para calcular todas las soluciones y luego seleccionar solo una de ellas, razón por la cual es tan lenta. La ventaja de esta solución es que no requiere mucho código adicional. El código almacenado en Y se ejecuta con la ayuda de Eval clase (no se requiere una quine verdadera).

El código modificado imprime la solución señalada por X , aumenta X y agrega una copia de sí mismo:

//[...]
X=1;Y="...";print(Eval.xy(X,Y,Y))

También intenté generar todas las soluciones como código para el segundo paso, pero para n = 6 estaba produciendo demasiado código para que Groovy lo manejara.

Lisp común, 737

^{auto-respuesta}

(lambda(n &aux(d 1))#2=(catch'$(let((s(* n n))(c d))(labels((R(w % @ b ! &aux r h v a)(loop for u from % below s do(setf h(mod u n)v(floor u n)a #4=(aref b u))(when(< 0(logand a w)4)(and(= 6 w)!(throw'! t))(let((b(copy-seq b))(o 5))(loop for(K D)on'(-1 -2 -1 2 1 -2 1 2)for y =(+ K v)for x =(+(or D -1)h)for u =(and(< -1 y n)(< -1 x n)(+(* y n)x))if u do #1=(if(< #4#4)(setf #4#(logand #4#o(if(= w o)3 0)))))(#8=dotimes(y N)(#8#(x N)(let((u(+(* y n)x))(o 6))(if(or(= x h)(= y v)(=(abs(- h x))(abs(- v y))))#1#))))(setf #4#w r(or(cond((= w 5)(R 6 @ U b !))((R 5 @ U b())t)((catch'!(R 5 0 0 b t))t)(t(and(=(decf c)0)(incf d)(or(format t"~%(lambda(&aux(n ~A)(d ~A))~%~S)"n d'#2#)(throw'$ B)))t))r)))))r))(R 5 0 0(fill(make-array s)3)())))))

Ejemplo

Pegue lo anterior en REPL, que devuelve un objeto de función:

#<FUNCTION (LAMBDA (N &AUX (D 1))) {1006D1010B}>

Llámelo (la estrella está vinculada al último valor devuelto):

QN> (funcall * 4)

Esto imprime lo siguiente en la salida estándar:

(lambda(&aux(n 4)(d 2))
#1=(CATCH '$
 (LET ((S (* N N)) (C D))
   (LABELS ((R (W % @ B ! &AUX R H V A)
              (LOOP FOR U FROM % BELOW S
                    DO (SETF H (MOD U N)
                             V (FLOOR U N)
                             A #2=(AREF B U)) (WHEN (< 0 (LOGAND A W) 4)
                                                (AND (= 6 W) !
                                                     (THROW '! T))
                                                (LET ((B (COPY-SEQ B))
                                                      (O 5))
                                                  (LOOP FOR (K D) ON '(-1
                                                                       -2
                                                                       -1 2
                                                                       1 -2
                                                                       1 2)
                                                        FOR Y = (+ K V)
                                                        FOR X = (+
                                                                 (OR D -1)
                                                                 H)
                                                        FOR U = (AND
                                                                 (< -1 Y N)
                                                                 (< -1 X N)
                                                                 (+ (* Y N)
                                                                    X))
                                                        IF U
                                                        DO #3=(IF (< #2# 4)
                                                                  (SETF #2#
                                                                          (LOGAND
                                                                           #2#
                                                                           O
                                                                           (IF (=
                                                                                W
                                                                                O)
                                                                               3
                                                                               0)))))
                                                  (DOTIMES (Y N)
                                                    (DOTIMES (X N)
                                                      (LET ((U
                                                             (+ (* Y N) X))
                                                            (O 6))
                                                        (IF (OR (= X H)
                                                                (= Y V)
                                                                (=
                                                                 (ABS
                                                                  (- H X))
                                                                 (ABS
                                                                  (- V
                                                                     Y))))
                                                            #3#))))
                                                  (SETF #2# W
                                                        R
                                                          (OR
                                                           (COND
                                                            ((= W 5)
                                                             (R 6 @ U B !))
                                                            ((R 5 @ U B
                                                                NIL)
                                                             T)
                                                            ((CATCH '!
                                                               (R 5 0 0 B
                                                                  T))
                                                             T)
                                                            (T
                                                             (AND
                                                              (= (DECF C)
                                                                 0)
                                                              (INCF D)
                                                              (OR
                                                               (FORMAT T
                                                                       "~%(lambda(&aux(n ~A)(d ~A))~%~S)"
                                                                       N D
                                                                       '#1#)
                                                               (THROW '$
                                                                 B)))
                                                             T))
                                                           R)))))
              R))
     (R 5 0 0 (FILL (MAKE-ARRAY S) 3) NIL)))))

Además, el valor devuelto por esta función es:

#(5 0 0 0 0 0 0 6 0 0 0 2 0 2 0 0)

... que es una matriz literal. El número 5 representa las reinas, el 6 es para los caballeros y cualquier otra cosa representa una celda vacía, excepto que hay más información almacenada internamente. Si copiamos y pegamos la función devuelta a la respuesta, obtenemos una nueva función.

#<FUNCTION (LAMBDA (&AUX (N 4) (D 2))) {100819148B}>

Y podemos llamarlo, sin argumentos:

QN> (funcall * )

Esta llamada devuelve una nueva solución. #(5 0 0 0 0 0 0 2 0 0 0 6 0 0 2 0) y el origen de otra función (no se muestra aquí). En caso de que la función original o la última generada no encuentre una solución, no se imprime nada y no se devuelve nada.

Valores internos

|----------+--------+---------+--------+-----------------|
|          | Binary | Decimal | Symbol | Meaning         |
|----------+--------+---------+--------+-----------------|
| Empty    |    000 |       0 | -      | safe for none   |
|          |    001 |       1 | q      | safe for queen  |
|          |    010 |       2 | n      | safe for knight |
|          |    011 |       3 | #      | safe for both   |
|----------+--------+---------+--------+-----------------|
| Occupied |    101 |       5 | Q      | a queen         |
|          |    110 |       6 | K      | a knight        |
|----------+--------+---------+--------+-----------------|

Solía ​​generar muy pocas soluciones. Ahora, propago qué celda es segura para una reina y un caballero, independientemente. Por ejemplo, aquí hay una salida para n = 5 con impresión bonita:

Q - - - - 
- - - n N 
- q - n n 
- # n - n 
- n # # - 

Cuando colocamos a la reina Q, las posiciones que están a un paso de distancia de esta reina aún son seguras para las reinas y se denotan q. Del mismo modo, los caballeros a los que solo las reinas pueden llegar son seguros para otros caballeros. Los valores son bit a bit y -ed para representar los posibles movimientos y algunas celdas son accesibles por ningún tipo de pieza.

Más precisamente, aquí está la secuencia de tableros que conducen a la siguiente solución (de izquierda a derecha), donde las celdas libres se restringen gradualmente con diferentes valores:

# # # # # #     q - - - q #     - - - - - #     - - - - - #     - - - - - n
# # # # # #     - - Q - - -     - - Q - - -     - - Q - - -     - - Q - - -
# # # # # #     q - - - q #     q - - - - -     Q - - - - -     Q - - - - -
# # # # # #     - q - q - #     - q - - - n     - - - - - n     - - - - - n
# # # # # #     # # - # # -     n n - n N -     - - - n N -     - - - - N -
# # # # # #     # # - # # #     # # - n n n     - # - - n n     - n - - n N

Enfoque no quine

Versión no comentada, comentada

(defun queens-and-knights
    (n    ; size of problem
     fn   ; function called for each solution

     ;; AUX parameters are like LET* bindings but shorter.
     &aux
       ;; total number of cells in a board
       (s (* n n)))

  (labels
      ;; Define recursive function R
      ((R (w      ; what piece to place: 5=queen, 6=knight 
           %      ; min position for piece of type W
           @      ; min position for the other kind of piece
           b      ; current board
           !      ; T iff we are in "check" mode (see below)
           &aux  
           r      ; result of this function: will be "true" iff we can
                  ; place at least one piece of type W on the board b
           h      ; current horizontal position 
           v      ; current vertical position
           a      ; current piece at position (h,v)
           )

         (loop
            ;; only consider position U starting from position %,
            ;; because any other position below % was already visited
            ;; at a higher level of recursion (e.g. the second queen
            ;; we place is being placed in a recursive call, and we
            ;; don't visit position before the first queen).
            for u from % below s

            do
              (setf h (mod u n)         ; Intialize H, V and A
                    v (floor u n)       ; 
                    a (aref b u))       ; 

            ;; Apply an AND mask to current value A in the board
            ;; with the type of chess piece W. In order to consider
            ;; position U as "safe", the result of the bitwise AND
            ;; must be below 4 (empty cell) and non-null.
              (when (< 0 (logand a w) 4)

                ;; WE FOUND A SAFE PLACE TO PUT PIECE W

                (when (and ! (= 6 w))
                  ;; In "check" mode, when we place a knight, we knwo
                  ;; that the check is successful. In other words, it
                  ;; is possible to place an additional queen and
                  ;; knight in some board up the call stack. Instead
                  ;; of updating the board we can directly exit from
                  ;; here (that gave a major speed improvement since
                  ;; we do this a lot). Here we do a non-local exit to
                  ;; the catch named "!".
                  (throw '! t))

                ;; We make a copy of current board b and bind it to the
                ;; same symbol b. This allocates a lot of memory
                ;; compared to the previous approach where I used a
                ;; single board and an "undo" list, but it is shorter
                ;; both in code size and in runtime.
                (let ((b (copy-seq b)))

                  ;; Propagate knights' constraints
                  (loop
                     ;; O is the other kind of piece, i.e. queen here
                     ;; because be propagate knights. This is used as
                     ;; a mask to remove knights pieces as possible
                     ;; choices.
                     with o = 5

                     ;; The list below is arranged so that two
                     ;; consecutive numbers form a knight-move. The ON
                     ;; iteration keyword descend sublist by sublist,
                     ;; i.e. (-1 -2), (-2 -1), (-1 2), ..., (2 NIL). We
                     ;; destructure each list being iterated as (K D),
                     ;; and when D is NIL, we use value -1.
                     for (K D) on '(-1 -2 -1 2 1 -2 1 2)

                     ;; Compute position X, Y and index U in board,
                     ;; while checking that the position is inside the
                     ;; board.
                     for y = (+ K v)
                     for x = (+ (or D -1) h)
                     for u = (and (< -1 y n)
                                  (< -1 x n)
                                  (+(* y n)x))

                     ;; if U is a valid position...
                     if u
                     do
                     ;; The reader variable #1# is affected to the
                     ;; following expression and reused below for
                     ;; queens. That's why the expression is not
                     ;; specific to knights. The trick here is to
                     ;; use the symbols with different lexical
                     ;; bindings.
                       #1=(when (< (aref b u) 4) ; empty?
                            (setf (aref b u)

                                  (logand
                                   ;; Bitwise AND of current value ...
                                   (aref b u)

                                   ;; ... with o: position U is not a
                                   ;; safe place for W (inverse of O)
                                   ;; anymore, because if we put a W
                                   ;; there, it would attack our
                                   ;; current cell (H,V).
                                   o

                                   ;; ... and with zero (unsafe for
                                   ;; all) if our piece W is also a
                                   ;; knight (resp. queen). Indeed, we
                                   ;; cannot put anything at position
                                   ;; U because we are attacking it.
                                   (if (= w o) 3 0)))))

                  ;; Propagate queens' constraints
                  (dotimes (y N)
                    (dotimes (x N)
                      (let ((u(+(* y n)x))(o 6))
                        (if (or (= x h)
                                (= y v)
                                (= (abs(- h x)) (abs(- v y))))

                            ;; Same code as above #1=(if ...)
                            #1#))))

                  (setf
                   ;; Place piece
                   (aref b u) w

                   ;; Set result value
                   r (or (cond
                           ;; Queen? Try to place a Knight and maybe
                           ;; other queens. The result is true only if
                           ;; the recursive call is.
                           ((= w 5) (R 6 @ U b !))

                           ;; Not a queen, so all below concern   
                           ;; knights: we always return T because
                           ;; we found a safe position.
                           ;; But we still need to know if
                           ;; board B is an actual solution and 
                           ;; call FN if it is.
                           ;; ------------------------------------

                           ;; Can be place a queen too? then current
                           ;; board is not a solution.
                           ((R 5 @ U b()) t)

                           ;; Try to place a queen and a knight
                           ;; without constraining the min positions
                           ;; (% and @); this is the "check" mode that
                           ;; is represented by the last argument to
                           ;; R, set to T here. If it throws true,
                           ;; then board B is a duplicate of a
                           ;; previous one, except that it is missing
                           ;; pieces due to constraints % and @. The
                           ;; "check" mode is a fix to a bug where we
                           ;; reported as solutions boards where there
                           ;; was still room for other pieces.
                           ((catch'!(R 5 0 0 b t)) t)

                           ;; Default case: we could not add one more
                           ;; layer of pieces, and so current board B
                           ;; is a solution. Call function FN.
                           (t (funcall fn b) t))

                         ;; R keeps being true if it already was for
                         ;; another position.
                         r)))))

         ;; Return result R
         r))

    ;; Start search with a queen and an empty board.
    (R 5 0 0 (fill (make-array s) 3)  nil)))

Duplicados y errores

Mi primera solución produjo soluciones duplicadas. Para resolverlo, presenté dos contadores para reinas y caballeros. El contador para reinas (resp. Caballeros) realiza un seguimiento de la primera posición en el tablero donde existe una reina (resp. Caballero): agrego una reina (resp. Un caballero) solo en las posiciones que siguen esa posición mínima.

Esos métodos me impiden volver a visitar soluciones que ya se encontraron en iteraciones anteriores, porque itero con una posición creciente de reina (resp. Caballero).

Sin embargo, Sleafar notó que había soluciones para las que podría haber espacio para reinas y caballeros, lo que va en contra de las reglas. Durante un tiempo pensé que tenía que volver a una búsqueda normal y almacenar todas las soluciones conocidas para evitar duplicados, lo que me pareció demasiado costoso (tanto en términos de bytes como de uso de memoria).

En cambio, esto es lo que hago ahora: cuando se encuentra una placa de solución potencial, trato de agregar exactamente una reina y una caballero, sin tener en cuenta los contadores (es decir, para todas las celdas en el tablero). Si esto es posible, la placa actual es un duplicado de una anterior, y rechazo la solución.

Pruebas

|---+---------+------------+--------------|
| N |  boards |    seconds |        bytes |
|---+---------+------------+--------------|
| 3 |       0 |          0 |        32768 |
| 4 |      40 |          0 |       360416 |
| 5 |     172 |          0 |      3440016 |
| 6 |    2836 |   0.085907 |     61251584 |
| 7 |   23876 |   1.265178 |    869666288 |
| 8 |  383586 |  24.991300 |  17235142848 |
| 9 | 6064506 | 524.982987 | 359952648832 |
|---+---------+------------+--------------|

Quineificación

Tenía diferentes ideas para hacer quines sucesivas. La más fácil es probablemente generar todas las soluciones primero como una lista de cadenas y escribir quines secuenciales que aparecen en esa lista en cada generación. Sin embargo, esto no parecía ser más corto que el enfoque actual. Alternativamente, traté de reescribir el código recursivo con una pila personalizada y volcar todas las variables de estado cada vez que encuentro una solución; El objetivo es que el siguiente paso se pueda procesar como una continuación del paso actual. Tal vez esto sería más adecuado para un lenguaje basado en pila. El actual es bastante simple y se basa en las variables del lector Common Lisp, que siempre son divertidas de usar.