Es gibt eine Variante des bekannten N-Königinnen-Problems, die Königinnen und Ritter betrifft und als "wesentlich schwieriger" bezeichnet wird ¹ . Die Problemstellung lautet wie folgt:

Sie müssen eine gleiche Anzahl von Rittern ♞ und Königinnen ♛ auf ein Schachbrett legen, sodass keine Figur eine andere angreift. Was ist die maximale Anzahl von Stücken, die Sie so auf das Brett legen können, und wie viele verschiedene Arten können Sie es tun?

Bei dieser Code-Golf- Herausforderung erhalten Sie eine Eingabe n zwischen 3 und 32 (so, wie es für Ihre Sprache am besten geeignet ist). Für ein gegebenes n kann es keine oder mehrere Lösungen für das obige Problem geben. Falls es keine Lösung gibt, müssen Sie nichts ausgeben / zurückgeben ( null , leere Zeichenfolge , falsch , ...). Andernfalls müssen Sie zwei Ergebnisse angeben:

1. Eine Lösungskarte (siehe unten) für Größe n, bei der es nicht möglich ist, eine Dame oder eine Ritterschachfigur hinzuzufügen, ohne dass eine Figur angegriffen wird. Es muss eine gleiche Anzahl von Königinnen und Rittern geben .
2. Die Quelle eines auszuführenden Programms, das keine Eingabe akzeptiert und (i) eine andere Lösung (oder nichts ) für die gleiche Größe n im gleichen Format sowie (ii) ein anderes Programm für die nächste Lösung (und so weiter ) liefert ...).

Beachten Sie, dass:

• Die Programmsequenz darf niemals dieselbe Karte zweimal zurückgeben, muss alle möglichen Lösungen für das Problem der Größe n abdecken und muss schließlich enden (keine Ausgabe produzieren).
• Sie können entweder zwei Werte zurückgeben, einen zurückgeben und den anderen ausdrucken oder die beiden Rückgabewerte ausdrucken.
• Allerdings , wenn Sie sowohl drucken Sie das Brett, und das nächste Programm, muss der Vorstand nicht als Teil des nächsten Programms in Betracht gezogen werden (Ich würde empfehlen , das Brett in Kommentar Drucke oder verwenden sowohl die Standardausgabe und Fehlerströme).
• Der Rückgabewert des Programms muss eine Zeichenfolge sein, kein Abschluss.

Kartenformat

• Eine Tafel ist ein Quadrat der Größe n .
• Eine Brettzelle kann leer sein, eine Königin oder ein Ritter.
• Sie müssen unterschiedliche Werte für jede Art von Zellen auswählen (dh Sie können beim Drucken der Karte andere Symbole als Q, N verwenden).
• Wenn Sie ein Board ohne Zeichenfolge zurückgeben, muss es eine geordnete Sammlung der n ² -Werte des Boards sein (z. B. Matrix, Vektor oder Liste in Zeilen- / Spalten-Hauptreihenfolge, ...).

• Wenn Sie die Tafel drucken, können Sie sie entweder im Quadrat oder als Linie drucken. Zum Beispiel kann eine Lösungskarte der Größe 4 wie folgt gedruckt werden (Leerzeichen nicht erforderlich; Symbole nach Ihrem Ermessen):

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

  Wenn Sie dies wünschen, können Sie auch Folgendes ausgeben:

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

  ... aber das reicht aus:

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

  Es spielt keine Rolle, ob Sie Zellen in einer Zeilen- oder Spaltenfolge durchlaufen, da es symmetrische Lösungen gibt. Zum Beispiel sind die Lösungen für n = 4:

  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
  

Sie können die Lösungen für n = 5 auch als Matrizen betrachten ; die Platten enthalten #, qund nSymbole, die leeren Zellen verschiedener Arten sind (siehe meine Antwort unten). Ich zähle 2836 Boards für n = 6 , wie in Sleafars Antwort (ich habe einen Fehler beim Reduzieren der Byteanzahl eingeführt, aber er ist jetzt behoben).

Vielen Dank an Sleafar, dass sie nicht nur einen, sondern zwei Fehler in meinem Code gefunden haben.

Ergebnis

Kürzester Code in Bytes gewinnen.

Wir messen die Größe des ersten Programms, das n akzeptiert .

1 . Königinnen und Ritter , von Roger KW Hui (Vorsicht! Enthält eine Lösung)

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

Testen

Geben Sie n als Befehlszeilenargument an:

groovy qak.groovy 4

Die erste Zeile der Ausgabe ist immer eine Lösung als Kommentar (0 = leer, 1 = Dame, 2 = Ritter), gefolgt vom Code in der zweiten Zeile:

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

Das folgende Skript kann für automatisierte Tests verwendet werden (erneut n als Argument angeben):

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

Da ich versucht habe, die Lösung so klein wie möglich zu halten, ist sie sehr langsam (Einzelheiten siehe unten). Ich habe mit dieser Version nur n = 4 getestet, um zu sehen, ob die Quineifizierung funktioniert.

Ergebnisse

n = 4: 40 Lösungen ( konvertiertes Format )
n = 5: 172 Lösungen ( konvertiertes Format )
n = 6: 2836 Lösungen ( konvertiertes Format )

Algorithmus

Dies ist eine leicht ungolfederte, nicht quine Version der Lösung:

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

Quineifikation

Ich habe hier einen sehr einfachen Ansatz gewählt, um die Codegröße niedrig zu halten.

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

Die Variable X enthält den Index der Lösung, die als nächstes gedruckt werden soll. Y enthält eine modifizierte Kopie des obigen Algorithmus, mit der alle Lösungen berechnet und dann nur eine davon ausgewählt werden. Dies ist der Grund dafür, dass der Algorithmus so langsam ist. Der Vorteil dieser Lösung ist, dass nicht viel zusätzlicher Code benötigt wird. Der in Y gespeicherte Code wird mit Hilfe der Eval- Klasse ausgeführt (eine echte Quine ist nicht erforderlich).

Der geänderte Code gibt die Lösung aus, auf die X zeigt , erhöht X und fügt eine Kopie von sich selbst an:

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

Ich habe auch versucht, alle Lösungen als Code für den zweiten Schritt auszugeben, aber für n = 6 wurde zu viel Code erzeugt, als dass Groovy damit umgehen konnte.

Common Lisp, 737

^{Selbstantwort}

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

Beispiel

Fügen Sie das Obige in die REPL ein, die ein Funktionsobjekt zurückgibt:

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

Nennen Sie es (der Stern ist an den zuletzt zurückgegebenen Wert gebunden):

QN> (funcall * 4)

Dies druckt Folgendes auf die Standardausgabe:

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

Der von dieser Funktion zurückgegebene Wert ist außerdem:

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

... das ist ein Array-Literal. Nummer 5 steht für Königinnen, 6 für Ritter und alles andere steht für eine leere Zelle, außer es sind weitere Informationen intern gespeichert. Wenn wir die zurückgegebene Funktion kopieren und in die Replik einfügen, erhalten wir eine neue Funktion.

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

Und wir können es ohne Argumente nennen:

QN> (funcall * )

Dieser Aufruf gibt eine neue Lösung #(5 0 0 0 0 0 0 2 0 0 0 6 0 0 2 0)und die Quelle einer anderen Funktion zurück (hier nicht gezeigt). Falls die ursprüngliche oder die zuletzt erzeugte Funktion keine Lösung findet, wird nichts gedruckt und nichts zurückgegeben.

Interne Werte

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

Früher habe ich zu wenige Lösungen generiert. Nun propagiere ich unabhängig voneinander, welche Zelle für eine Königin und einen Ritter sicher ist. Hier ist zum Beispiel eine Ausgabe für n = 5 mit hübschem Ausdruck:

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

Wenn wir die Königin platzieren Q, sind Positionen, die ein Springer von dieser Königin entfernt sind, für Königinnen immer noch sicher und gekennzeichnet q. Ebenso sind Ritter, die nur von Königinnen erreicht werden können, für andere Ritter sicher. Die Werte sind bitweise und -ed, um die möglichen Bewegungen darzustellen, und einige Zellen sind von keiner Art von Stück erreichbar.

Genauer gesagt, hier ist die Reihenfolge der Karten, die zu der folgenden Lösung führt (von links nach rechts), bei der freie Zellen allmählich mit unterschiedlichen Werten eingeschränkt werden:

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

Ungolfed, kommentierte 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)))

Duplikate und Bugs

Meine allererste Lösung gab doppelte Lösungen aus. Um das Problem zu lösen, habe ich zwei Marken für Königinnen und Ritter eingeführt. Der Zähler für Königinnen (bzw. Ritter) verfolgt die erste Position auf dem Brett, an der eine Königin (bzw. ein Ritter) existiert: Ich füge eine Königin (bzw. einen Ritter) nur an Positionen hinzu, die auf diese minimale Position folgen.

Diese Methode hindert mich daran, Lösungen erneut aufzurufen, die bereits in früheren Iterationen gefunden wurden, da ich mit zunehmender Position der Dame (bzw. des Ritters) iteriere.

Sleafar bemerkte jedoch, dass es Lösungen gab, für die Königinnen und Ritter Platz hatten, was gegen die Regeln verstieß. Für eine Weile musste ich jedoch zu einer normalen Suche zurückkehren und alle bekannten Lösungen speichern, um Duplikate zu vermeiden, die sich zu kostspielig anfühlten (sowohl in Bezug auf Bytes als auch auf die Speichernutzung).

Stattdessen mache ich jetzt Folgendes: Wenn ein mögliches Lösungsbrett gefunden wird, versuche ich, genau eine Dame und einen Ritter hinzuzufügen , ohne die Zähler zu berücksichtigen (dh für alle Zellen auf dem Brett). Wenn dies möglich ist, ist die aktuelle Karte ein Duplikat der vorherigen und ich lehne die Lösung ab.

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

Ich hatte verschiedene Ideen, um aufeinanderfolgende Quines herzustellen. Am einfachsten ist es wahrscheinlich, alle Lösungen zuerst als Liste von Zeichenfolgen zu generieren und sequentielle Quines zu schreiben, die bei jeder Generation aus dieser Liste hervorgehen. Dies schien jedoch nicht kürzer zu sein als der derzeitige Ansatz. Alternativ habe ich versucht, den rekursiven Code mit einem benutzerdefinierten Stapel neu zu schreiben und jedes Mal, wenn ich eine Lösung finde, alle Statusvariablen zu sichern. das ziel ist, dass der nächste schritt als fortsetzung des aktuellen schritts abgearbeitet werden kann. Vielleicht ist dies besser für eine stapelbasierte Sprache geeignet. Die aktuelle Version ist recht einfach und basiert auf Common Lisp Reader-Variablen, deren Verwendung immer Spaß macht.