Subgraphs in the service of the Queen

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 15^th century. The complexity of the game is highlighted by the countless possible chess matches (~10¹²⁰). 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[1], LeelaChessZero[2], KomodoChess[3] 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).

[1] https://stockfishchess.org/

[2] https://lczero.org/

[3] https://komodochess.com/

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 [1] 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 [2], for very large chessboards, the upper and lower bounds were brought close enough to estimate the number of solutions with:

Q(n) =(0.143n)ⁿ

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

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 V_s ⊂ V with |V_s|=8, for which all nodes of the subset are not directly connected. As shown in Fig.2, if the 1^st Queen is placed on a node, all visible nodes become unavailable. Then, the 2^nd 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[4] uses the algorithm implemented in [3] to find cliques).

[4] https://networkx.org/

 

 

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 s_pos={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 |s_pos|<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 |s_pos|=8, then the particular configuration is a solution.

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

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[5] group of order eight, D₄ (four rotations and four reflections). If the symmetries of D₄ get applied on the 92 solutions, only 12 fundamental solutions will remain.

[5] 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

[1]	E. Pauls, Das Maximalproblem der Damen auf dem Schachbrete, Dtsch. Schachzeitung 29 (5) (1874) 261–263.
[2]	M. Simkin, The number of $n$-queens configurations., 2021.
[3]	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.