Math on 2⁶ Squares

For centuries, chess has fascinated not only as a strategic game but also as a subject of scientific inquiry. Among the many disciplines reflected within the 64-square world, mathematics holds a special place. It allows us to analyze the vast number of possible combinations, study the symmetries of positions, optimize strategies, and predict moves with computer-like precision. At first glance, the chessboard may seem like nothing more than a battlefield of pieces, but in reality, it holds endless layers of logical relationships and computational challenges. In this article, we’ll explore how mathematics permeates the game of chess - from graph theory and combinatorics to the algorithms behind artificial intelligence.

Table of contents:

1. The Knight’s Tour:

• Mathematical Patterns on the Chessboard
• Warnsdorff’s Remarkable Heuristic
• Warnsdorff’s Heuristic - Mathematical Description
• Euler - A Pioneer’s Perspective
• Hamilton and the Paths That Bear His Name
• Hamiltonian Cycle - Mathematical Description

2. The N-Rooks Problem:

• What does "polynomial time" mean?
• Mathematical Approach
• What if we add obstacles?
• Theoretical Background
• Connection to Other Chess Problems

3. How to Place the Maximum Number of Kings on a Chessboard?:

• Solution for an n × n Board
• Example: 4 × 4 Board
• Theoretical Perspective

4. Conclusion

1. The Knight’s Tour

Mathematical Patterns on the Chessboard:

Knight’s tours created by different algorithms often reveal stunning geometric patterns - spirals, symmetries, and even graceful, calligraphy-like paths. These visualizations are not only aesthetically pleasing but also deeply inspiring for graph theorists, programmers, and lovers of recreational mathematics.

Warnsdorff’s Remarkable Heuristic:

In 1823, German mathematician H. C. von Warnsdorff proposed a beautifully simple yet powerful method for solving the knight’s tour. Known as Warnsdorff’s heuristic, the rule is: always move the knight to the square with the fewest onward moves.

This approach helps prioritize the most constrained parts of the board first, reducing the chances of getting stuck. While it doesn’t guarantee a solution in every case, it’s surprisingly effective - especially on the standard 8x8 chessboard. It’s a brilliant example of how elegant logic can lead to complex, often beautiful outcomes.

Warnsdorff’s Heuristic - Mathematical Description:

Let:

• $G = (V, E)$ be a graph where the vertices $V$ correspond to the squares of an $N \times N$ chessboard,

• and the edges $E$ represent legal knight moves, i.e., for each $(u, v) \in E$, the knight can move from square $u$ to square $v$.

The goal is to find a Hamiltonian path:

$$P=(v_1,v_2,\dots ,v_n),\text{where }n=N^2,v_i\in V,v_i\mathrm{\ne }{v}_j\text{ for }i\mathrm{\ne }j$$

Euler - A Pioneer’s Perspective:

Although the origins of the Knight’s Tour trace back to ancient India, the problem gained serious mathematical attention in the 18th century thanks to the legendary Swiss mathematician Leonhard Euler. Known for his foundational work in calculus, number theory, and graph theory, Euler also investigated knight tours, particularly closed tours - paths that return to the starting square.

His studies on knight movements were among the earliest examples of what we now call graph theory, a field that wouldn’t fully blossom until the 19th and 20th centuries.

Hamilton and the Paths That Bear His Name:

Sir William Rowan Hamilton, an Irish mathematician and physicist of the 19th century, didn’t work directly on the knight’s tour, but his contributions were pivotal. He introduced the concept of the Hamiltonian path - a route that visits every vertex of a graph exactly once - and the Hamiltonian cycle, which returns to the starting point.

The knight’s tour fits this framework perfectly: each square on the board represents a vertex, and legal knight moves are the edges connecting them.

Hamiltonian Cycle - Mathematical Description:

Let $G = (V, E)$ be a graph, where:

• $V$ is the set of vertices (e.g., chessboard squares, points in space),

• $E$ is the set of edges (connections between vertices, e.g., legal knight moves).

A Hamiltonian cycle is a cyclic path in the graph that satisfies the following conditions:

1. Visits each vertex exactly once - for each $v \in V$ there exists exactly one $v_i$ such that $v_i = v$ within the cycle.

2. Starts and ends at the same vertex - the cycle is closed, i.e., $v_1 = v_n$, where $v_1, v_2, \dots, v_n \in V$.

Formally, a Hamiltonian cycle in a graph $G$ is such a path:

$P = (v1​,v2​,…,vn​,v1​)$

where:

• $v_1, v_2, \dots, v_n \in V$,

• $(v_i, v_{i+1}) \in E$ for $i = 1, 2, \dots, n-1$,

• $(v_n, v_1) \in E$(i.e., the cycle is closed),

• Each vertex appears exactly once in $P$ (except for $v_1$, which repeats at the end of the cycle).

2. The N-Rooks Problem

One of the classic puzzles that connects chess with mathematics is the n-rooks problem. The task is to place n rooks on an n × n chessboard in such a way that no two rooks attack each other. In chess, a rook attacks all squares in its row and column, so a valid arrangement must ensure that each row and column contains exactly one rook.

What does "polynomial time" mean?

In computer science, a problem is said to be solvable in polynomial time if there exists an algorithm whose running time grows at most like some power of n (e.g., n², n³) with respect to the size of the input. This generally means the problem is considered "efficiently solvable."

Example: n = 4

Let’s consider a 4 × 4 board and try to place 4 rooks so that none attack each other.

One valid solution is:

R . . .  
. R . .  
. . R .  
. . . R  

(R represents a rook, and dots represent empty squares.)

In this solution:

• there is exactly one rook per row,

• exactly one rook per column,

• and no two rooks share a row or column.

This arrangement corresponds to the permutation (1, 2, 3, 4) - meaning: the rook in row 1 is in column 1, in row 2 in column 2, and so on.

Another solution would be:

. R . .  
. . . R  
R . . .  
. . R .  

This configuration corresponds to the permutation (2, 4, 1, 3). In total, there are 4! = 24 such arrangements for n = 4.

Mathematical Approach:

The n-rooks problem can be modeled using permutations of the set {1, 2, ..., n} — since each permutation represents a way to choose one unique column for a rook in each row. The number of valid configurations is:

$$\text{Number of solutions} = n!$$

Where n! (read as “n factorial”) is the product of all positive integers up to n. For example:

4!=4×3×2×1=24

What if we add obstacles?

If some squares on the board are blocked (e.g., rooks can't be placed there), the problem becomes harder. In that case, we may need to use backtracking algorithms, and the problem can become NP-hard - meaning that we don’t know of any efficient (polynomial-time) solution, and even checking whether a solution exists might be computationally difficult.

Theoretical Background:

Combinatorics and Permutations

The n-rooks problem is a classic combinatorial problem, focused on counting how many configurations satisfy a given condition. In this case, we're dealing with permutations - ordered arrangements without repetition.

Each valid rook configuration can be represented by a permutation matrix: an n × n matrix with 1s where rooks are placed and 0s elsewhere, with exactly one 1 in each row and column.

Example for the permutation (2, 4, 1, 3):

Permutation matrices are important in group theory (especially in the symmetric group Sₙ) and in linear algebra.

Computational Complexity

In theoretical computer science, problems are classified based on how hard they are to solve. A problem belongs to the class P if it can be solved in polynomial time - i.e., efficiently. The standard n-rooks problem belongs to this class.

However, more complex variants - such as:

• blocked squares

• irregular boards

• or logical constraints

can fall into the class NP or even be NP-hard. This means we don’t know of any fast algorithms to solve them, and it's part of the famous open question in computer science: Is P = NP?

Connection to Other Chess Problems:

The n-rooks problem is a simplified version of the more famous n-queens problem, where the task is to place n queens on an n × n board so that none attack each other. Queens can move diagonally, making the problem significantly more complex. For n ≥ 4, solutions exist, but there’s no simple formula for generating them - and solving the n-queens problem requires more advanced algorithmic techniques.

---

3. How to Place the Maximum Number of Kings on a Chessboard?

Another interesting problem combining chess and discrete mathematics is:

"What is the maximum number of kings that can be placed on a chessboard so that no two attack each other?"

In chess, a king attacks all adjacent squares - up to 8 surrounding squares (if available). That means no two kings can be placed in neighboring squares, including diagonals. So, the challenge is to find the largest possible set of squares on which kings can be placed without attacking each other.

Solution for an n × n Board:

The general rule is:

The maximum number of non-attacking kings that can be placed on an n × n board is:

$$\lceil \frac{n}{2}\rceil \times \lceil \frac{n}{2}\rceil$$

This result comes from the idea that if we place kings on every other square, skipping both rows and columns, we can avoid all conflicts.

Example: 4 × 4 Board:

We can place kings like this:

k . k .  
.  .  .  .  
k . k .  
.  .  .  .  

Here we have 4 kings in a 2 × 2 pattern. The formula gives:

$$\lceil \frac{4}{2}\rceil \times \lceil \frac{4}{2}\rceil =2\times 2=4$$

On a standard 8 × 8 chessboard:

$$\lceil \frac{8}{2}\rceil \times \lceil \frac{8}{2}\rceil =4\times 4=16$$

So, a maximum of 16 kings can be placed without attacking each other.

Theoretical Perspective:

This problem is a classic example of an independent set problem in graph theory, where:

• each square is a vertex,

• an edge connects two vertices if the corresponding squares are within a king’s move (i.e., adjacent).

We are looking for the largest set of vertices (squares) such that no two are connected - this is called a maximum independent set.

For a standard chessboard, the underlying structure is a grid graph with 8-neighbor adjacency, and this problem is known as:

Maximum independent set of kings on an n × n board

For this specific setup, an exact formula and algorithm are known, but for more general versions (e.g., irregular boards, obstacles, modified movement patterns), the problem becomes NP-hard - meaning no fast algorithm is currently known.

4. Conclusion

The intersection of chess and mathematics is not only a fascinating way to explore logic and strategy, but it also highlights the elegance and power of mathematical thinking in various aspects of life. By looking at chess from a mathematical perspective, we discover patterns, optimize strategies, and deepen our understanding of both the game and the world around us.

Thank you for reading my article! If you'd like to explore more chess puzzles, feel free to check out this link - https://en.wikipedia.org/wiki/Mathematical_chess_problem it's the source I used for my research.