The Queens Puzzle, a classic problem in recreational mathematics, has intrigued puzzle enthusiasts and mathematicians for many years. The challenge is to place n queens on an n x n chessboard in a configuration where no two queens can attack each other. Solving the Queens Puzzle is not only intellectually stimulating but also provides insights into various problem-solving techniques. Here we will explore the application of graph theory to solve the Queens Puzzle. Specifically, we will use the concept of vertex independent sets, which plays a crucial role in solving combinatorial problems. By representing the Queens Puzzle as a graph and applying vertex independent set algorithms, we will see how we can systematically find all the solutions that satisfy the puzzle’s constraints.

Introduction

The Queens Puzzle is a fascinating and challenging problem that involves placing N queens on an NxN chessboard in such a way that no two queens can attack each other. This classic puzzle has intrigued mathematicians and puzzle enthusiasts for centuries, inspiring various approaches and strategies to find the solutions.
Graph theory provides a mathematical framework for studying relationships between objects, and it offers valuable insights into solving combinatorial problems. Here we will explore a unique and powerful technique to solve the Queens Puzzle using graph theory. The main idea behind using graph theory in solving the Queens Puzzle is to represent the problem as a graph, where each vertex corresponds to a position on the chessboard, and the edges represent the possibility of two queens attacking each other.
By utilizing the graph theory concept of vertex independent sets, which are sets of non-adjacent vertices, we can identify valid configurations of queens where no two queens threaten each other. This approach provides an elegant and efficient solution to the Queens Puzzle, enabling us to systematically find all the possible arrangements of queens on the chessboard that satisfy the puzzle's constraints.
Here will guide you through the step-by-step process of solving the Queens Puzzle using vertex independent sets. We will discuss the construction of the Queens Graph and explore the number of solutions for different board sizes. Moreover, we will gain valuable insights into the applications of graph theory beyond puzzle-solving, as it provides a versatile framework for addressing various real-world problems.

Queens Puzzle

The Queens Puzzle is a classic problem in the field of chess and combinatorial optimization. The most well-known instance of the Queens Puzzle is the 8-queens puzzle, where we aim to place 8 queens on an 8x8 chessboard so that no queen can capture another queen. This original problem was first posed by a German chess player in 1848. Gauss, a prominent mathematician of his time, had knowledge of this problem and found 72 solutions. However, he later realized that there were even more solutions, and he claimed that the total number of solutions was 92. E. Pauls subsequently published a proof in 1874, settling the question and confirming that there are indeed 92 unique configurations that satisfy the puzzle’s constraints.
The Queens Puzzle can also be extended to larger chessboards with different values of N. In general, the n queens problem involves placing N queens on an NxN chessboard in such a way that no two queens can attack each other. This constraint implies that no two queens should share the same row, column, or diagonal.
To solve the Queens Puzzle, a systematic approach is required to ensure a valid arrangement of the queens. One commonly used method is the backtracking algorithm. This algorithm systematically explores the solution space, placing queens on the chessboard one by one and backtracking whenever a conflict arises. It is a powerful and efficient technique for solving combinatorial problems.
Another approach to solving the Queens Puzzle, which we will focus on, involves utilizing graph theory. By representing the puzzle as a graph, with vertices corresponding to positions on the chessboard and edges representing the possibility of two queens attacking each other, we can apply graph theory techniques. In particular, we can focus on the concept of an independent vertex set, which is a set of non-adjacent vertices. In the context of the Queens graph, finding independent vertex sets allows us to identify valid configurations where no two queens threaten each other. This approach enables us to systematically find solutions that satisfy all the constraints of the puzzle.

Vertex Independent Set

A graph is a collection of vertices (also known as nodes) and edges that connect these vertices. You can think of a graph as a set of points connected by lines. The vertices are the points, and the edges are the lines connecting them. For instance, imagine a group of friends represented by a graph, where each person is a point (vertex) on the graph, and the connections between the friends are represented by lines (edges).
Out[]=
In graph theory, a vertex independent set, also known as an independent vertex set or a stable set, is a fundamental concept. It refers to a group of vertices that do not have direct connections between them. In this case, an independent set of vertices can be thought of as a group of people in the friends group that are not directly connected to each other. In other words, no two persons in the independent set are friends with each other nor they have a edge between them.
Out[]=
For example, in this graph the vertices Rose, Carol, Larry, and Rudy form an independent set, since each person in this set is not directly connected to any other in the set.
By finding independent vertex sets in a graph, we can identify groups of vertices that do not have direct connections between them. This concept has applications in various areas, including optimization problems, network analysis, and puzzle-solving. In the context of the Queens Puzzle, finding an independent vertex set corresponds to identifying a valid configuration of queens on the chessboard where no two queens can attack each other. Therefore, it helps us discover valid configurations of queens that satisfy all the constraints of the puzzle.

How the Queens Puzzle can be solved using Graph Coloring

Queens Graph

The Queens graph is a special type of graph used to represent the Queens Puzzle. It serves as a visual representation of the puzzle, where each vertex in the graph corresponds to a square on the chessboard. An edge is present between two vertices in the Queens graph if and only if the corresponding squares on the chessboard are reachable by a queen’s movement.
To establish these connections between vertices in the Queens graph, we consider the rules of the puzzle. A queen can attack another queen if they occupy the same row, column, or diagonal on the chessboard. With this in mind, we connect vertices in the graph that are in the same row, column, or diagonal.
For example, let’s consider an 8x8 Queens graph. In this case, the graph consists of 64 vertices, where each vertex represents a cell on the chessboard grid.
Out[]=
To establish the connections in the Queens graph, we assign a unique position to each node, indicating its location on the chessboard. In the case of an 8x8 chessboard, we can assign a number from 1 to 64 to each node to represent its position. Once the nodes are positioned, we can determine which nodes should be connected based on their row, column, and diagonal.
Out[]=
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
Lets begin with the rows connections. For example, let’s focus on vertex 20 as an example. Vertex 20 corresponds to a cell on the chessboard. To establish its connections, we create edges between vertex 20 and all the vertices in the same row, which are the vertices 17, 18, 19, 21, 22, 23, and 24.
Out[]=
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
We repeat this process for every node in the Queens graph. By establishing connections based on rows we capture the potential horizontal movements of a queen on the chessboard.
Out[]=
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
Let’s keep in mind that this is a simplified representation, where many edges are hidden, as all of these edges overlap with each other.
In addition to connecting each node to every other node in the same row, we also need to establish connections between nodes in the same columns. Building on the example of vertex 20, we will now connect it to all other vertices in the same column. This involves creating edges between vertex 20 and vertices 4, 12, 28, 36, 44, 52, and 60.
Out[]=
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
We repeat this process for every node in the Queens graph. By establishing connections based on columns we reflect the potential vertical movements of a queen on the chessboard.
Out[]=
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
In addition to connecting nodes based on rows and columns, we also establish edges between each node and every other node in the same diagonal. Building upon our example of vertex 20, we connect it to all the vertices within the same forward diagonal.
Out[]=
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
By establishing these forward diagonal connections, we accurately represent the potential forward diagonal movements of a queen on the chessboard.
Out[]=
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
Finally, to complete the connections in the Queens graph, we establish edges between each node and every other node in the same counter diagonal. Continuing with our example of vertex 20, we connect it to all the vertices within the same counter diagonal.
By establishing these counter diagonal connections, we accurately represent the potential counter diagonal movements of a queen on the chessboard.
By establishing all these connections based on rows, columns, and diagonals, we create a connected graph where each node follows the following connection pattern:
This comprehensive network of connections ensures that the graph accurately represents the potential movements of a queen on the chessboard, covering all possible paths and capturing the constraints of the Queens Puzzle.
The described graph can be constructed using the following resource function:
We can also generalize this approach for queens puzzles of different sizes. Let’s consider a 4 queens puzzle as an example. In a 4 queens puzzle, the queens graph consists of 16 vertices, with each vertex representing a cell on the chessboard. To solve the queens puzzle using graph theory, we still need to establish connections between these vertices. Similar to the 8 queens example, we assign a unique position to each node based on its location on the chessboard. Once the nodes are positioned, we can determine the connections based on rows, columns, and diagonals. This results in a graph where each vertex is connected to every other vertex in its row, column, diagonal, and counter-diagonal.
However, it’s important to remember that these graphs are simplified representations, and the provided images show these edges lying on top of each other to avoid clutter and provide clarity.

Vertex Independent Set

As mentioned earlier, an independent set is a subset of vertices in the graph where no two vertices are adjacent, ensuring that no edges exist between any two vertices within the set. In the context of the Queens Puzzle, the concept of vertex independent sets becomes significant because each queen represents a vertex on the chessboard, and the connections between queens represent the potential attacks they can make on each other. By finding an independent set of vertices (queens) on the chessboard, we guarantee that no two queens can attack each other, ultimately solving the puzzle. Therefore, finding an independent set in the Queens graph allows us to identify a valid placement of queens that solves the puzzle.
However, not all independent sets in the Queens graph correspond to valid solutions for the puzzle. Some independent sets may result in configurations with fewer than n queens, failing to satisfy the puzzle's constraints. To address this, we need to find the maximum independent sets, which are independent sets containing exactly n vertices (queens). By finding all possible maximum vertex independent sets in the Queens Graph, we can identify all distinct arrangements of queens on the chessboard that solve the puzzle. Each vertex independent set corresponds to a valid solution, where the queens are placed in non-attacking positions.
Fortunately, the Wolfram Language provides a function that can assist us in this task. We can use this function to find all the vertex independent sets of a specified size in the Queens Graph. By specifying the size of the vertex independent set, we can generate all possible valid configurations of queens for that size. This allows us to systematically explore and enumerate all the solutions to the Queens Puzzle using graph theory. For example to find the Maximal Independent Vertex Set (of size 4) we can use:

Solutions

Now that we have a good understanding of vertex independent sets, let’s explore how they can be applied to solve the Queens Puzzle. In this section, we will discuss how to identify independent sets within the graph and translate these independent sets into valid configurations of queens on the chessboard.
To solve the n queens problem, let's revisit our 8 queens example. By utilizing the Queens graph, we can find all the independent vertex sets of size 8. These independent sets correspond to valid configurations of queens on the chessboard that satisfy the constraints of the puzzle.
To visualize these solutions, we can print the solution on the chessboard. This allows us to observe and analyze the various valid configurations for the Queens Puzzle:
For example, let’s consider four additional possible solutions for the 8 queens problem:

Number of Solutions

The number of solutions for the n Queens Puzzle is a fascinating aspect to explore. For n = 1, the problem has a trivial solution, and no solution exists for n = 2 and n = 3. So let’s consider the 4 queens problem:
As we can see there are two possible solutions for the 4 queens problem.
For n=5, there are 10 solutions:
For n=6, there are 4 solutions:
For n=7, there are 40 solutions:
And for n=8, as mention previously, there are 92 solutions:
As we can see, as n increases, the complexity of finding solutions grows exponentially. Therefore, finding an exact formula or enumeration for the number of solutions becomes increasingly difficult. As a result, researchers have primarily focused on determining the total count of solutions for relatively small values of n. The following table shows the number of solutions for up to the 12 queens puzzle:
To verify the number of solutions for puzzles beyond n=8, we can calculate the size of the Vertex Independent Set for each value of n. By finding all independent sets of size n in the Queens graph, we can determine the number of distinct arrangements of queens on the chessboard that satisfy the puzzle’s constraints:
Up to this point, the calculations for finding all the solutions have been relatively fast, with just seconds required to obtain all the solutions for the given puzzle sizes. However, when it comes to the 12 queens puzzle, the process becomes more computationally intensive, taking approximately 5 minutes to find all the possible 14,200 configurations.
The computation time required for larger puzzle sizes serves as a reminder of the growing complexity of the problem. Nonetheless, having this knowledge is crucial as it guides our search for solutions and forms the foundation for developing efficient algorithms and techniques.

Conclusion

Here we have explored the application of graph theory in solving the Queens Puzzle. By utilizing the concept of vertex independent sets, we have been able to find solutions that satisfy the puzzle’s constraints and ensure that no two queens can attack each other. We have gained an understanding of the Queens Puzzle, the significance of vertex independent sets, and how they can be applied to address the puzzle effectively.
By using graph theory, we have discovered a powerful framework for solving complex problems. The concept of independent sets has provided a systematic approach to finding all possible configurations of queens on the chessboard, allowing us to explore and enumerate solutions. We have also discussed the challenges and exponential growth of the problem as the puzzle size increases.
Through this exploration, we have not only solved the Queens Puzzle but also we can observe how graph theory concepts provide a versatile toolkit that enables us to analyze and solve a wide range of problems by representing them as graphs and applying relevant algorithms and techniques.

References

◼
  • Campbell, P. J. (1977). Gauss and the eight queens problem: A study in miniature of the propagation of historical error. Historia mathematica, 4(4), 397-404.
    • ◼
  • Sprague, T. B. (1898). On the eight queens problem. Proceedings of the Edinburgh Mathematical Society, 17, 43-68.

    • CITE THIS NOTEBOOK

    Solving the Queens Puzzle with Graph Theory​
    by Alejandra Ortiz Duran​
    Wolfram Community, STAFF PICKS, August 1, 2023
    ​https://community.wolfram.com/groups/-/m/t/2981266