Question

A simple graph can be used to determine the minimum number of queens on a chessboard that control the entire chessboard. An\({\rm{n}} \times {\rm{n}}\) chessboard has \({{\rm{n}}^2}\) squares in an \({\rm{n}} \times {\rm{n}}\) configuration. A queen in a given position controls all squares in the same row, the same column, and on the two diagonals containing this square, as illustrated. The appropriate simple graph has \({{\rm{n}}^2}\) vertices, one for each square, and two vertices are adjacent if a queen in the square represented by one of the vertices controls the square represented by the other vertex.

Construct the simple graph representing the\({\rm{n}} \times {\rm{n}}\)chessboard with edges representing the control of squares by queens for

a)\({\rm{n}} = 3\).b)\({\rm{n}} = 4\).

Short answer

(a) The figure for \({\rm{n}} = 3\) isgiven below.

(b) The figure for \({\rm{n}} = 4\) is given below.

Step-by-step solution

Identification of the given data

The given data can be listed as follows:

• The configuration of the chessboard is\({\rm{n}} \times {\rm{n}}\).
• The number of squares on the chessboard is\({{\rm{n}}^2}\).

Concept/Significance of the graph theory

Points and lines are subjects of the graph theory. It is concerned with a manner in which vertices (groups of points) can be joined by edges (lines or arcs).

(a) Construction of a simple graph of a chessboard with \(3 \times 3\) edges

The graph for \(3 \times 3\) edges is constructed as given below.

Thus, here, the control of the queen is shown by edges.

Step 4:(b) Construction of a simple graph of a chessboard with \(4 \times 4\) edges

The graph for \(4 \times 4\)edges is constructed as given below.

Thus, here, the control of the queen is shown by edges.