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.
4Maybe you should put a bounty on this. Honestly, the problem is hard enough without the quine part. – mbomb007 – 2016-03-31T21:35:10.780
Can we use any symbols other than Q, N and - to denote Queens and Knights and empty, as long as they are distinct? – Fatalize – 2016-04-01T12:50:48.133
@Fatalize Yes, sure – coredump – 2016-04-01T12:56:24.820
@coredump Could you please give some example outputs for a board with a solution? Especially examples of what the second output would look like? – R. Kap – 2016-04-01T22:21:57.327
@R.Kap The second output depends heavily on which language you use. It should be a program or function that can produce the next solution as well as yet another program. I just posted an answer to give an example of what I have in mind. – coredump – 2016-04-02T08:53:59.580
We don't need to produce a "true quine", do we? Because that would be very ungolfy. – wizzwizz4 – 2016-04-03T16:39:08.520
@wizzwizz4 (1) This is not a "true" quine. Programs (textual source code) are generated in sequence, and the first generated one does not need to be in any way similar to the one you submit. It is inspired from questions like https://codegolf.stackexchange.com/questions/68521/growing-quine-sequence and https://codegolf.stackexchange.com/questions/69504/generate-programs-in-increasing-size. (2) There should be an objective winning criterion, and code-golf is sufficient here (and I think some people here are able to come up with an answer below, say, 200 bytes)
– coredump – 2016-04-03T17:39:45.0601@coredump I meant reading the contents of the function. And I'll take that as a "yes, you are allowed to read your own source code and / or function contents". (My solution relies on it, so...) – wizzwizz4 – 2016-04-03T18:33:46.777
@wizzwizz4 As long as your 1st function takes one arg. and the generated ones take none, as stated. I am curious about your solution, now... – coredump – 2016-04-03T18:52:38.173
1@coredump If I understand the challenge correctly, then your reference solution for n=6 contains invalid entries (e.g.
-------------------------N--------Q-is invalid because more pieces can be added:Q--------N---------------N--------Q-). – Sleafar – 2016-04-06T19:31:57.387@Sleafar Thank you very much, that's true. I'll investigate my answer and edit the question. – coredump – 2016-04-06T19:54:35.853
@coredump If you are still on, could you have a look at my solution so far? https://jsfiddle.net/wizzwizz4/c0v7pn73/
– wizzwizz4 – 2016-04-07T09:53:11.587@coredump There are still invalid entries (e.g.
– Sleafar – 2016-04-07T16:31:24.597--N--------------------------------Q->--N-------------N-------Q----------Q). My current solution for n=6 contains 2836 entries (0=empty, 1=queen, 2=knight).@Sleafar I tried to check, but I missed that. Back to the whiteboard, thanks. – coredump – 2016-04-07T17:08:22.890