LABTITLE=: 'Queens and Knights'
LABAUTHOR=: 'Roger Hui'
LABWIDTH=: 56
LABWRAP=: 0
LABCOMMENTS=: 'original writing: 2005-02-11; last changed: 2005-02-23'

NB. ====================================================
Lab Chapter    The Problem
NB. ====================================================
Lab Section The Problem

The webpage 
   http://www.itasoftware.com/careers/programmers.php
often contains interesting programming puzzles.  The 
"Queens & Knights" puzzle was posted in 2003-2004:

In 1850, Carl Friedrich Gauss and Franz Nauck showed 
that it is possible to place eight queens on a 
chessboard such that no queen attacks any other queen. 
The problem of enumerating the 92 different ways there 
are to place 8 queens in this manner has become a 
standard programming example, and people have shown that 
it can be solved using many different search techniques.

Now consider a variant of this problem: 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?
)
PREPARE 
NB. pre-define everything so that the reader can  
NB. safely jump to any chapter
n     =: 8

MT    =: ' '-.~' .NQxnq N???N? Q????Q x??xxx nN?xnx q?Qxxq'
MTy   =: (%:#MT){.MT
MTx   =: (##])MTy
merge =: MT"_ {~ MTx&i.@[ + MTy&i.@]

UI    =: >,{;~i.n
NI    =: _2]\_2 _1 _2 1 _1 _2 _1 2 1 _2 1 2 2 _1 2 1
QI    =: 0 0 -.~ (0&,. , ,.&0 , ,.~ , (,.|.)) i: n
mask  =: 3 : 'UI e."2 UI +"1"1 2 y.'
QT    =: '.Qqx' {~ (=i.n*n)+(2*mask NI)+3*mask QI
NT    =: '.Nxn' {~ '.Qqx'i.QT

q1    =: 3 : '~.((+/"1 b)#y.) merge QT {~ (n*n)|I.,b=. y.e.''.q'''
n1    =: 3 : '~.((+/"1 b)#y.) merge NT {~ (n*n)|I.,b=. y.e.''.n'''
qx    =: 4 : 'for_j. (-i.)x. do. y.=. q1 y.#~j<:+/"1 y.e.''.q'' end.'
nx    =: 4 : 'for_j. (-i.)x. do. y.=. n1 y.#~j<:+/"1 y.e.''.n'' end.'
qn    =: 3 : 'y. nx y. qx (1,n*n)$''.'''

see   =: ,~@%:@# $ 'QN'&i. { 'QN.'"_
var   =: ~.@(] , |:&.> , |.&.> , |."1&.>)^:3 
uvar  =: ~. @: ({.@(/:~)@var&>) @: (<@<@see"1)

x     =: '....xqxq....qxxxxxxxxxQx....qxxx....xqxq...x..x...x...x..x....x.'
y     =: '.n.....n.n....n..n...n...n..n...xnxn....nnnx....nNnnnnnnnnnx....'

PREPARE

NB. ====================================================
Lab Section 

The n queens problem can be solved succinctly and
efficiently.  A solution is presented in the "for." page 
of the J dictionary.

The queens and knights problem is considerably more
difficult.
)

NB. ====================================================
Lab Chapter    Configs
NB. ====================================================
Lab Section Configs

A _config_ is an n*n (n=:8) element string recording the 
placement of queens (Q) and knights (N) together with 
the coverage, the squares under attack by pieces already 
on the board and the squares from where additional 
pieces would attack an existing piece.

x below is a config.  Q indicates a square where a queen 
is placed, on row 2 and column 6.  x indicates a square 
under attack.  n indicates a square where a knight, if 
there placed, would attack Q.  A "." indicates a free 
square.

A queen can be placed on a "." or q square.  A knight 
can be placed on a "." square.
)
n=: 8
x=: '....xqxq....qxxxxxxxxxQx....qxxx....xqxq...x..x...x...x..x....x.'
(n,n) $ x

NB. ====================================================
Lab Section 

y below is another config.  N indicates a square where a 
knight is placed, on row 6 and column 1.  x indicates a 
square under attack.  n indicates a square where a 
queen, if there placed, would attack N.  A "." indicates 
a free square.

A knight can be placed on a "." or n square.  A queen 
can be placed on a "." square.
)
y=: '.n.....n.n....n..n...n...n..n...xnxn....nnnx....nNnnnnnnnnnx....'
(n,n) $ y

NB. ====================================================
Lab Section 

Our plan for solving the queens and knights problem is
as follows:  starting with the empty config ((n*n)$'.'), 
place queens and knights one piece at a time on all 
possible squares.  As a piece is placed the config is 
updated.

Placing a piece and updating the config means merging 
the config with a config that represents putting a 
piece on a particular square, to derive a new config.

Consider again the configs x (a Q on the (2,6) square) 
and y (an N on the (6,1) square).  How do we merge them?
That is, what is the config for a board with a Q on 
(2,6) and an N on (6,1)?
)
(<n,n) $&.> x;y;'?'

NB. ====================================================
Lab Chapter    A Calculus of Configs
NB. ====================================================
Lab Section A Calculus of Configs

We have seen that a config can contain the letters 
.NQxnq .  To merge two configs, we need to determine 
what letter should be the result for every combination 
of two letters.

.  free
N  N sits here
Q  Q sits here
x  under attack
n  Q here would attack N
q  N here would attack Q
)

NB. ====================================================
Lab Section

It is clear that "." (a free square) with any letter 
should result in that letter.  N (a knight on this 
square) with n (queen here would attack a knight) should 
be N, but N with anything other than "." or n should be 
?, an error.  

The combinations (n,q) or (q,n) merit some comment.
A queen can be placed on a q square but not on an n 
square, and a knight can be placed on an n square but 
not on a q square.  Therefore, a square that is both n 
and q is equivalent to an x square, "under attack", 
because no piece (neither queen nor knight) can be 
placed there.

The results for other combinations are derived 
similarly.

.  free                    .  N  Q  x  n  q
N  N sits here             N  ?  ?  ?  N  ?
Q  Q sits here             Q  ?  ?  ?  ?  Q
x  forbidden               x  ?  ?  x  x  x
n  Q here would attack N   n  N  ?  x  n  x
q  N here would attack Q   q  ?  Q  x  x  q
?  error
)

NB. ====================================================
Lab Section

The list MT records the ravelled operation table derived 
in the previous section.  The rows and columns are in 
the order .NQxnq .  Having MT, it is straightforward to 
write a verb that merges configs x and y :  index into 
MT using letters in x as row indices and letters in y as 
column indices.
)
MT    =: ' '-.~' .NQxnq N???N? Q????Q x??xxx nN?xnx q?Qxxq'
MTy   =: (%:#MT){.MT
MTx   =: (##])MTy
merge =: MT"_ {~ MTx&i.@[ + MTy&i.@]

(,~%:#MT) $ MT
(-: |:) (,~%:#MT) $ MT

(<n,n) $&.> x;y;x merge y
x (merge -: merge~) y

NB. ====================================================
Lab Section 

The table QT is an n*n row matrix of configs, one for
each possible placement of a queen.  The table NT is an
n*n row matrix of configs, one for each possible 
placement of a knight.
)
UI  =: >,{;~i.n
NI  =: _2]\_2 _1 _2 1 _1 _2 _1 2 1 _2 1 2 2 _1 2 1
QI  =: 0 0 -.~ (0&,. , ,.&0 , ,.~ , (,.|.)) i: n
mask=: 3 : 'UI e."2 UI +"1"1 2 y.'
QT  =: '.Qqx' {~ (=i.n*n)+(2*mask NI)+3*mask QI
NT  =: '.Nxn' {~ '.Qqx'i.QT

$ QT
$ NT

(<n,n) $&.> <"1 (16 17 18 19){QT
(<n,n) $&.> <"1 (16 17 18 19){NT

NB. ====================================================
Lab Chapter    Queens and Knights
NB. ====================================================
Lab Section Queens and Knights

With verb merge and tables QT and NT, the queens and 
knights problem is ready for solution.  

q1 applies to a table of configs and produces new
configs by placing one more queen in all possible ("." 
or q) squares.  Similarly, n1 applies to a table of 
configs and produces new configs by placing one more 
knight in all possible ("." or n) squares.

x qx y puts x additional queens on the configs y by
calling q1 x times, at each step removing configs with 
less than the required number of "." or q squares.
Similarly, x nx y puts x additional knights on the 
configs y.

qn y finds all solutions of putting y queens and y 
knights on a chessboard, starting from the table of the 
empty config ((1,n*n)$'.').  Since a queen attacks many 
more squares than a knight, thereby reducing many more 
possibilities, it is more efficient to place the queens 
first, then the knights.
)
q1=: 3 : '~.((+/"1 b)#y.) merge QT {~ (n*n)|I.,b=. y.e.''.q'''
n1=: 3 : '~.((+/"1 b)#y.) merge NT {~ (n*n)|I.,b=. y.e.''.n'''

qx=: 4 : 'for_j. (-i.)x. do. y.=. q1 y.#~j<:+/"1 y.e.''.q'' end.'
nx=: 4 : 'for_j. (-i.)x. do. y.=. n1 y.#~j<:+/"1 y.e.''.n'' end.'

qn=: 3 : 'y. nx y. qx (1,n*n)$''.'''

NB. ====================================================
Lab Section 
 
It is obviously not possible to place 8 queens and 8
knights, since 8 queens alone already attack the entire 
board.  We start with 7 queens and 7 knights and work
down from there.
)
# t=: qn 7
# t=: qn 6
# t=: qn 5

NB. ====================================================
Lab Section

That is, up to 5 queens and 5 knights can be place on an
8-by-8 chessboard, and there are 16 solutions.

The solutions can be displayed by mapping the letters Q 
and N to themselves and other letters to ".".  Boxing 
and reshaping make a pleasing display.
)
$t
{. t
(n,n) $ {. t

see=: ,~@%:@# $ 'QN'&i. { 'QN.'"_
see {. t
2 8 $ <@see"1 t

NB. ====================================================
Lab Chapter    Variants
NB. ====================================================
Lab Section Variants

Let s be one of the solutions as displayed in the 
previous section.  It is clear that reflections and
transpositions of s, and compositions thereof, are also 
solutions.
)
PREPARE
". (_1=4!:0 <'t')#'t=: qn 5'
PREPARE
s=: see {. t
(] ; |: ; |. ; |."1) s
NB. self ; transposition ; reflection 0 ; reflection 1

NB. ====================================================
Lab Section

var computes all reflectional and transpositional 
variants of a solution.  There can be up to 8 variants.
)
s

var=: ~.@(] , |:&.> , |.&.> , |."1&.>)^:3 
var <s

NB. ====================================================
Lab Section

To find the unique solutions with respect to reflections
and transpositions, we can proceed as follows:

- find all the variants of each solution;
- sort the variants;
- select the "smallest" of each set of variants;
- find the nub of these smallest variants.
)
uvar=: ~. @: ({.@(/:~)@var&>) @: (<@<@see"1)
uvar t

NB. ====================================================
Lab Chapter    Summary
NB. ====================================================
Lab Section Summary

In summary:

- At most 5 queens and 5 knights can be placed on an 
  8-by-8 chessboard so that no piece attacks another. 
- There are 16 different ways to place the 5 queens and
  5 knights.
- If reflectional and transpositional variants are 
  considered to be the same, then there are 2 different 
  ways to place the 5 queens and 5 knights. 
)

NB. ====================================================
Lab Section Summary

The following are the collected definitions for the
queens and knights problem.
)
NB.  .  free                    .  N  Q  x  n  q
NB.  N  N sits here             N  ?  ?  ?  N  ?
NB.  Q  Q sits here             Q  ?  ?  ?  ?  Q
NB.  x  forbidden               x  ?  ?  x  x  x
NB.  n  Q here would attack N   n  N  ?  x  n  x
NB.  q  N here would attack Q   q  ?  Q  x  x  q
NB.  ?  error

n    =: 8

MT   =: ' '-.~' .NQxnq N???N? Q????Q x??xxx nN?xnx q?Qxxq'
MTy  =: (%:#MT){.MT
MTx  =: (##])MTy
merge=: MT"_ {~ MTx&i.@[ + MTy&i.@]

UI   =: >,{;~i.n
NI   =: _2]\_2 _1 _2 1 _1 _2 _1 2 1 _2 1 2 2 _1 2 1
QI   =: 0 0 -.~ (0&,. , ,.&0 , ,.~ , (,.|.)) i: n
mask =: 3 : 'UI e."2 UI +"1"1 2 y.'
QT   =: '.Qqx' {~ (=i.n*n)+(2*mask NI)+3*mask QI
NT   =: '.Nxn' {~ '.Qqx'i.QT

q1   =: 3 : '~.((+/"1 b)#y.) merge QT {~ (n*n)|I.,b=. y.e.''.q'''
n1   =: 3 : '~.((+/"1 b)#y.) merge NT {~ (n*n)|I.,b=. y.e.''.n'''
qx   =: 4 : 'for_j. (-i.)x. do. y.=. q1 y.#~j<:+/"1 y.e.''.q'' end.'
nx   =: 4 : 'for_j. (-i.)x. do. y.=. n1 y.#~j<:+/"1 y.e.''.n'' end.'
qn   =: 3 : 'y. nx y. qx (1,n*n)$''.'''

see  =: ,~@%:@# $ 'QN'&i. { 'QN.'"_

var  =: ~.@(] , |:&.> , |.&.> , |."1&.>)^:3 
uvar =: ~. @: ({.@(/:~)@var&>) @: (<@<@see"1)
