N-queen-and-equine quine

Question

There is a variant of the well-known N-queens problem which involves queens and knights and is said to be "considerably more difficult" ¹. The problem statement is as follows:

You must place an equal number of knights ♞ and queens ♛ on a chessboard such that no piece attacks any other piece. What is the maximum number of pieces you can so place on the board, and how many different ways can you do it?

In this code-golf challenge, you will be given an input n between 3 and 32 (in a way that is the most suitable for your language). For a given n, there might be zero or more solutions to the above problem. In case there is no solution, you must output/return nothing (nil, empty string, false, ...). Otherwise, you must give two results:

1. A solution board (see below) for size n where it is not possible to add a queen or a knight chess piece without having any piece being under attack. There must be an equal number of queens and knights.
2. The source of a program to be run which accepts no input and gives (i) another solution (or nothing) for the same size n, in the same format, as well as (ii) another program for the next solution (and so on...).

Note that:

• The sequence of programs must never return the same board twice, must cover all possible solutions for the problem of size n and eventually has to terminate (producing no output).
• You can either return two values, return one and print the other, or print the two return values.
• However, if you print both the board and the next program, the board must not be considered to be a part of the next program (I'd recommend printing the board in comment, or use both standard output and error streams).
• The program-as-a-return-value must be a string, not a closure.

Board format

• A board is a square of size n.
• A board cell can be empty, a queen or a knight.
• You must choose distinct values for each kind of cells (i.e. you can use other symbols than Q, N when printing the board).
• If you return a non-string board, it must be an ordered collection of the n² values of the board (e.g. matrix, vector or list in row/column-major order, ...).

• If you print the board, you can either print it squared, or as a line. For example, a solution board of size 4 can be printed as follows (spaces not required; symbols at your discretion):

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

  If you feel so, you can also output:

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

  ... but this is sufficient:

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

  It does not matter if you iterate through cells in a row-major or column-major order, because there are symmetrical solutions. For example, the solutions for n=4 are:

  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
  

You can also look at the solutions for n=5 as matrices; the boards contains #, q and n symbols, which are empty cells of different kinds (see my answer below). I count 2836 boards for n=6, like in Sleafar's answer (I introduced a bug when reducing byte count, but it is fixed now).

Many thanks to Sleafar for finding not one but two bugs in my code.

Score

Shortest code in bytes win.

We measure the size of the first program, the one which accepts n.

---

1. Queens and Knights, by Roger K.W. Hui (beware! contains a solution)

Answer 1

Common Lisp, 737

^self-answer

(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)())))))

Example

Paste the above in the REPL, which returns a function object:

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

Call it (the star is bound to the last returned value):

QN> (funcall * 4)

This prints the following to the standard output:

(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)))))

Also, the value returned by this function is:

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

... which is an array literal. Number 5 represents queens, 6 is for knights and anything else stands for an empty cell, except there are more informations stored internally. If we copy-paste the returned function to the repl, we obtain a new function.

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

And we can call it to, without arguments:

QN> (funcall * )

This call returns a new solution #(5 0 0 0 0 0 0 2 0 0 0 6 0 0 2 0) and the source of another function (not shown here). In case the original function or the last generated one does not find a solution, nothing is printed and nothing is returned.

Internal values

|----------+--------+---------+--------+-----------------|
|          | 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        |
|----------+--------+---------+--------+-----------------|

I used to generate too few solutions. Now, I propagate what cell is safe for a queen and for a knight, independently. For example, here is an output for n=5 with pretty-printing:

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

When we placed the queen Q, positions that are a knight-move away from this queen are still safe for queens and denoted q. Likewise, knights that are reachable only by queens are safe for other knights. Values are bitwise and-ed to represent the possible moves and some cells are reachable by no kind of piece.

More precisely, here is the sequence of boards leading to the following solution (from left to right), where free cells are gradually constrained with different values:

# # # # # #     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

Non-quine approach

Ungolfed, commented version

(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)))

Duplicates and bugs

My very first solution outputted duplicate solutions. In order to solve it, I introduced two counters for queens and knights. The counter for queens (resp. knights) keep track of the first position in the board where a queen (resp. knight) exists: I add a queen (resp. a knight) only at positions that follow that minimal position.

That methods prevents me from revisiting solutions that were already found in previous iterations, because I iterate with an increasing queen (resp. knight) position.

However, Sleafar noticed that there were solutions for which there could be room for queens and knights, which is against the rules. For a while I though I had to revert to a normal search and store all the known solutions to prevent duplicates, which felt too costly (both in terms of bytes and memory usage).

Instead, here is what I do now: when a potential solution board is found, I try to add exactly one queen and one knight, without taking into account the counters (i.e. for all cells on the board). If this is possible, then current board is a duplicate of a previous one, and I reject the solution.

Tests

|---+---------+------------+--------------|
| 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 |
|---+---------+------------+--------------|

Quine-ification

I had different ideas to make successive quines. The easiest one is probably to generate all solutions first as a list of strings and write sequential quines which pop from that list at each generation. However this did not seem to be shorter than current approach. Alternatively, I tried to rewrite the recursive code with a custom stack and dump all the state variables each time I find a solution; the goal is that the next step can be processed as a continuation of current step. Maybe this would be better suited for a stack based language. The current one is quite simple and rely on Common Lisp reader variables, which are always fun to use.

Answer 2

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))

Testing

Provide n as a command line argument:

groovy qak.groovy 4

The first line of the output is always a solution as a comment (0=empty, 1=queen, 2=knight), followed by the code in the second line:

//[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))

The following script can be used for automated testing (provide n as an argument again):

#!/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

Because I tried to make the solution as small as possible, it is very slow (see below for details). I tested only n=4 with this version to see if the quineification works.

Results

n=4: 40 solutions (converted format)
n=5: 172 solutions (converted format)
n=6: 2836 solutions (converted format)

Algorithm

This is a slightly ungolfed non-quine version of the solution:

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

I used a very simple approach here to keep the code size low.

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

The variable X holds the index of the solution to print next. Y holds a modified copy of the algorithm above, which is used to calculate all solutions and then select only one of them, which is the reason for it being so slow. The advantage of this solution is, that it doesn't require much additional code. The code stored in Y is executed with help of the Eval class (a true quine is not required).

The modified code prints the solution pointed to by X, increases X and appends a copy of itself:

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

I also tried to output all solutions as code for the second step, but for n=6 it was producing too much code for Groovy to handle.