## Introduction

Chess is a game whose roots go all the way back to the 7th century, where text references about its predecessors are found. It evolved through the years and reached its current state during the 15th century. The complexity of the game is highlighted by the countless possible chess matches (~10120). Regardless, the game attracted all kinds of different people, showcasing their nature through their playing style (e.g. strategists, perfectionists, passive, attacking maniacs, etc.). Along with those, chess attracted scientists’ attention, mostly mathematicians and in recent years, computer scientists. Since 1997, when the world champion Garry Kasparov lost to the supercomputer Deep Blue, the landscape of chess changed drastically.

Nowadays, chess engines use artificial intelligence and neural networks and have surpassed human players in every aspect of the game. Some of the most popular engines, like Stockfish, LeelaChessZero, KomodoChess and more, are rated well over 3300 Elo (rating system), while the highest Elo ever achieved by a human is 2882 (in year 2014 by Magnus Carlsen, current world champion).

## Eight Queens Puzzle

One could talk about the different openings, tactics, strategies, endgames or analyses of amazing games between strong opponents, but this would take hours on end. Let’s see a well-known chess puzzle instead and attempt to perceive it from a Graph theoretical point of view. The “Eight Queens puzzle” was composed by Max Bezzel, a German chess composer, in 1848. The aim of the problem is to place 8 Queens in a 8×8 chessboard, in a way that no two Queens attack each other, meaning that no two Queens share a row, column or diagonal. The puzzle was the first realization of a more general problem, placing n non-attacking Queens on a n×n chessboard. Regarding the general problem, different questions have been formulated:

• Does a solution exist for a specific n-Queen problem?

It has been proven  that for any n, apart from n=2 and n=3, solutions do exist

• How many solutions exist?

No exact number of solutions has been calculated, but the actual number can be estimated in certain bounds. Most recently , for very large chessboards, the upper and lower bounds were brought close enough to estimate the number of solutions with:

Q(n) =(0.143n)n

• How can the solutions be computed?

Algorithms using combinatorics have been implemented, but the computational cost for increasing n is too high (e.g. for n=20, more than 40 billion solutions exist!)

## Graph representation

After setting the general picture, let us play with the original 8 Queens problem.

In a 8×8 chessboard, 64 squares exist. Each square can be viewed as a node of a graph and edges will connect nodes that are “visible” to each other. For any Queen placement on node i, all nodes in the same row/column/diagonal, therefore attacked by the Queen, are “visible” from node i. Applying this on every node, an adjacency matrix can be created and a graph can be constructed (Fig.1). This graph is known as the Q(8) Queen graph and has |V|=64 nodes and |E|=728  edges. Fig.1 On the left, the adjacency matrix for the 8×8 Queen graph, blue indicates link and white indicates absence of link. On the right, the Queen graph with the actual layout of the chessboard.

## Solutions

The brute force way of finding the solutions -by checking all the different configurations- scales terribly with n, since the factorial of n is involved. For n=8, number |P| shows the different ways that a set of 64 items (squares) can be arranged into permutations of length 8: If we notice that all Queens are of the same “quality”, meaning that the reshuffling of a solution maps to the solution itself, we can use combinations instead of permutations. Despite this simplification, combinations still scale rapidly with  and every combination must be checked if it serves as a solution. Calculating all the solutions is not something that you can “just do”, even for the small 8×8 problem.

Let’s see the solutions from another point of view now. Notice that in the graph representation, a solution of the problem will be a subset Vs ⊂ V with |Vs|=8, for which all nodes of the subset are not directly connected. As shown in Fig.2, if the 1st Queen is placed on a node, all visible nodes become unavailable. Then, the 2nd Queen can be placed in any position in the subset of available nodes and will further reduce the subset of available nodes. This implies that if a configuration is a solution, it will also be an independent set of Q(8) or a clique of its complement. The problem of finding either independent sets or cliques is NP-complete, but for small graphs like Q(8) it is easily computed using any complex network package (e.g. NetworkX uses the algorithm implemented in  to find cliques). Fig.2 On the left, the 1st Queen of a possible solution has been placed on node 1 (black). The red nodes are visible from the 1st Queen, hence they become unavailable for other Queens. On the right, the 2nd Queen has been placed on node 31(black) and all nodes visible from her become unavailable. The same applies for every step of placing a Queen in order to construct a solution.

Let’s now implement a simple “subgraph-algorithm” based on the abovementioned idea. Solutions will be constructed in the following way:

• Iterate through the nodes of any row i (since any solution will have a node in every row, checking all possible Queen placements for a single row will find all the solutions)
• For every node j in row i,  create the induced subgraph that contains only nodes that are not visible from j, hence are available for the following Queen placements. Construct a possible solution spos={j}.
• For every node k in the vertex set of the induced subgraph, add a new node to the possible solution and remove any nodes that are visible to k, resulting to a new subgraph. Do this recursively until the vertex set of the induced subgraph is empty, meaning that all the nodes are visible, hence the whole chessboard can be attacked.
• If the length of the possible solution is |spos|<8, it means that the whole chessboard can be attacked and no more Queens can be placed, hence the particular configuration cannot be extended into an actual solution.
• If the length of the possible solution is |spos|=8, then the particular configuration is a solution.

Using either algorithm  or the mentioned subgraph-algorithm, all 92 solutions of the problem can be identified. In Fig.3 two solutions are shown. Fig.3 Two solutions of the 8 Queens problem, identified using the subgraph-algorithm

## Symmetry

Clearly, there is symmetry in the solutions of the problem (e.g. seeing the same solution after rotating the board). Since the chessboard is a square, all its symmetries are included in the dihedral group of order eight, D4 (four rotations and four reflections). If the symmetries of D4 get applied on the 92 solutions, only 12 fundamental solutions will remain.

 A dihedral group is the group of symmetries of a regular polygon, https://en.wikipedia.org/wiki/Dihedral_group

## Conclusions

All this was just a fun, network approach to a fraction of the work done on the n-Queens problem. Several variations of the problem have been studied (e.g. toroidal chessboards or problems for other chess pieces like knights or fictional pieces like super-queens, etc.). In conclusion, chess is whatever anyone makes it to be. It could be a boring/uninteresting game for some, an enjoyable evening for others, a trip in a fantasy world for the romantics, a whole life for the pioneers and professionals and in the eyes of a scientist, chess can turn into patterns, numbers, graphs and more. One thing is for certain, as soon as someone sees the beauty of it, he is hooked for life.

### References

  E. Pauls, Das Maximalproblem der Damen auf dem Schachbrete, Dtsch. Schachzeitung 29 (5) (1874) 261–263.  M. Simkin, The number of \$n\$-queens configurations., 2021.  F. N. A.-K. N. E. B. E. J. C. M. A. L. a. N. F. S. Yun Zhang, Genome-Scale Computational Approaches to Memory-Intensive Applications in Systems Biology, SC ’05: Proceedings of the 2005 ACM/IEEE Conference on Supercomputing, 2005, pp. 12-12, doi: 10.1109/SC.2005.29., 2005.