Chess and Mathematics: Kim Yong Woo

Basic Rules of Chess
Chess and Mathematics

Kim Yong Woo
KAIST
December 23, 2011
Kim Yong Woo Chess and Mathematics
Board and pieces
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
Chess is played on an 8x8 chessboard
with a whole lot of other pieces.
Pawn Knight Bishop Rook Queen King
Board and pieces
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
Chess is played on an 8x8 chessboard with a whole lot of other pieces.
Pawn Knight Bishop Rook Queen King
Board and pieces
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
Pawn
Knight Bishop Rook Queen King
Board and pieces
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
Pawn
Knight
Bishop Rook Queen King
Board and pieces
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
Pawn Knight
Bishop
Rook Queen King
Board and pieces
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
Pawn Knight Bishop
Rook
Queen King
Board and pieces
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
Pawn Knight Bishop Rook
Queen
King
Board and pieces
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
Pawn Knight Bishop Rook Queen
King
The Pawn
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
The pawn can move only one square forward
except at the beginning where it
can move two squares.
When capturing, pawns move diagonally
The Pawn
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
The pawn can move only one square forward
except at the beginning where it
The Pawn
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
The pawn can move only one square forward except at the beginning where it
The Pawn
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
The Pawn
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
The Knight
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
Knights move in an interesting way.
Knights can jump over other pieces.
The Knight
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
The Knight
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
The Knight
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
The Knight
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
The Bishop
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
Bishops move diagonally.
The Bishop
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
The Bishop
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
The Rook
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
Rooks move in a straight line.
The Rook
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
The Rook
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
The Queen
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
Queens can move both like rooks and bishops.
The Queen
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
The Queen
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
The Queen
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
The King
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
Kings can move to any square surrounding it.
The game ends when the king cannot escape. (Check mate)
The King
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
The King
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
The King
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
So how can we relate chess to mathematics?
In recreational mathematics, there are two problems asked.
1
How many pieces of a given type can be placed on a chessboard without
attacking each other?
2
What is the smallest number of pieces needed to attack every square?
1
2
1
2
The Bishops Problem
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
For an n n chessboard, the answer is 2n 1.
The number of rotationally
and reectively distinct solutions is given by,
B(n) =
2
n4
2
2
n2
2
+ 1
for n even
2
n3
2
2
n3
2
+ 1
for n odd
The Bishops Problem
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
For an n n chessboard, the answer is 2n 1. The number of rotationally
and reectively distinct solutions is given by,
B(n) =
2
n4
2
2
n2
2
+ 1
for n even
2
n3
2
2
n3
2
+ 1
for n odd
The Bishops Problem
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
The answer is n = 8.
The Knights Problem
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
For an 8 8 chessboard, the answer is 32.
In general,
K(n) =
1
2
n
2
for n > 2 even
1
2
n
2
+ 1
for n > 1 odd

The Knights Problem
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
For an 8 8 chessboard, the answer is 32. In general,
K(n) =
1
2
n
2
for n > 2 even
1
2
n
2
+ 1
for n > 1 odd

The Knights Problem
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
The answer is 12.
The Knights Tour
The knights tour is a mathematical problem involving a knight on a
chessboard.
An instance of the more general Hamiltonian path problem, or
Hamiltonian cycle problem in graph theory.
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
On an 8 8 chessboard, there are exactly 26,534,728,821,064 directed closed
tours.
The Knights Tour
chessboard. An instance of the more general Hamiltonian path problem, or
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
tours.
The Knights Tour
Schwenks Theorem
1
m and n are both odd and are both not equal to 1.
2
m = 1, 2, 4 and m and n are both not equal to 1.
3
m = 3 and n = 4, 6, 8
Proofs?
The Knights Tour
Schwenks Theorem
1
2
3
m = 3 and n = 4, 6, 8
Proofs?
The Knights Tour
Schwenks Theorem
1
2
3
m = 3 and n = 4, 6, 8
Proofs?
The Knights Tour
Schwenks Theorem
1
2
3
m = 3 and n = 4, 6, 8
Proofs?
The Knights Tour
Schwenks Theorem
1
2
3
m = 3 and n = 4, 6, 8
Proofs?
Condition 1: m and n are both odd
For the standard black and white chessboard, the knight must move either
from a black square to a white square or from a white square to a black square.
So in a closed tour, the knight must visit the same number of black and white
squares. (i.e. the total number of squares visited must be even)
However, when m and n are both odd, the total number of squares is odd and
therefore, a closed tour does not exist.(except for the trivial case of m = 1 = n)
Condition 2: The shorter side m is of length 1, 2, 4.
When m = 1, the knight cannot move anywhere since it must change lines
when moving.
When m = 2, the knight can move but it can only visit some squares which are
determined by the knights starting point
The case when m = 4 requires some more thinking.
when moving.
when moving.
when moving.
Imagine a 4 n board, which is coloured like the following gure, and lets
assume that a closed knights tour exist.
Now lets dene the following:
A
1
- The set of all black squares.
A
2
- The set of all white squares.
B
1
- The set of all green squares.
B
2
- The set of all red squares.
Note that there are an equal number of green squares and red squares.
From a square in B
1
, the knight doesnt have any choice apart from moving to
a square in B
2
.
Since the knight has to visit every square, and there are an equal number of
green squares and red squares, from a square in B
2
, the knight must move to a
square in B
1
or else the knight would have to move from B
1
to B
1
which is
impossible.
A
1
A
2
B
1
B
2
From a square in B
1
a square in B
2
.
2
square in B
1
1
to B
1
which is
impossible.
A
1
A
2
B
1
B
2
From a square in B
1
a square in B
2
.
2
square in B
1
1
to B
1
which is
impossible.
A
1
A
2
B
1
B
2
From a square in B
1
a square in B
2
.
2
square in B
1
1
to B
1
which is
impossible.
A
1
A
2
B
1
B
2
From a square in B
1
a square in B
2
.
2
square in B
1
1
to B
1
which is
impossible.
Now we can draw a closed knights tour. Looking at the process step by step:
1
Lets start at a square of A
1
and B
1
.
2
The second square must be of A
2
and B
2
.
3
The third square must be of A
1
and B
1
.
4
The fourth square must be of A
2
and B
2
.
5
And so on.
This shows that set A
1
has the same elements as set B
1
and set A
2
has the
same elements as set B
2
.
This is obviously not true since the red and green patterns do not have the
checkerboard pattern of a chessboard.
Therefore, our assumption was false and no closed knights tour can be drawn
for a 4 n board.
1
1
and B
1
.
2
2
and B
2
.
3
1
and B
1
.
4
2
and B
2
.
5
And so on.
1
1
and set A
2
has the
2
.
for a 4 n board.
1
1
and B
1
.
2
2
and B
2
.
3
1
and B
1
.
4
2
and B
2
.
5
And so on.
1
1
and set A
2
has the
2
.
for a 4 n board.
1
1
and B
1
.
2
2
and B
2
.
3
1
and B
1
.
4
2
and B
2
.
5
And so on.
1
1
and set A
2
has the
2
.
for a 4 n board.
1
1
and B
1
.
2
2
and B
2
.
3
1
and B
1
.
4
2
and B
2
.
5
And so on.
1
1
and set A
2
has the
2
.
for a 4 n board.
1
1
and B
1
.
2
2
and B
2
.
3
1
and B
1
.
4
2
and B
2
.
5
And so on.
1
1
and set A
2
has the
2
.
for a 4 n board.
1
1
and B
1
.
2
2
and B
2
.
3
1
and B
1
.
4
2
and B
2
.
5
And so on.
1
1
and set A
2
has the
2
.
for a 4 n board.
1
1
and B
1
.
2
2
and B
2
.
3
1
and B
1
.
4
2
and B
2
.
5
And so on.
1
1
and set A
2
has the
2
.
for a 4 n board.
1
1
and B
1
.
2
2
and B
2
.
3
1
and B
1
.
4
2
and B
2
.
5
And so on.
1
1
and set A
2
has the
2
.
for a 4 n board.
Condition 3: m = 3 and n = 4, 6, 8
This condition can be proved by actually attempting to draw a closed knights
tour which will lead to failure. For n even and greater than 8, there is a
repeating pattern and therefore could be shown to have closed knights tours
by induction.
Warnsdors rule
Warnsdors rule is a method for nding a knights tour; always proceed to the
square from which the knight will have the fewest onward moves.
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
2
3
5
7
7
7
When calculating the number of onward moves, we do not include squares that
have been visited already. This rule in general can be applied to any graph;
each move is made to the adjacent vertex with the least degree.
Warnsdors rule
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
2
3
5
7
7
7
Warnsdors rule
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
2
3
5
7
7
7
Warnsdors rule
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
2
3
5
7
7
7
have been visited already.
This rule in general can be applied to any graph;
Warnsdors rule
a
1
b
c
d
e
f
g
h
2
3
4
5
6
7
8
2
3
5
7
7
7
Thank you for listening!

Chess and Mathematics: Kim Yong Woo

Uploaded by

Copyright:

Available Formats

Chess and Mathematics: Kim Yong Woo

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Chess and Mathematics: Kim Yong Woo

Uploaded by

Copyright:

Available Formats

Basic Rules of Chess

Chess and Mathematics

for n > 1 odd

for n > 1 odd

You might also like