Los valores que puede tomar cada variable, sería los posibles cuadrados a los que puede moverse según el estado en que se encuentre.

6.2 Consider the problem of placing k knights on an n×n chessboard such that no two knights are attacking each other, where k is given and k ≤ n

1. Choose a CSP formulation. In your formulation, what are the variables?

El problema de Reyes, es una variante del conocido problema de Reinas. En este caso, el CPS sería que los reyes no se ataquen entre ellos, es decir, que no haya dos reyes contiguos entre filas. En la imagen se puede apreciar una resolución posible del problema.

[pic 1]

Entonces, podríamos tener una variable que corresponda a cada rey en el tablero de juego.

1. What are the possible values of each variable?

Los valores que puede tomar cada variable, sería los posibles cuadrados a los que puede moverse según el estado en que se encuentre.

1. What sets of variables are constrained, and how?

Todo par de reyes es una restricción, debido a que por definición del problema explicado en la pregunta a, no puede haber dos reyes contiguos.

1. Now consider the problem of putting as many knights as possible on the board without

any attacks. Explain how to solve this with local search by defining appropriate ACTIONS and RESULT functions and a sensible objective function.

La búsqueda local a utilizar puede ser el hill climbing cuyo criterio puede ser dada bajo la premisa de que se permitan los ataques, pero se debe de tratar en la medida de lo posible el eliminarlos.  En base a esto, la acciones serían eliminar los reyes y moverlos o agregar otro rey a los cuadros vacíos.

Con respecto a la función objetivo, se debe penalizar cada ataque que se reciba por parte de los reyes, desde el punto de vista de rey – ataque, aunque el valor a penalizar debe de ser calculado y tomada con cuidado para no exagerar en el puntaje dado.

6.3 Consider the problem of constructing (not solving) crossword puzzles:5 fitting words into a rectangular grid. The grid, which is given as part of the problem, specifies which squares are blank and which are shaded. Assume that a list of words (i.e., a dictionary) is provided and that the task is to fill in the blank squares by using any subset of the list. Formulate this problem precisely in two ways:

1. As a general search problem. Choose an appropriate search algorithm and specify a heuristic function. Is it better to fill in blanks one letter at a time or one word at a time?

Tomando en cuenta el planteamiento del problema, un algoritmo adecuado sería llenar los espacios vacíos con las letras de forma individual, en vez de realizarlo llenando toda la palabra. Esto puede ser posible si se utiliza un algoritmo de búsqueda como el DFS.

1. As a constraint satisfaction problem. Should the variables be words or letters?

Tomando en cuenta el problema y la forma común en que se suele llenar los crucigramas, las variables deberían ser las letras, ya que estas suelen dar pistas de la siguiente o siguientes palabras, ya sea de forma horizontal o vertical.

Which formulation do you think will be better? Why?

...