In a bin-packing problem, during the exploration of the search tree by a DFS, the variable heuristic choses the next object to place (the one with a weight 3 on top) in the partial solution represented below.

By default the search will create a branch in the search tree for the placement of this object in each bin. As you have learned from the videos, this might lead to the exploration of symmetrical search spaces.

What are the branching decisions (bins) you would keep to avoid the exploration of symmetrical search spaces while remaining complete.

We consider an alternative model for the n-queens problem, where the n-variables \(q_1, ..., q_n\) correspond to the n queens and the domain of each variable is the set of integers \(\{1, 2, ..., n^2\}\), representing the squares on the chessboard. Thus an assignment \((q_i, a)\) means that the \(i\) th queen is on square \(a\).

Check all the valid statements:

We consider an alternative model for the n-queens problem, where the n-variables \(q_1, ..., q_n\) correspond to the n queens and the domain of each variable is the set of integers \(\{1, 2, ..., n^2\}\), representing the squares on the chessboard. Thus an assignment \((q_i, a)\) means that the \(i\) th queen is on square \(a\).

Check all the valid statements:

Assume that we use search heuristic denoted by H, and we break the symmetries by adding the constraints \(q_1 < q_2 < \ldots < q_n\) to our model. Check all the valid statements

The graph Coloring problem is to assign a color to each vertex in a graph such that no adjacent vertices share the same color using at most k-colors. We consider a model with one variable per vertex and the domain of each variable is the set of possible colors.

Check all the valid statements: