N-Queens problem

Consider an n × n chessboard. Let there be n queens. These n queens are to be placed on the board so that no two queens are on the same column, same row or same diagonal, i.e. they do not attack each other.

4-Queens problem

Explicit constraints: 4 queens are to be placed on a 4 × 4 chessboard in $4^4$ ways.

Implicit constraints: no two queens are in the same row, column or diagonal.

Apply backtracking

Begin with the root node and generate other nodes.

• A node which has been generated and all of whose children have not yet been generated is called a live node.
• The live node whose children are currently being generated is called the E-node (node being expanded).
• A dead node is a generated node which is not to be expanded further or all of whose children have been generated.

In both methods of generating, we have a list of live nodes.

• Method 1: As soon as a new child C of the current E-node R is generated, this child becomes the new E-node. Then R will become the E-node again when the subtree C has been fully explored. This corresponds to a depth first generation of the problem states.
• Method 2: The E-node remains the E-node until it is dead.

In both methods, bounding functions are used to kill live nodes without generating all their children. At the end of the process one answer node is always generated, or all answer nodes are generated if the problem requires us to find all solutions.

• Depth first node generation with bounding functions is called backtracking.
• State generation methods in which the E-node remains the E-node until it is dead lead to branch-and-bound methods.

Terminology

1. Each node of the tree defines a problem state.
2. All paths from the root to other nodes define the state space of the problem.
3. Solution states are those problem states s for which the path from the root to s defines a tuple in the solution space.

Permutation tree for n = 4

A possible tree organization for the case n = 4, i.e. a permutation tree.

• Nodes are numbered as in depth first search.
• Edges from level i to level i+1 are labeled with the values of $x_i$.
• The solution space is defined by all the paths from the root node to a leaf node. There are $4!=24$ leaf nodes in the tree.

Two tree organizations of the solution space

The heading on this page of the handwritten notes is partly crossed out; the two trees below are the variable-size and fixed-size tuple formulations for n = 4.

Solution 1: variable tuple size

Nodes are numbered as in breadth first search with variable tuple size formulation. New nodes are placed into a queue.

Solution 2: fixed tuple size

Nodes are numbered as in D-search (depth search) with fixed tuple size. New nodes are placed into a stack.

Solution 1: At each node the solution space is partitioned into sub-solution spaces. The solution space is defined by all paths from the root node to any node in the tree, since any such path corresponds to a subset satisfying the explicit constraints. Possible paths are (), (1), (1,2), (1,2,3), (1,2,3,4), (1,2,4), (1,3,4), (2), (2,3) and so on.

Solution 2: The left subtree of the root defines all subsets containing w₁, the right subtree those not containing w₁. There are $2^4$ leaf nodes which represent 16 possible tuples.

• In the Solution 1 tree, all nodes are solution states.
• In the Solution 2 tree, only leaf nodes are solution states.

Terminology (continued)

4. Answer states are those solution states s for which the path from the root to s defines a tuple that is a member of the set of solutions (i.e. it satisfies the implicit constraints) of the problem.
5. The tree organization of the solution space is referred to as the state space tree. The solution space is partitioned into disjoint sub-solution spaces at each internal node. Every element of the solution space is represented by at least one node in the state space tree.
6. Solution tree 2 is a static tree. Tree organizations are independent of the problem instance being solved.
7. Solution tree 1 is a dynamic tree.

• The Solution 2 tree is numbered according to the generation method in which the E-node remains the E-node until it is dead. New nodes are placed into a stack, i.e. it uses depth search.
• In the Solution 1 tree each new node is placed into a queue. When all the children of the current E-node have been generated, the next node at the front of the queue becomes the new E-node.

Backtracking solution for Solution tree 1

Bounding function criteria: if $(x_1,x_2,\dots ,x_i)$ is the path to the current E-node, then all children nodes with parent-child labelings $x_{i+1}$ are such that $(x_1,\dots ,x_{i+1})$ represents a chessboard configuration in which no two queens are attacking.

Example of a backtrack solution to the 4-queens problem

The number inside each queen is its row. A × marks a square that is attacked, so the next queen cannot be placed there.

Solution = $⟨2,4,1,3⟩$. The portion of the tree generated during backtracking is shown below. This tree is part of the Solution 1 tree. B marks a node that gets killed as a result of the bounding function.

Nodes 19 and 24 are marked B here because they violate the bounding function; the handwritten figure leaves them unmarked.

Number of nodes in the 8-queens state space tree

The total number of nodes in the 8-queens state space tree is, as written in the notes:

Check: evaluated exactly as written, this formula gives 109,601 (for n = 4 the same formula gives 65, the size of the permutation tree drawn above). The value 69,281 equals the same sum without its last term, 40,320. Please confirm which figure your course expects.

Trace of NQueens(1, 4)

Place(k, i) checks whether the k^th queen can be placed in column i. The solution vector is (x₁, x₂, x₃, x₄).