This worksheet gives you some important practice with the fundamentals of CSPS!
- Provide answers to each of the following questions and write your responses in the blanks. If you are expected to show your work in arriving at a particular solution, space will be provided for you.
- Place the names of your group members below:
Problem 1 – CSP Formalization & Backtracking
Time for another rite of passage in this Tour de Algorithms we call 282: The N-Queens Problem.
The N-Queens Problem is a CSP in which the goal is to place chess queens on an chess board such that no queen can capture any other. For those unfamiliar with chess, Queens are the most powerful piece that, on any given turn, can move as many tiles as desired in horizontal, vertical, and diagonal directions. A Queen is capturable if an attacker can move from its tile to that of in a single turn.
Below, observe (left) a solution to the 4-Queens problem and (right) constraints violated on that same problem (the Queen at can capture both the one at and ).
In these problems, we have Queen variables to place with the implicit constraint that none may capture one another (too verbose to list explicitly).
- For the purposes of improving the efficiency of backtracking, why would it be wasteful to represent each variable’s state as an tuple rather than simply their (i.e., as a single integer)?
- Using this representation (i.e., assigning each Queen to a specific row), would constraint propagation preprocessing be effective at pruning any domains? Why or why not?
Suppose we represent the partially specified assignments during backtracking on the N-Queens problem as a tuple of queens in which the tuple index specifies each Queen’s column, and int contents specify each Queen’s Row. For example: denotes a partial specification in which (because it’s at the 0th index, and therefore the Queen in the 0th column, and the value there is a 2), , and have yet to be assigned.
Now during backtracking, suppose we apply forward checking to remove any inconsistent values from the domains of adjacent (in the constraint graph), unassigned variables based on the assignments made to variables thus far. This means that an assignment of , denoted by the partial assignment , would have the following domain restrictions by forward checking (with the constraint graph on the left and reductions in red on the right):
- Draw the backtracking recursion tree with forward checking during backtracking that would solve the 4-Queens problem using the above partial-assignment-notation.
Problem 2 – Constraint Propagation
Since it’s relevant to your upcoming assignment, let’s talk about a nice numerical example; we’ll do something similar with Dates in HW 5, but for now, let’s just stick with numbers.
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: email@example.com 微信:itcsdx