queens and knights

[Roger|Dyalog]

The Problem

ITA Software was founded as a travel industry software company and is a division of Google since 2011. Its website often contained interesting programming puzzles. The “Queens and 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?

The n queens problem can be solved succinctly and efficiently. The queens and knights problem is considerably more difficult.

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.

a 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. q 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
      a← '....xqxq....qxxxxxxxxxQx....qxxx....xqxq...x..x...x...x..x....x.'
      (n,n) ⍴ a
....xqxq
....qxxx
xxxxxxQx
....qxxx
....xqxq
...x..x.
..x...x.
.x....x.

b 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.

      b← '.n.....n.n....n..n...n...n..n...xnxn....nnnx....nNnnnnnnnnnx....'
      (n,n) ⍴ b
.n.....n
.n....n.
.n...n..
.n..n...
xnxn....
nnnx....
nNnnnnnn
nnnx....

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 a (a Q on the (2,6) square) and b (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) ⍴¨ (⊂a),(⊂b),⊂'?'
┌────────┬────────┬────────┐
│....xqxq│.n.....n│????????│
│....qxxx│.n....n.│????????│
│xxxxxxQx│.n...n..│????????│
│....qxxx│.n..n...│????????│
│....xqxq│xnxn....│????????│
│...x..x.│nnnx....│????????│
│..x...x.│nNnnnnnn│????????│
│.x....x.│nnnx....│????????│
└────────┴────────┴────────┘

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

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 - under attack........... 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

The list MT records the ravelled operation table. The rows and columns are in the order .NQxnq. Having MT, it is straightforward to write a function that merges configs a and b: index into MT using letters in a as row indices and letters in b as column indices.

      ⍝
MT    ← ' ' ~⍨ ' .NQxnq N???N? Q????Q x??xxx nN?xnx q?Qxxq'
m     ← (≢MT)*0.5
MTy   ← m ↑ MT
MTx   ← m ⌿ MTy
merge ← {MT[(MTx⍳⍺)+(MTy⍳⍵)]}

      (m,m) ⍴ MT
.NQxnq
N???N?
Q????Q
x??xxx
nN?xnx
q?Qxxq

      (⊢ ≡ ⍉) (m,m) ⍴ MT
1
      (⊂n,n) ⍴¨ (⊂a), (⊂b), ⊂a merge b
┌────────┬────────┬────────┐
│....xqxq│.n.....n│.n..xqxx│
│....qxxx│.n....n.│.n..qxxx│
│xxxxxxQx│.n...n..│xxxxxxQx│
│....qxxx│.n..n...│.n..xxxx│
│....xqxq│xnxn....│xnxnxqxq│
│...x..x.│nnnx....│nnnx..x.│
│..x...x.│nNnnnnnn│nNxnnnxn│
│.x....x.│nnnx....│nxnx..x.│
└────────┴────────┴────────┘

      a (merge ≡ merge⍨) b
1

The table QT is an n×n row table of configs, one for each possible placement of a queen. The table NT is an n×n row table of configs, one for each possible placement of a knight.

      ⍝
UI   ← , ⍳ n,n
NI   ← ↓ 8 2 ⍴ ¯2 ¯1 ¯2 1 ¯1 ¯2 ¯1 2 1 ¯2 1 2 2 ¯1 2 1
QI   ← ↓ (t∨.≠0)⌿t← (0,t)⍪(t,0)⍪(t,t)⍪t,⊖t←⍪n-⍨⍳1+2×n
mask ← {UI∊⍤1 ⊢UI +⍤0 1 ⊢⍵}
QT   ← '.Qqx'[(∘.=⍨⍳n×n)+(2×mask NI)+3×mask QI]
NT   ← '.Nxn'['.Qqx'⍳QT]

      ⍴ QT
64 64
      ⍴ NT
64 64

      (⊂n,n) ⍴¨ ↓ QT[16 17 18 19;]
┌────────┬────────┬────────┬────────┐
│xqx.....│qxqx....│xqxqx...│.xqxqx..│
│xxq.....│xxxq....│qxxxq...│.qxxxq..│
│Qxxxxxxx│xQxxxxxx│xxQxxxxx│xxxQxxxx│
│xxq.....│xxxq....│qxxxq...│.qxxxq..│
│xqx.....│qxqx....│xqxqx...│.xqxqx..│
│x..x....│.x..x...│..x..x..│x..x..x.│
│x...x...│.x...x..│..x...x.│...x...x│
│x....x..│.x....x.│..x....x│...x....│
└────────┴────────┴────────┴────────┘
      (⊂n,n) ⍴¨ ↓ NT[16 17 18 19;]
┌────────┬────────┬────────┬────────┐
│nxn.....│xnxn....│nxnxn...│.nxnxn..│
│nnx.....│nnnx....│xnnnx...│.xnnnx..│
│Nnnnnnnn│nNnnnnnn│nnNnnnnn│nnnNnnnn│
│nnx.....│nnnx....│xnnnx...│.xnnnx..│
│nxn.....│xnxn....│nxnxn...│.nxnxn..│
│n..n....│.n..n...│..n..n..│n..n..n.│
│n...n...│.n...n..│..n...n.│...n...n│
│n....n..│.n....n.│..n....n│...n....│
└────────┴────────┴────────┴────────┘

Queens and Knights

With function 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.

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

qn ⍵ finds all solutions of putting ⍵ queens and ⍵ 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 ← {∪ ((+/b)⌿⍵) merge QT[(n×n)|⍸,b←⍵∊'.q';]}
n1 ← {∪ ((+/b)⌿⍵) merge NT[(n×n)|⍸,b←⍵∊'.n';]}
qx ← {0=⍺:⍵ ⋄ (⍺-1) ∇ q1 ⍵⌿⍨⍺≤+/⍵∊'.q'}
nx ← {0=⍺:⍵ ⋄ (⍺-1) ∇ n1 ⍵⌿⍨⍺≤+/⍵∊'.n'}
qn ← {⍵ nx ⍵ qx (1,n×n)⍴'.'}

On an 8-by-8 board, it is obviously not possible to place m queens and m knights for m≥6, since m queens alone that do not attack each other necessarily attack m rows and m columns, leaving at most (n-m)×(n-m) free squares. (For n=8 and m=6, there would be at most 4=2×2 free squares.) We start with 5 queens and 5 knights.

      ≢ t← qn 5
16
      ≢ qn 8    ⍝ just checking!
0
      ≢ qn 7
0
      ≢ qn 6
0

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
16 64

      (n,n) ⍴ t[0;]
xQxxxxxx
xxxxxxQx
xxQxxxxx
xxxxxQxx
xxxxxxxQ
Nxxxxxxx
NxxNNxxx
xxxNxxxx
      see← {(n,n) ⍴ 'QN.'['QN'⍳⍵]}
      see t[0;]
.Q......
......Q.
..Q.....
.....Q..
.......Q
N.......
N..NN...
...N....
      2 8 ⍴ see¨ ↓t
┌────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
│.Q......│..Q.....│..Q.....│...Q....│....Q...│.....Q..│.....Q..│......Q.│
│......Q.│.....Q..│.....Q..│......Q.│.Q......│..Q.....│..Q.....│.Q......│
│..Q.....│.Q......│.......Q│....Q...│...Q....│Q.......│......Q.│.....Q..│
│.....Q..│......Q.│N.......│.N......│......N.│.......N│.Q......│..Q.....│
│.......Q│........│NN......│NN......│......NN│......NN│........│Q.......│
│N.......│Q.......│......Q.│.....Q..│..Q.....│.Q......│.......Q│.......N│
│N..NN...│....N..N│....Q...│.......Q│Q.......│...Q....│N..N....│...NN..N│
│...N....│...NN..N│NN......│.NN.....│.....NN.│......NN│N..NN...│....N...│
├────────┼────────┼────────┼────────┼────────┼────────┼────────┼────────┤
│.....NN.│......NN│NN......│.NN.....│...NN..N│N..NN...│....N...│...N....│
│Q.......│...Q....│....Q...│.......Q│....N..N│N..N....│...NN..N│N..NN...│
│..Q.....│.Q......│......Q.│.....Q..│Q.......│.......Q│.......N│N.......│
│......NN│......NN│NN......│NN......│........│........│Q.......│.......Q│
│......N.│.......N│N.......│.N......│......Q.│.Q......│..Q.....│.....Q..│
│...Q....│Q.......│.......Q│....Q...│.Q......│......Q.│.....Q..│..Q.....│
│.Q......│..Q.....│.....Q..│......Q.│.....Q..│..Q.....│.Q......│......Q.│
│....Q...│.....Q..│..Q.....│...Q....│..Q.....│.....Q..│......Q.│.Q......│
└────────┴────────┴────────┴────────┴────────┴────────┴────────┴────────┘

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.

      s← see t[0;]
      (⊢ ⍪ ⍉¨ ⍪ ⊖¨ ⍪ ⌽¨) ⊂s
┌────────┬────────┬────────┬────────┐
│.Q......│.....NN.│...N....│......Q.│
│......Q.│Q.......│N..NN...│.Q......│
│..Q.....│..Q.....│N.......│.....Q..│
│.....Q..│......NN│.......Q│..Q.....│
│.......Q│......N.│.....Q..│Q.......│
│N.......│...Q....│..Q.....│.......N│
│N..NN...│.Q......│......Q.│...NN..N│
│...N....│....Q...│.Q......│....N...│
└────────┴────────┴────────┴────────┘
      ⍝ self ; transposition ; reflection 0 ; reflection 1

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

      var ← (∪ ⊢ ⍪ ⍉¨ ⍪ ⊖¨ ⍪ ⌽¨)⍣3
      var ⊂s
┌────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
│.Q......│.....NN.│...N....│......Q.│.NN.....│....Q...│....N...│...Q....│
│......Q.│Q.......│N..NN...│.Q......│.......Q│.Q......│...NN..N│......Q.│
│..Q.....│..Q.....│N.......│.....Q..│.....Q..│...Q....│.......N│....Q...│
│.....Q..│......NN│.......Q│..Q.....│NN......│......N.│Q.......│.N......│
│.......Q│......N.│.....Q..│Q.......│.N......│......NN│..Q.....│NN......│
│N.......│...Q....│..Q.....│.......N│....Q...│..Q.....│.....Q..│.....Q..│
│N..NN...│.Q......│......Q.│...NN..N│......Q.│Q.......│.Q......│.......Q│
│...N....│....Q...│.Q......│....N...│...Q....│.....NN.│......Q.│.NN.....│
└────────┴────────┴────────┴────────┴────────┴────────┴────────┴────────┘

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

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.

Collected Definitions

      . - free................... .  N  Q  x  n  q
      N - N sits here............ N  ?  ?  ?  N  ?
      Q - Q sits here............ Q  ?  ?  ?  ?  Q
      x - under attack........... 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

      ⍝
n     ← 8

MT    ← ' ' ~⍨ ' .NQxnq N???N? Q????Q x??xxx nN?xnx q?Qxxq'
m     ← (≢MT)*0.5
MTy   ← m ↑ MT
MTx   ← m ⌿ MTy
merge ← {MT[(MTx⍳⍺)+(MTy⍳⍵)]}

UI    ← , ⍳ n,n
NI    ← ↓ 8 2 ⍴ ¯2 ¯1 ¯2 1 ¯1 ¯2 ¯1 2 1 ¯2 1 2 2 ¯1 2 1
QI    ← ↓ (t∨.≠0)⌿t← (0,t)⍪(t,0)⍪(t,t)⍪t,⊖t←⍪n-⍨⍳1+2×n
mask  ← {UI∊⍤1 ⊢UI +⍤0 1 ⊢⍵}
QT    ← '.Qqx'[(∘.=⍨⍳n×n)+(2×mask NI)+3×mask QI]
NT    ← '.Nxn'['.Qqx'⍳QT]

q1    ← {∪ ((+/b)⌿⍵) merge QT[(n×n)|⍸,b←⍵∊'.q';]}
n1    ← {∪ ((+/b)⌿⍵) merge NT[(n×n)|⍸,b←⍵∊'.n';]}
qx    ← {0=⍺:⍵ ⋄ (⍺-1) ∇ q1 ⍵⌿⍨⍺≤+/⍵∊'.q'}
nx    ← {0=⍺:⍵ ⋄ (⍺-1) ∇ n1 ⍵⌿⍨⍺≤+/⍵∊'.n'}
qn    ← {⍵ nx ⍵ qx (1,n×n)⍴'.'}

see   ← {(n,n) ⍴ 'QN.'['QN'⍳⍵]}

var   ← (∪ ⊢ ⍪ ⍉¨ ⍪ ⊖¨ ⍪ ⌽¨)⍣3
uvar  ← {∪ ⊃∘{(⊂⍋⍵)⌷⍵}∘var¨ ⊂∘⊂∘see⍤1 ⊢⍵}

Substantially the same text in J appeared as Queens and Knights in a J Wiki Essay and in Vector, volume 21, number 3, summer 2005.

[Roger|Dyalog]

The code developed above can solve the 8 queens problem: add 8 queens to the empty config (1,n×n)⍴'.' (There are more efficient solutions.)

      ⍴ t← 8 qx (1,n×n)⍴'.'
92 64
      ⍴ uvar t    ⍝ unique WRT transpositions and rotations
12
      2 6 ⍴ uvar t
┌────────┬────────┬────────┬────────┬────────┬────────┐
│.......Q│.......Q│......Q.│......Q.│......Q.│......Q.│
│...Q....│..Q.....│....Q...│...Q....│...Q....│..Q.....│
│Q.......│Q.......│..Q.....│.Q......│.Q......│.......Q│
│..Q.....│.....Q..│Q.......│.......Q│....Q...│.Q......│
│.....Q..│.Q......│.....Q..│.....Q..│.......Q│....Q...│
│.Q......│....Q...│.......Q│Q.......│Q.......│Q.......│
│......Q.│......Q.│.Q......│..Q.....│..Q.....│.....Q..│
│....Q...│...Q....│...Q....│....Q...│.....Q..│...Q....│
├────────┼────────┼────────┼────────┼────────┼────────┤
│......Q.│......Q.│......Q.│.....Q..│.....Q..│.....Q..│
│..Q.....│.Q......│.Q......│...Q....│...Q....│..Q.....│
│Q.......│.....Q..│...Q....│......Q.│Q.......│......Q.│
│.....Q..│..Q.....│Q.......│Q.......│....Q...│...Q....│
│.......Q│Q.......│.......Q│.......Q│.......Q│Q.......│
│....Q...│...Q....│....Q...│.Q......│.Q......│.......Q│
│.Q......│.......Q│..Q.....│....Q...│......Q.│.Q......│
│...Q....│....Q...│.....Q..│..Q.....│..Q.....│....Q...│
└────────┴────────┴────────┴────────┴────────┴────────┘