The **n-queens problem** is a generalization of the 8-queens prob...
Fermat's theorem on sums of two squares says that an odd prime $p$ ...
The set of all integers which have the same remainder when divided ...
the only symmetrical solution!
This result is not obvious, particularly for someone without any kn...
Since we are going to place n queens in an nxn board, every queen n...
For the example in Figure 1, since $n=13$ if we choose $r=2$, $(13,...
Note that $(n,c) + \langle (1,d) \rangle $ generates positions of t...
As seen before two numbers a and b are relatively prime if and only...
$(p,c)+ \langle(1, d)\rangle = (p + i, c+ id)$ where $i=1,2,...,n$....
If $d=p$, d is obviously not relatively prime to p.
If $d=p-1$, ...
A
Theorem
about Primes
Proved on
a Chessboard
An
elementary treatment
of
a
class of solutions to
the
n-queens problem leads to a
proof of Fermat's
theorem on
primes
which
are
sums
of
two squares.
LOREN C. LARSON
St.
Olaf College
Arrange queens
on a 13
x
13
chessboard according to the following rule: place a queen on the
center
square
and from it
locate others
by making successive (2, 3) movements
-
two squares to the
right
and
three
squares
upward (top and bottom edges are identified, as well as right and left). The
resulting queen placement
(FIGURE 1) shows exactly one queen
in
each row and column, and no two on
the
same
diagonal;
as
such,
it
is
a
solution
to the
n-queens problem (to place n nonattacking queens
on
the
n
x
n
chessboard)
for
n
=
13. The
solution
is
distinguished
from other solutions
in
two
respects: (i)
it is
regular,
meaning
that the
queens
are
located at successive
(s, t)
movements
from each
other,
for
some
integers
s and
t
(a
more
precise
definition
will
be
given later),
and
(ii)
it
is
doubly
symmetric, meaning
that it is invariant under a 900
rotation of
the
board
about the center
square.
More
generally, suppose
that u and
v
are
positive integers
and
u2+ v2 is
an odd
prime p.
We will
show
that
queens
located at
successive
(u, v)
movements from
a
queen
on the center
square
of
the
p
x
p chessboard give a
regular, doubly symmetric solution to the p-queens problem. Conversely, we
will see
that regular,
doubly symmetric
solutions
to
the
p-queens problem,
for
p
a
prime, yield
positive integers
u
and v such that
u2+ v2
=p.
In the
final section
we will show
by
a
simple
combinatorial
argument
that there
is
a
regular, doubly symmetric
solution to the
p-queens problem
whenever p is a prime of the
form
4k
+
1. Combining
this result with
the
preceding implication gives
a
proof
of Fermat's
Two-Square
Theorem:
primes of
the
form
4k
+
1 can be
expressed
as the sum
of
two
squares.
This
proof
of
Fermat's theorem
is
both
elementary
and concrete.
It
avoids the
usual first
step
of
knowing
that
-
1 is
a
quadratic
residue modulo
p
when
p
is
a
prime
of
the
form
4k
+
1.
Moreover
it
uses
the
chessboard to
provide
a
specific geometrical setting
for
illustrating
and
interpreting
abstract
concepts usually
first
encountered
in
an
introductory
abstract
algebra
course. The ideas on
which this
approach
is
based are
scattered
throughout
references
[1]
and
[2].
The
chief
insight
-
relating
Fermat's
Two-Square
Theorem to the n-queens problem
-
is due to George Polya.
This content downloaded from 129.128.216.34 on Wed, 13 Nov 2013 15:26:47 PM
All use subject to JSTOR Terms and Conditions
Preliminaries
The additive group of integers
will
be denoted
by Z, and
Z,,
=
{1
2,
3, .. .,
n} will denote the
cyclic
group of order
n, having the
operation of addition
modulo
n. If x is an integer,
[x] will denote
that
integer
between 1 and
n
inclusive
which
is
congruent
to x
modulo n. (Since
we will be working
on an
n
x
n
chessboard,
there will be no need to
write
[x],n
to indicate
the modulus.)
There is little danger
of
confusion
in
using [x]
to
denote
an element
of
Z
and
also
an element of
Zn,
for the context will
make
the
intention clear.
For convenience
we will identify
the chessboard
with the
group Zn
x
Zn.
Geometrically, the
group
element (i,j)
represents
the square
in
the
ith column (from
the left) and
the jth row (from
the
bottom).
A
regular
solution to
the
n-queens
problem
is
a
solution
in
which the
queens
are located on
the
squares
(represented by
the
elements)
of
the
coset (a, b)
+
((s, t))
for some (a, b), (s, t)
E Zn
x
Zn
where ((s, t))
is the cyclic subgroup
of
Zn
x
Zn generated
by (s, t). In this
case, we will
say that
(a, b)
+
((s,
t))
is
a regular
solution.
FIGURE
1
It
is
important
to
observe that
every
regular
solution can
be
expressed
in
the form
(n,
c)
+
((1,
d))
for
some
c,
d
E
Z,n.
For,
suppose
that
(a,
b)
+
((s,
t))
is
a
regular
solution.
We
know
that k
(s, t)
is
a
generator
of
((s, t))
whenever k
is
an
integer
relatively
prime
to n.
(Geometrically,
the solution
can
be
generated
by
many
different
regular
movements.)
Since s
must
be
relatively
prime
to
n in
order
that
each column
be
occupied
(similarly
for
t and
the
rows),
there exists an
integer
r,
relatively
prime
to
n,
such
that rs
1
(mod n).
For
this
r,
r(s, t)
is
of the form
(1,
d)
for some d
E
Z,n.
Thus
(
(s, t))=
(r(s,
t))
=
((1, d)).
Since
a
queen
occurs
in
column
n,
we
have,
for -some
c
E
Zn,
(n,
c)
E
(a,
b)
+
((s,
t)),
or
equivalently,
(n,
c)
E
(a, b)
+
((1,
d)).
It
follows, then,
that
(a,
b)
?
((s,
t))
=
(n,
c)
?
((1, d)).
(For
the
example
in
the
introduction,
c
=3 and
d
=
8.)
70~ IIIII
x
This content downloaded from 129.128.216.34 on Wed, 13 Nov 2013 15:26:47 PM
All use subject to JSTOR Terms and Conditions
We are interested
in
finding
conditions on c and d so that
(n, c)
+
((1, d))
will be
a solution
to
the
n-queens problem.
It
is
easy
to see that a
necessary
condition is that d be
relatively prime
to n
(so that
each row
be
occupied);
but this
is
not
sufficient, since,
for
ex`ample, d
= 1
violates the
diagonal
requirements.
Notice that two
queens
lie
on the same
rising
diagonal (diagonals having slope 1)
if
the
differences
(in Z)
of their coordinates are
the
same,
and on the same
falling diagonal
if
the sums
(in
Z)
of their coordinates are
equal.
For the coset
above, queens
are located on
the
squares (i, [c
+
id])
for
i
=
1, 2,...,
n.
Since i
+
[c
+
id]
c
+
i(d
+
1) (mod n),
the sums of these coordinates
will
be
different
provided that d
+
1 is
relatively prime
to n.
Similarly,
since
[c
+
id]
-
i
c
+
i(d
-
1) (mod n),
the
differences
will
be distinct
if d - 1 is
relatively prime to
n.
Thus,
a sufficient
condition for
(n, c)
+
((1, d))
to
be
a
solution
is
that d
-
1,
d
and
d
+
1 each
be
relatively prime
to n. We leave it as
an exercise to
prove
that
this condition
is
also
necessary.
(Warning:
this converse is not immediate
since two of the
coordinate
sums
(differences) may
be
equal
in
4,
but
unequal
in
Z.)
We
summarize
the
preceding discussion
in
the
following
formal
lemma:
FUNDAMENTAL
LEMMA.
The
placement (n, c)
+
((1, d))
is
a solution to the
n-queens problem if
and
only if
d
-
1,
d and
d
+ 1
are each
relatively prime
to n.
An immediate
corollary helps explain why
the
8-queeens
problem
is
so much more
difficult than
the
7-queens problem,
which most
beginners
solve
very
quickly.
We
will
state and
prove
it
here,
even
though
we
will
not need
it
(nor,
for that
matter,
the
"only
if"
part
of the Fundamental
Lemma)
for the
main
result
of
the
paper.
COROLLARY.
There
exists a
regular
solution
to
the
n-queens
problem if
and
only if
n ?
1
(mod
6).
Proof
We have seen
that
regular
solutions
have
the
form
(n, c)+((I, d))
for some
c and
d. If
n
+ 1
(mod 6) we
get a regular solution by taking
d
=
2
(ordinary knight moves).
However,
for
n
0,
2, 3,
4
(mod 6)
we
cannot have
regular
solutions since one of
d
-
1, d,
d
+
1
is
divisible
by
3
and
at
least
one of
them
is
even.
From Number
Theory
to the
Chessboard
Suppose
that
p
is
an
odd
prime
number
and
that
u
and
v are
positive integers
such that
u2
+
v2=
p. Choose
an
integer
r
so that
r(u, v)
=
(1, d)
for some
d
E
Z,.
Then
r2u2+ r2v2
=
r2p,
12+
d2
0
(mod p)
and therefore
d2-
1(mod p).
Thus
(d
+
1)(d
-
1)d21
- 2
(mod
p).
It
follows
that d
-
1,
d and d
+
1
are each
relatively prime
to
p
and
therefore
(1, d)
movements
will
generate
a
regular
solution. The
center
square
has coordinates
((p
+
1)/2, (p
+
1)/2),
so
in
order that
(p, c)
+
((1, d))
have a
queen
on
the center
square,
it
is
necessary
and sufficient that
c
+
( ) d
(mod
p)
or
(1) 2c+d
1
(modp).
Suppose
that c is so
determined. Now
under a 900
clockwise rotation, the queen located
on the
square (i, [c
+
id])
will
rotate
to
the square ([c
+
id], [1
-
iJ).
But this square is occupied by a
queen in
(p, c)+((1, d)),
since
[c
+
[c
+
id]d]
=
[c
+
cd
+
id2]
=
[c(1
+
d)-
il
=
[(1- d)12)(1
+
d)-
i=
[(1
-
d2)/2)-
il
=
[1
-
il.
Therefore the
solution
is
doubly
symmetric.
From
the Chessboard
to
Number
Theory
Suppose
now
that
p
is
a
prime
and
that
(p, c)
+
((1, d))
is
a
regular, doubly symmetric
solution to
the
p-queens problem.
Since
the
2
x
2
board does not
admit such a solution, the prime p is
odd.
Observe that a
queen
is located on the center
square,
since
queens
off the
center come in sets of
four,
VOL. 50, NO.
2, MARCH 1977
71
This content downloaded from 129.128.216.34 on Wed, 13 Nov 2013 15:26:47 PM
All use subject to JSTOR Terms and Conditions
these located
at
quarter
turns
from each other (rotational symmetry). (Incidentally, this
shows that p
has the form 4k
+
1.)
From among all the queens on the board, pick one that is closest to the queen on the
center square;
suppose it is located at a (u, v) movement from the center square. Because of rotational
symmetry we
may suppose
that
u
and
v
are
positive. (Other closest queens
will
be
located at (v,
-
u), (- u,
-
v),
and
(- v, u) movements
from the center
square.)
Because the solution
is
regular,
no two queens can
be located closer together than these two queens. (To get from one queen to another
requires an
i(l, d)
E
Zp
X
Zp
movement
for some
integer i,
and this
same movement
could
be
made from the
center
square.)
The
center queen
and the two
queens
located at
(u, v)
and
(v,
-
u) movements
from it, occupy
three vertices
of
a
square region;
the fourth vertex of
this
square
is
occupied by
a
queen
in
the solution
since
it is
a
(u, v)
+
(v,
-
u)
E
Zp
x
Zp
movement from the center (and each summand
is a multiple of
a
(1, d) movement). Furthermore,
no
queen
in
the solution
will
be located
in the interior
of
this
square (since
that
would
violate our choice of
u
and
v).
In
the same way, every queen
on the board
can
be associated with
a
square region
whose vertices are
given by
its
own
position
and
those
queens
at
(u, v), (v,
-
u)
and
(u, v)
+
(v,
-
u)
movements from
it.
It
is
understood
that
left
and
right, top
and
bottom
edges
are
identified,
so that
squares
which
overlap
an
edge
are continued
on
the
opposite
side
(see
FIGURE
2).
In
this
way the p
x
p chessboard
is
dissected
into
p regions (one
for
each
queen) each
of
equal
area.
Since
the total area of the
chessboard
is p2,
each
individual
square
has an area
equal
to
p. It
follows that the
side length of
each
square
is
\/p,
and
therefore,
from the
Pythagorean
theorem,
that
p
= u2+
V2.
FIGURE
2
72 MAHMTC
MAGAZIN
This content downloaded from 129.128.216.34 on Wed, 13 Nov 2013 15:26:47 PM
All use subject to JSTOR Terms and Conditions
It may be instructive to point out that the
queen positions
in
a
regular
solution are
part
of a lattice
that
extends to
the
entire
plane.
This can be seen
algebraically by
first
observing
that the
mapping
k:
Z
x
Z
->
Z
x
Zn
defined
by ((x, y))4
=
([x], [y])
is a
group homomorphism.
Let H
be the
cyclic
subgroup
of
Z x Z
generated by
(u, v).
Then the elements of
(HO)4f`
may
be
interpreted
geometrically
as the
positions
of the
queens
obtained
by tiling
the entire
plane
with
copies
of
the
chessboard having queens
located
on
the
squares
Ho.
However,
(HO)O`
is a
subgroup of Z
x
Z, and
therefore it
is a lattice of dimension
two, having
a fundamental
region
of area
equal
to the
absolute
value of the determinant of the matrix
gotten by expressing the lattice basis in terms of
the canonical
basis
of Z
x
Z. Now
an
arbitrary regular
solution
to the
n-queens problem
is
a
translation
of
Ho
for
some cyclic group
H
of
Z
x
Z,
and
this
corresponds
to
the
same
translation
in Z
x
Z
of the
subgroup
(H4)f
'.
Fermat's Two Square
Theorem
In
order to prove Fermat's
result,
we need to show that there
is
a
regular,
doubly symmetric
solution
to
the p-queens problem
whenever
p
is
a
prime
of the form
4k
+
1. To do
this,
we
will
count
the
total
number
of
regular
solutions
for the
p
x
p
board
in
two different
ways.
LEMMA. The number of regular solutions
to
the
p-queens problem,
where
p
is a
prime,
is
p(p
-
3).
Proof. We know that regular solutions have the form
(p, c)
+
((1, d)). Clearly
we do not
get
a
solution
when d
is
p, p
-
1,
or 1. But
any
of
the
other
p
-
3
possibilities
for
d,
in
Zp,
will
produce
regular solutions,
since in these cases
d
-
1, d,
and
d
+
1 will
each be
relatively prime
to
p.
Since
c can
take
on
any
of
p values,
the total number of
regular
solutions
is
p(p
-
3).
A
second
way
of
counting
the
regular
solutions
is
to
partition
them into three
classes, depending
upon
their
symmetry
-
doubly
symmetric, symmetric (invariant
under
a
1800 rotation but not a 900
rotation),
or
nonsymmetric (no
symmetry).
The
symmetries
of the
square
consist of
four reflections
and four
rotations,
and these form
a
group G,
under
composition.
If x
denotes a
regular
solution and
U
E G,
the
regular
solution which results from
x
by applying
the
transformation
U will be denoted
by
xU.
Two
regular
solutions
x
and
y
are
essentially
the
same
if and
only
if
there exists
a
U
E
G such that
xU
=
y.
This is an
equivalence
relation
on the set of all
regular
solutions. The
equivalence
class
of a
solution x consists of all those
solutions
that can be
obtained
from
x
by
rotation
and
reflection. For
each
regular
solution
x,
let
HI-
denote the set of
all
symmetries
of
x;
that
is,
HI
=
{U
E
G
I
xU
=
x}.
HI-
is a
subgroup
of
G.
Furthermore,
if
U,
V
E
G,
xU
=
xV
if
and
only
if
xUV-
=
x,
and
this
happens
if and
only
if
UV-
E
HI-.
It
follows that the number of elements in the
equivalence
class
of
x is
equal
to the index of
HI-
in
G,
and
this
is
2, 4,
or 8
depending upon
whether
x
is
doubly symmetric,
symmetric,
or
nonsymmetric
respectively.
Thus
we
have
the
following
lemma:
LEMMA. The number of regular
solutions to the n-queens problem is 2x
+
4y
+
8z,
where x, y, z are,
respectively,
the number
of essentially
different doubly symmetric, symmetric, and nonsymmetric
regular
solutions to the
n-queens problem.
Now
suppose
that
p
is a
prime
of the
form
4k
+
1.
Combining
the results
of the
preceding
two
lemmas,
we know
that
p(p -3)
=
2x
+
4y
+
8z.
Since,
in this
equation, p
1
(mod
4),
it
becomes
2
2x
(mod 4).
But
this
completes the
proof,
since
this
last
equation implies that x, the number of
essentially
different
regular, doubly
symmetric solutions,
is
not zero.
Finally, we can show that the
positive integers u and v in Fermat's result are unique.
To do this, it
is
sufficient to
prove that
there
are
only two regular, doubly symmetric solutions to the
p-queens
problem
-
a
single solution, and its
horizontal reflection, both of which induce the
same positive
integers
u
and v
for
which
u2
+
v2
=
p.
So, suppose
that
(p, c)
+
((1, d))
is
a
regular,
doubly symmetric
solution
to the
p-queens problem. Since
a
queen
is
located
on
the square (1, [c
+
d]), there must also
be
(by
rotational
symmetry)
a
queen
on the square ([c
+
d], p). This means that
VOL. 50, NO. 2, MARCH 1977
73
This content downloaded from 129.128.216.34 on Wed, 13 Nov 2013 15:26:47 PM
All use subject to JSTOR Terms and Conditions
(2)
c+[c+d]d-p
(mod
p).
The
fact that
the center
square
is occupied
means that
(1) holds, so that we may substitute
c
(1
-
d)12
from
(1)
into (2)
to get
(2 d)+(
2
d)
p
(mod
p)
which
simplifies
to
(3)
d2+ 1
O
(mod p).
Thus d satisfies
x2 + 1 = 0
over
the field
Zp. Alternatively,
if we substitute
d 1
-
2c from (1) into (2)
we see
that c
must satisfy
x2
+
(x
-
1)2
=
0
over Zp.
Thus the existence of a regular, doubly symmetric
solution
to the
p queens
problem,
for p
a prime
of the form
4k
+
1, also implies
the
existence of
two
solutions
to each
of the
equations
x2+ 1 =
0
and
x2+ (x
- 1)2 =
0
in 4. Since
Zp
is a field,
these
second order
polynomial
equations
can
have only
two solutions
in
Zp, which implies that there can be
only
two possible
values
for d and
c. But
once one
of these
values is known, so is the other by equation
(1), proving
that
there are at most two
regular, doubly
symmetric
solutions
to the p-queens
problem
when
p
is
a
prime.
In
conclusion,
we
note
that
these
latter equations
offer an alternative, albeit less elegant,
procedure
for
proving
the existence
of
a
regular,
doubly symmetric
solution
to the p-queens problem
for
p
a
prime
of the form 4k
+
1; simply
choose d
by (3)
and c by (1)
and apply the argument following
equation
(1).
References
[1]
Maurice Kraitchik,
La
Mathematique des Jeux
ou
Recreations
Mathematiques, Chapter XIII,
Le
Probleme
des Reines,
Bruxelles, 1930, pp. 300-356.
[2] G. Polya, Uber die
"doppelt-periodischen" Losupgen des
n-Damen Problems,
Mathematische
Unterhal-
tungen und Spiele,
Dr. W. Ahrens. Zweiter Band, B. G.
Teubner, Leipzig, 1918, pp. 363-374.
Proof
without
words:
Cubes and squares
12 3
4
5
6
7
r rLl- J . BARRY
LOVE
s _ _ ~~~I I
I
111
1__11 :T
Naioa
LibertyCH
i Corp.110 -
13~
~~
~~~~~~~~
3r
3
I
3
5
I -F
I1I_TEI-_
Va
1,1
lle
Foge
Penn.
_I _
7T+M2+M3+
+
n)2
_ _ 7 __N
-J.
BARRY
LOVE
National
Liberty Corp.
Valley Forge,
Penn.
74
MATHEMATICS
MAGAZINE
This content downloaded from 129.128.216.34 on Wed, 13 Nov 2013 15:26:47 PM
All use subject to JSTOR Terms and Conditions
the only symmetrical solution!
Tony it is indeed a symmetric solution but it's not unique. As we discuss at the end of page 73, the number of regular solutions for p=13 is $p(p-3)= 130$, including many symmetric solutions (both doubly symmetric - invariant under 90 degree rotations - and just symmetric - invariant under 180 degree rotations ).
If $d=p$, d is obviously not relatively prime to p.
If $d=p-1$, $d+1=p$ is obviously not relatively prime to p.
And finally if $d=1$, as we have seen above in page 71, we violate the diagonal requirements.
$(p,c)+ \langle(1, d)\rangle = (p + i, c+ id)$ where $i=1,2,...,n$. If we want to have a queen in the center position we end up with two equations for the coordinates
$$
p+i = \frac{p+1}{2} \leftrightarrow p+2i = 1 \leftrightarrow 2i \equiv 1 \text{(mod p)} \\
c+id = \frac{p+1}{2} \leftrightarrow 2c + 2id = p+1 \leftrightarrow 2c+2id \equiv 1 \text{(mod p)}
$$
Combining the two equations
$$
2c+d \equiv 1 \text{(mod p)}
$$
As seen before two numbers a and b are relatively prime if and only if there exists an integer y such that by ≡ 1 (mod a).
For d:
$d^2 \equiv - 1 \leftrightarrow d(-d) \equiv 1 \text{(mod p)} $
and so $y = -d$
For d +1 :
$(d+1)(d-1) \equiv -2 \leftrightarrow (d+1)\frac{d-1}{-2} \equiv 1 \text{(mod p)} $
and so $y = \frac{d-1}{-2}$
Finally for d -1 :
$(d+1)(d-1) \equiv -2 \leftrightarrow (d-1)\frac{d+1}{-2} \equiv 1 \text{(mod p)} $
and so $y = \frac{d+1}{-2}$
For the example in Figure 1, since $n=13$ if we choose $r=2$, $(13,3) + \langle (1,8) \rangle$ gives:
$$
(13,3)+(2,3)=(2,6) \\
(13,3)+(4,6)= (4,9)\\
(13,3)+(6,9)=(6,12)\\
(13,3)+(8,12)= (8,2)\\
(13,3)+(10,2)= (10,5)\\
(13,3)+(12,5)= (12,8)\\
(13,3)+(1,8)= (1,11)\\
(13,3)+(3,11)= (3,1)\\
(13,3)+(5,1)= (5,4)\\
(13,3)+(7,4)= (7,7)\\
(13,3)+(9,7)= (9,10)\\
(13,3)+(11,10)= (11,13)\\
(13,3)+(13,13)= (13,3)\\
$$
If you check the positions generated above are exactly the solution for the 13-queens problem in Figure 1.
Fermat's theorem on sums of two squares says that an odd prime $p$ is expressible as
$$p = x^2 + y^2$$
with $x$ and $y$ integers, if and only if
$$
p \equiv 1 \pmod{4}
$$
which is the same thing as saying if and only if $p=4k+1$, where $k \in \mathbb{N}$.
The prime numbers for which this is true are called Pythagorean primes.
For example, the primes 5, 13, 17, 29, 37 and 41 are all congruent to 1 modulo 4, and they can be expressed as sums of two squares in the following ways:
$$
5 = 1^2 + 2^2 \\
\quad 13 = 2^2 + 3^2\\
\quad 17 = 1^2 + 4^2
$$
A one-sentence proof of Fermat's theorem on sums of two squares has already been discussed on [Fermat's Library](http://fermatslibrary.com/p/eea4212e).
This result is not obvious, particularly for someone without any knowledge of group theory.
I'll give a motivation of why this might be true by showing an example for $\bar Z_6 $.
In $\bar Z_6 = \{1, 2, 3, 4, 5,6\}$, the generators of $\bar Z_6$ are the integers
$k$ between 1 and 6 such that gcd (6, k) = 1 (in other words 6 and k are relatively primes) that is 1, 5. We can verify that, $\langle 1\rangle = \{1, 2, 3, 4, 5,6\}$ and $\langle 5\rangle = \{5, 4, 3,2,1,6\} = \{1, 2, 3, 4, 5,6\}$ but $\langle 6\rangle = \{6\}$, $\langle 3\rangle = \{3,6\}$, $\langle 4\rangle = \{4,2,6\}$, $\langle 2\rangle = \{2,4,6\}$.
If you want to see a proof of this theorem you can go [here](https://www.math.lsu.edu/~adkins/m4201/cyclicgroup.pdf).
Since we are going to place n queens in an nxn board, every queen needs to be in a different column, otherwise at least two of the queens would be attacking each other. This means that $s$ has to be able to "generate" all the different possibilities for the columns: {1,2,...,n}.
As we have seen before, for $s \in \bar Z_n$, $s$ is a generator of $\bar Z_n$ if and only if n and s are relatively prime. We conclude that s and n need to be relatively prime!
At the same time, according to the [Bézout's identity](https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity), for 2 numbers n and s that are relatively prime there exist integers r and y such that $rs + yn = 1 \leftrightarrow rs\equiv 1 \text{ (mod n)} $.
The **n-queens problem** is a generalization of the 8-queens problem published by chess composer Max Bezzel in 1848. Max Bezzel, whose main occupation was creating chess problems, challenged people to find a way to place 8 non-attacking queens on an 8x8 chessboard.
Franz Nauck was the first person to publish solutions to the 8-queens problem in 1850 and also generalized the puzzle to the n-queens problem.
Many famous mathematicians including Gauss and Dijkstra worked on the problem and proposed various methods to find solutions.
These days the 8-queens problem is most often encountered as an exercise in introductory artificial intelligence programming courses. In fact, the n-queens problem is one of the benchmarks by which backtracking algorithms have been compared.
This reminds me of a boardgame, played with 8 queens on a chess board, that was part of the National Mathematical Games Championship when I was in high school (in Portugal). It's called Game of the Amazons [1], and each player owns 4 queens. They take turns moving one of their queens to a valid position and then placing a stone within "sight" of this queen. Stones block cells and the first player to not be able to move any of his queens loses. Quite dynamic, and fun to devise successful strategies.
Again, cool paper!
[1] https://en.wikipedia.org/wiki/Game_of_the_Amazons
Note that $(n,c) + \langle (1,d) \rangle $ generates positions of the form $(n+i,c+id)$. Since $n+i$ is equal to $i$ (mod n), the positions of the queens can be written as $(i,c+id)$. $n$ is the size of the chessboard, so if we add $i$ and $n$ we will just be looping back to the original position $i$
The set of all integers which have the same remainder when divided by $q$ is called the $\textbf{congruence class}$ of a modulo $q$. The collection of all congruence classes modulo q is called the $\textbf{set of integers modulo q}$, denoted by $\bar Z_q$
For instance, the set of integers modulo 3 $\bar Z_3$ has three elements which we will call {$\bar1,\bar2,\bar3$}. Don't confuse these elements with the regular integers 1,2,3. As an example, $\bar 2$ denotes the set of all integers which have remainder 2 when divided by 3: {2,5,8,...}
Now we can perform standard modular arithmetic to determine the addition table for this set. We find that $\bar 1 + \bar 1= \bar 2 $ (mod 3), and $\bar 2 + \bar 2= \bar 4= \bar 1$ (mod 3).
It's also easy to see that $\bar Z_q$ is a cyclic group of order q: $Z_q=\{g^0,g^1,g^2,g^3,...,g^{q-1} \}=\{\bar 1,\bar 2,\bar 3,\bar 4,...,\bar q \}$, where $g^1 \cdot g^2 =g^3 $.