===================================
Problem 1. Crossword puzzle
===================================
Part A. Variables.
We use rows or columns of boxes as variables. In this case we have
four variables H1,H2,V1,V2  (we use H for horizontal and V for vertical)

Part B. Domains
All the variables can take values out of the same domain D. In our case
we define D = {THE, UNIVERSITY, OF, CHICAGO}

Part C. Constraints
We define two kinds of constraints.
Length constraints:
	length(H1) == 10
	length(H2) == 2
	length(V1) == 3
	length(V2) == 7
Cross constraints:
	H1(5) == V1(3)
	H1(8) == V2(3)
	H2(1) == V2(7)

Part D. Arc consistency problems
There are two kinds of problems, when there are no legal assignments or there are more
than one legal assignment.

Example of more than one legal assignment.
Assume three variables V1,H1,H2 taking values out of the domain D = {bit, its, hit, sit, ion, one}
      V1
H1 | | | |
     | |
H2 | | | |

after applying the arc consistency algorithm (page 146) the domains for each variable are equal to
D(H1) = {bit, hit, sit}
D(V1) = {ion}
D(H2) = {one}
There is more than one legal assignment for the variable H1

Example of no legal assignment.
In the previous example change the domain from D to E = {bit, its, hit, sit, ion } 

Part E.
Procedures based on backtracking do not have problems with multiple legal assignments because
they pick the first one that satisfies the constraints without looking for more options.
When there are no legal assignments, they search the whole space, then return a failure value
(see algorithm in the book)

Part F.
(0). Start a counter of steps count := 0
(1). Assign to each variable a random word taken from its respective domain.
(2). Count the number of conflicts each assignment produced (number of constraints unsatisfied)
(3). Pick the variable with the highest number of conflicts and change its value until its number of conflicts
     is reduced
(4). Increase count by one
(5). If count is less than a predetermined maximum number of steps, repeat from step (2)

Note: Explain why it is necessary to have a maximum number of steps. Is this an optimal method?

Part G.
now that you have the algorithm, try it at home!


===================================
Problem 2. Constraint satisfaction
===================================
Part A.

The plain backtracking algorithm does a search of possible solutions for 
a constraint satisfaction problem using an incremental scheme. 
It represents the search space as a tree in which each node is a partial 
assignment of values. The depth of the node is equal to the number of
variables that have assigned values.
The search is done using depth first search and checking in each visited node
if the partial assignment satisfies the problem constraints.
The constraints are not prechecked, meaning that the only way that the algorithm
has to discard a partial assignment is evaluating it.
If the partial assignment is invalid, the algorithm does not continue assigning values
to the rest of free variables but backtracks one step and continues doing the depth
first search.

Part B.
When one value is assigned to a variable X it can affect the domain of none/some/all 
the variables connected to X. As the partial assignment cover more variables,
the domains of "unassigned" variables can get smaller and eventually empty (a dead end in the 
plain backtracking algorithm).

Forward tracking tries to avoid partial assignments that lead to dead ends. Each time that 
a variable X is assigned it updates the domain of each of the variables connected to X.
When the domain of a variable becomes empty the algorithm backtracks.

===================================
Problem 3. 
===================================
Part A.
Choosing the most constrained variable increases the chances of ruling out bad 
partial assignments in early stages of the search. It's assumed that variables 
with more constraints are more likely to run out of valid values.

Part B.
Choosing the least constrained variable decreases the chances of reducing the domain 
of related variables to an empty set. 

===================================
Problem 4. Genetic Algorithm 
===================================
Chromosome.
In this problem we represent a gene as a variable that can take values out of the domain
RAINBOW = {r, o, y, g, b, i, v}
The chromosome is a string of 20 variables that belong to the set RAINBOW

Quality measure.
There are many possible ways of defining the quality measure. One option is to define it as:
F( chromosome ) = number of correct colors + number of correctly positioned pegs
Observe that the function F assign two points for each correctly positioned peg
and one point for each of the rest of pegs with correct color but in the wrong position
How would you give more priority to the correctly positioned pegs?
Is a good idea to change F generation after generation?

Mutation operator.
There are many options for the mutation too. 
Examples:
- Pick a gene at random and change its value randomly. 
- Swap the values of two genes.
Are these two operators convenient at any generation? Why?