N-queen-and-equine quine
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.
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.