N-queen-and-equine quine

21

Ada varian dari masalah N-ratu yang terkenal yang melibatkan ratu dan ksatria dan dikatakan "jauh lebih sulit" 1 . Pernyataan masalah adalah sebagai berikut:

Anda harus menempatkan jumlah ksatria yang sama que dan ratu ♛ di papan catur sehingga tidak ada bagian yang menyerang bagian lainnya. Berapa jumlah maksimum potongan yang bisa Anda letakkan di papan tulis, dan berapa banyak cara berbeda yang bisa Anda lakukan?

Dalam tantangan , Anda akan diberikan input n antara 3 dan 32 (dengan cara yang paling cocok untuk bahasa Anda). Untuk n yang diberikan , mungkin ada nol atau lebih solusi untuk masalah di atas. Jika tidak ada solusi, Anda harus mengeluarkan / mengembalikan apa-apa ( nihil , string kosong , false , ...). Jika tidak, Anda harus memberikan dua hasil:

  1. Papan solusi (lihat di bawah) untuk ukuran dan di mana tidak mungkin untuk menambahkan ratu atau bidak catur ksatria tanpa ada bagian yang sedang diserang. Harus ada jumlah ratu dan ksatria yang sama .
  2. Sumber program yang akan dijalankan yang tidak menerima input dan memberikan (i) solusi lain (atau tidak sama sekali ) untuk ukuran yang sama n , dalam format yang sama, serta (ii) program lain untuk solusi berikutnya (dan seterusnya). ...).

Perhatikan bahwa:

  • Urutan program tidak boleh mengembalikan papan yang sama dua kali, harus mencakup semua solusi yang mungkin untuk masalah ukuran n dan akhirnya harus diakhiri (tidak menghasilkan output).
  • Anda bisa mengembalikan dua nilai, mengembalikan satu dan mencetak yang lain, atau mencetak dua nilai kembali.
  • Namun , jika Anda mencetak papan dan program berikutnya, papan tersebut tidak boleh dianggap sebagai bagian dari program berikutnya (saya akan merekomendasikan mencetak papan dalam komentar, atau menggunakan keluaran standar dan aliran kesalahan).
  • Program-as-a-return-value harus berupa string, bukan penutupan.

Format papan

  • Papan adalah ukuran persegi n .
  • Sel papan bisa kosong, ratu atau ksatria.
  • Anda harus memilih nilai yang berbeda untuk setiap jenis sel (yaitu Anda dapat menggunakan simbol selain Q, N saat mencetak papan).
  • Jika Anda kembali papan non-string, itu harus menjadi memerintahkan koleksi n 2 nilai dewan (misalnya matriks, vektor atau daftar di baris / kolom-besar pesanan, ...).
  • Jika Anda mencetak papan, Anda dapat mencetaknya dengan kuadrat, atau sebagai garis. Misalnya, papan solusi ukuran 4 dapat dicetak sebagai berikut (spasi tidak diperlukan; simbol sesuai kebijaksanaan Anda):

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

    Jika Anda merasa demikian, Anda juga dapat menampilkan:

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

    ... tapi ini sudah cukup:

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

    Tidak masalah jika Anda beralih melalui sel dalam urutan baris-mayor atau kolom-mayor, karena ada solusi simetris. Sebagai contoh, solusi untuk n = 4 adalah:

    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
    

Anda juga dapat melihat solusi untuk n = 5 sebagai matriks ; papan berisi #, qdan nsimbol, yang merupakan sel kosong dari berbagai jenis (lihat jawaban saya di bawah). Saya menghitung 2836 papan untuk n = 6 , seperti pada jawaban Sleafar (saya memperkenalkan bug ketika mengurangi jumlah byte, tetapi sudah diperbaiki sekarang).

Terima kasih banyak kepada Sleafar karena menemukan bukan hanya satu tetapi dua bug dalam kode saya.

Skor

Kode terpendek dalam byte menang.

Kami mengukur ukuran program pertama, yang menerima n .


1 . Ratu dan Ksatria , oleh Roger KW Hui (waspadalah! Mengandung solusi)

coredump
sumber
4
Mungkin Anda harus memberi hadiah pada ini. Jujur saja, masalahnya cukup sulit tanpa bagian quine.
mbomb007
Bisakah kita menggunakan simbol selain Q, N dan - untuk menunjukkan Ratu dan Ksatria dan kosong, selama mereka berbeda?
Fatalkan tanggal
@Fatalize Ya, tentu
coredump
1
@coredump maksud saya membaca isi dari fungsi. Dan saya akan menganggapnya sebagai "ya, Anda diizinkan membaca kode sumber dan / atau konten fungsi Anda sendiri". (Solusi saya bergantung padanya, jadi ...)
wizzwizz4
1
@coredump Jika saya memahami tantangan dengan benar, maka solusi referensi Anda untuk n = 6 berisi entri yang tidak valid (mis. -------------------------N--------Q-tidak valid karena lebih banyak bagian dapat ditambahkan :) Q--------N---------------N--------Q-.
Sleafar

Jawaban:

2

Groovy, 515 byte

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

Pengujian

Berikan n sebagai argumen baris perintah:

groovy qak.groovy 4

Baris pertama dari output selalu merupakan solusi sebagai komentar (0 = kosong, 1 = ratu, 2 = ksatria), diikuti oleh kode di baris kedua:

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

Script berikut dapat digunakan untuk pengujian otomatis (berikan n sebagai argumen lagi):

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

Karena saya mencoba membuat solusi sekecil mungkin, ini sangat lambat (lihat di bawah untuk detailnya). Saya hanya menguji n = 4 dengan versi ini untuk melihat apakah quineification berfungsi.

Hasil

n = 4: 40 solusi ( format yang dikonversi )
n = 5: 172 solusi ( format yang dikonversi )
n = 6: 2836 solusi ( format yang dikonversi )

Algoritma

Ini adalah versi solusi non-quine yang sedikit tidak disunat:

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

Saya menggunakan pendekatan yang sangat sederhana di sini untuk menjaga ukuran kode tetap rendah.

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

Variabel X memegang indeks solusi untuk dicetak berikutnya. Y memegang salinan modifikasi dari algoritma di atas, yang digunakan untuk menghitung semua solusi dan kemudian memilih hanya satu dari mereka, yang merupakan alasan untuk itu sangat lambat. Keuntungan dari solusi ini adalah, tidak memerlukan banyak kode tambahan. Kode yang disimpan dalam Y dijalankan dengan bantuan kelas Eval (quine yang sebenarnya tidak diperlukan).

Kode yang dimodifikasi mencetak solusi yang ditunjukkan oleh X , menambah X dan menambahkan salinannya sendiri:

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

Saya juga mencoba untuk mengeluarkan semua solusi sebagai kode untuk langkah kedua, tetapi untuk n = 6 itu menghasilkan terlalu banyak kode untuk ditangani oleh Groovy.

Sleafar
sumber
Jawaban yang bagus, kerja bagus.
coredump
6

Common Lisp, 737

jawaban sendiri

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

Contoh

Tempel di atas dalam REPL, yang mengembalikan objek fungsi:

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

Sebut saja (bintang terikat dengan nilai yang dikembalikan terakhir):

QN> (funcall * 4)

Ini mencetak yang berikut ini ke output standar:

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

Juga, nilai yang dikembalikan oleh fungsi ini adalah:

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

... yang merupakan array literal. Angka 5 mewakili ratu, 6 untuk ksatria dan yang lainnya berarti sel kosong, kecuali ada lebih banyak informasi yang disimpan secara internal. Jika kami menyalin-tempel fungsi yang dikembalikan ke repl, kami memperoleh fungsi baru.

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

Dan kita dapat menyebutnya, tanpa argumen:

QN> (funcall * )

Panggilan ini mengembalikan solusi baru #(5 0 0 0 0 0 0 2 0 0 0 6 0 0 2 0)dan sumber fungsi lain (tidak ditampilkan di sini). Jika fungsi asli atau yang terakhir dibuat tidak menemukan solusi, tidak ada yang dicetak dan tidak ada yang dikembalikan.

Nilai internal

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

Saya dulu menghasilkan terlalu sedikit solusi. Sekarang, saya menyebarkan sel apa yang aman untuk seorang ratu dan untuk seorang ksatria, secara mandiri. Sebagai contoh, ini adalah output untuk n = 5 dengan pencetakan cantik:

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

Ketika kami menempatkan ratu Q, posisi yang merupakan ksatria-pindah dari ratu ini masih aman untuk ratu dan dilambangkan q. Demikian juga, ksatria yang hanya bisa dijangkau oleh ratu aman untuk ksatria lain. Nilai bitwise dan -ed untuk mewakili gerakan yang mungkin dan beberapa sel dapat dicapai dengan tidak ada bagian.

Lebih tepatnya, di sini adalah urutan papan yang mengarah ke solusi berikut (dari kiri ke kanan), di mana sel bebas secara bertahap dibatasi dengan nilai yang berbeda:

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

Pendekatan non-quine

Versi komentar yang tidak disatukan

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

Duplikat dan bug

Solusi pertama saya menghasilkan solusi duplikat. Untuk mengatasinya, saya memperkenalkan dua counter untuk ratu dan ksatria. Penghitung untuk ratu (resp. Ksatria) melacak posisi pertama di papan tempat seorang ratu (resp. Ksatria) ada: Saya menambahkan ratu (resp. Seorang ksatria) hanya pada posisi yang mengikuti posisi minimal itu.

Metode itu mencegah saya mengunjungi kembali solusi yang sudah ditemukan di iterasi sebelumnya, karena saya beralih dengan posisi ratu (resp. Knight) yang semakin meningkat.

Namun, Sleafar memperhatikan bahwa ada solusi yang mungkin ada ruang untuk ratu dan ksatria, yang bertentangan dengan aturan. Untuk sementara saya pikir saya harus kembali ke pencarian normal dan menyimpan semua solusi yang dikenal untuk mencegah duplikat, yang terasa terlalu mahal (baik dalam hal byte dan penggunaan memori).

Alih-alih, inilah yang saya lakukan sekarang: ketika papan solusi potensial ditemukan, saya mencoba menambahkan satu ratu dan satu ksatria, tanpa memperhitungkan penghitung (yaitu untuk semua sel di papan). Jika ini memungkinkan, maka board saat ini adalah duplikat dari yang sebelumnya, dan saya menolak solusinya.

Tes

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

Saya punya ide berbeda untuk membuat quines berturut-turut. Yang paling mudah mungkin untuk menghasilkan semua solusi pertama sebagai daftar string dan menulis quines berurutan yang muncul dari daftar itu di setiap generasi. Namun ini tampaknya tidak lebih pendek dari pendekatan saat ini. Atau, saya mencoba untuk menulis ulang kode rekursif dengan tumpukan kustom dan membuang semua variabel keadaan setiap kali saya menemukan solusi; tujuannya adalah bahwa langkah selanjutnya dapat diproses sebagai kelanjutan dari langkah saat ini. Mungkin ini akan lebih cocok untuk bahasa berbasis stack. Yang saat ini cukup sederhana dan mengandalkan variabel Common Lisp reader, yang selalu menyenangkan untuk digunakan.

coredump
sumber