Búsqueda no informada

En está practica se implementara un algoritmos de búsqueda primero por amplitud para el problema de las N-Reinas. El problema consiste en encontrar una configuración en la que colocando N reinas sobre un tablero de ajedrez de NxN, ninguna se ataque entre si, es decir ninguna de las n reinas queda sobre la misma  columna, fila o diagonal.  No existe solución para el problema de 2x2 y 3x3. Una solucion posible para un tablero de 4x4 sería la siguiente.

Para simplificar la representación podemos definir una configuarción de tablero como un vector de n elmentos,  en el que cada del vector indica en que fila se encuantra la reina  de la i-esima columna.  Por ejemplo para la configuración anterior la representación como vector sería {2,4,1,3} (e.g la reina uno se encuentra en la fila 2, la reina 2 en la fila 4 ...).  Mientras que el vector {1,1,1,1} representaría la siguinte configuraciónde tablero.

Los tableros anteriores fueron creados con la instrucciónes GraphichsGrid, Graphics y Disk

Graphics[primitivas,opciones]		representa una imagen de dos dimensiones.

Algunas de las primitivas posibles son:

({{      , Arrow[{{(Subscript[x, 1]),(Subscript[y, 1])},…}], Flecha }, {      , BezierCurve[{(Subscript[pt, 1]),(Subscript[pt, 2]),…}], Curva Bézier}, {      , BSplineCurve[{(Subscript[pt, 1]),(Subscript[pt, 2]),…}], Curva B-spline}, {      , Circle[{x,y},r], Circulo }, {      , Disk[{x,y},r], Disco relleno }, {▪, FilledCurve[{(Subscript[seg, 1]),(Subscript[seg, 2]),…}], Curva rellena}, {      , Inset[obj,…], Objeto grafico}, {      , GraphicsComplex[pts,prims], Objetos graficos complejos }, {      , GraphicsGroup[{(Subscript[g, 1]),(Subscript[g, 2]),…}], Objetos seleccionables como groupo}, {▪, JoinedCurve[{(Subscript[seg, 1]),(Subscript[seg, 2]),…}], Curva por segmentos}, {      , Line[{{(Subscript[x, 1]),(Subscript[y, 1])},…}], Linea }, {      , Point[{x,y}], Punto }, {      , Polygon[{{(Subscript[x, 1]),(Subscript[y, 1])},…}], Poligono }, {      , Raster[array], Arreglo de cuadrados coloreados o grises }, {      , Rectangle[{(Subscript[x, min]),(Subscript[y, min])},{(Subscript[x, max]),(Subscript[y, max])}], Rectangulo }, {      , Text[expr,{x,y}], Texto }})

GraphicsGrid[{{(Subscript[g, 11]),(Subscript[g, 12]),…},…}]          Generaun grafico en el cual el elememto gij es 
                                                                               posicionado  en una rejilla bidimensional

GraphicsGrid[{{Graphics[Disk[]]}},Frame->All] (*Una fila, una columna *)

en el ejemplo anterior se define un grafico que contiene un obejto disco y se agrega a una rejilla de 1x1.

GraphicsGrid[{{Graphics[Disk[]]},{Graphics[Disk[]]}},Frame->All] (*Dos filas, una columna *)

en este  ejemplo se define un grafico que contiene dos obejtos disco y se agregan a una rejilla de 2x1.

GraphicsGrid[{{Graphics[],Graphics[Disk[]]},{Graphics[Disk[]],Graphics[]}},Frame->All] (* Dos filas, dos columnas *)

aquí se define una rejilla de 2x2 con  objetos discos en las posiciones (1,2) y (2,1). Y objetos vacios en las posisciones (1,1) y (2,2).

La instrucción para el tablero de la primera figura rquiere de una rejilla de 4x4 y objetos disco en las posiciones (1,3), (2,1),(3,4)  y (4,2).

definiendo primero una lista de objetos  vacios de 4x4:

ArregloDeObjetos={{Graphics[],Graphics[],Graphics[],Graphics[]},{Graphics[],Graphics[],Graphics[],Graphics[]},{Graphics[],Graphics[],Graphics[],Graphics[]},{Graphics[],Graphics[],Graphics[],Graphics[]}};

para ponerlo en la rejilla

GraphicsGrid[ArregloDeObjetos,Frame->All]

Agregar el disco en la posción (1,3):

ArregloDeObjetos[[1,3]]=Graphics[Disk[]];

GraphicsGrid[ArregloDeObjetos,Frame->All]

en la posción (2,1)

ArregloDeObjetos[[2,1]]=Graphics[Disk[]];
GraphicsGrid[ArregloDeObjetos,Frame->All]

Ejercicio: Agregar las dos fichas faltantes

Se pueden definir todo el objeto a la vez:

ArregloDeObjetos1={{Graphics[],Graphics[],Graphics[Disk[]],Graphics[]},{Graphics[Disk[]],Graphics[],Graphics[],Graphics[]},{Graphics[],Graphics[],Graphics[],Graphics[Disk[]]},{Graphics[],Graphics[Disk[]],Graphics[],Graphics[]}};
GraphicsGrid[ArregloDeObjetos1,Frame->All]

Ejercicio: Implementar una función CreaTablero la cualdada una representación como vector de n elementos para una configuración de las n reinas sobre un tablero, regrese la versión grafica equivalente.

CreaTablero[{l__Integer}]:=Module[{T=List[l],n},
	n=Length[T];
GraphicsGrid[Table[Table[If[T[[i+1]]==j ,Graphics[Disk[]],Graphics[]], {i,0,n-1}],{j,0,n-1}],Frame->All]
]

Calculando el número de ataques

Para una configuración de tablero dada se pueden determinar el número de ataques prcomo sigue:  se cuentan el número de reinas que comparten la misma fila nf,  y el número de reinas que comparten la diagonal nd y el número de ataques será la suma de nf-1+nd el términos -1 es debido a que cada reina no se ataca a si misma (observe que el número de ataques es simetrico así que si la (Subscript[reina, k]) ataca a la (Subscript[reina, l])ocurre también que la (Subscript[reina, l]) ataca a la (Subscript[reina, k])pero podemos contar solo uno de los ataques).  Para  calcular el número de ataques de fila nf basta con contar los grupos de elementos repetidos que hay en el vector. En el caso de los ataques en diagonal observese que la (Subscript[reina, k])ataca a la (Subscript[reina, l  ])si el los indices  ((Subscript[i, k]),(Subscript[j, k])) tienen una relación del tipo |(Subscript[i, l])-(Subscript[i, k])|=(Subscript[c, i]) y  |(Subscript[j, l])-(Subscript[j, k])| = (Subscript[c, j]) y (Subscript[c, i])=(Subscript[c, j]) .  Por ejemplo en la siguiente figura la (Subscript[reina, 1])ataca en diagonal a la (Subscript[reina, 2])y (Subscript[reina, 3]). Los indices (i,j) de la (Subscript[reina, 1])  son (1,2), de la (Subscript[reina, 2])(2,1) y (3,4) para la (Subscript[reina, 3]).  Para las reinar uno y dos se tiene que (Subscript[c, i])=|1-2|=1   y  (Subscript[c, j])=|2-1|=1  lo mismo ocurreo para la reina 3 solo que con (Subscript[c, i])=(Subscript[c, j])=2

Ejercicio: Implementar una función que cuente el número de ataques en una configuración de tableto dada. Recuerde que en nuestra representación como vector la reinas solo se mueven sobre las columnas por lo que el valor de i,  para un reina en particular siempte será el mismo y depende el indice del elemento.  Hint:  implemente un método que evalue dos reinas se atacan basaso en sus respectivos indices i,j y después aplique esa función a cada posible par (recuerde la simetria de los ataques)

SeAtacan[{{i_,j_},{l_,k_}}]:=If[i==l || Abs[i-l]==Abs[j-k] , True, False]; (* Prueba si dos reinas en la posición (i,j) y (l,k) se atacan *)

Ataques[{l__Integer}]:=Module[{x=List[l]},
	(*Se convierte la notación {i0,i1,...,in} a {{i0,j0},{i1,j1},...,{in,jn}}*)
	x=Map[Function[i,{x[[i]],i-1}],Range[Length[x]]]; 
	(*Se calculan todos lo posibles pares {{i,j},{k,l}} recuerde que el par {{i,j},{k,l}} es el mismo que {{k,l},{i,j}} *)
	x= Map[Function[i, Map[{x[[i]],#}&, Take[x,i-Length[x]]]],Range[Length[x]-1]];
	(* Se cuentan el número de ataques*)
	Count[Flatten[Map[SeAtacan,x,{2}]],True]	
]

Ataques[{0,2,0,3}]

x=Map[Function[i,{x[[i]],i-1}],Range[Length[x]]]

Map[{x[[3]],#}&, Take[x,3-Length[x]]]

CreaTablero[{0,2,0,3}]

Ataques[{0,2,0,3}]

CreaTablero[{1,3,0,2}]

Ataques[{1,3,0,2}]

Generar hijos

Para generar los hijos (posibles siguiente estados) dada nuestra representación como vector solo debemos incrementar uno de los elementos del vector, esto sin superar el valor de n (tamaño del tablero). Si asumimos que las reinas se mueven de un salto a la vez, cada posible configuración tiene a lo más n  posibles hijos.  Un ejemplo de una función que calcule los hijos e la siguiente:

GeneraHijos[{l__Integer}]:=Block[{R,r,n}, 
	r=List[l];
	n=Length[r];
	R=Map[ReplacePart[r,#->r[[#]]+1]&, Range[n]];
	R
]

GeneraHijos[{0,0,3,0}]

{{1,0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1}}

La función previa no verifica si el valor de cada elemento del vector supera la el valor máximo de n.

GeneraHijos[{0,0,0,3}]

No puede haber una reina en la posición 5, ya que el tablero sólo tiene 4 posibles posiciones. El resultado correcto deberia ser 
{{1,0,0,3},{0,1,0,3},{0,0,1,3}}

Ejercicio: Modifique el método para que no genere hijos que se salgan del rango.

GeneraHijosN[{l__Integer}]:=Block[{R,r,n}, 
	r=List[l];
	n=Length[r];
	R=Map[If[r[[#]]+1<n,ReplacePart[r,#->r[[#]]+1]]&, Range[n]];
	Delete[R,Position[R,Null]]
]

f=GeneraHijosN[{0,0,0,0}]

FreeQ[f,{1,0,0,0}]

Búsqueda a lo profundo

Ahora implementaremos búsqueda por profundidad, para esto es necesario utilizar un lista como si fuera una pila. Sólo tiene que utilizar una lista en la que insertamos y borramos en el mismo extermo.

El siguiente código define una posible implementación para el algoritmo de búsqueda por profundidad para el problema de las N-Reinas

BusquedaPorProfundidadNQ[n_,maxiter_:1000000]:=Module[{pila={},fringe={},current=Table[0,{n}],i=0},
(* n es el tamaño del tablero
maxiter establece el número maximo de iteraciones
*)
pila=Join[{current},pila];  (*se utiliza una pila para formar a los hijos*)
While[Ataques[current]>0 && i<maxiter&&  Length[pila]>0, (* se itera mientras el tablero tenga ataques, no se haya alcanzado el número máximo de iteraciones y la pila no éste vacia (se exploraron todas la soluciones posibles, como en el caso de n=3)*)
current=First[pila];(*se toma elemento en el tope de la pila*)
pila=Take[pila,1-Length[pila]]; (*se elimina el elemento en el tope de la pila*)
fringe=Join[fringe,{current}];(* se agrega al fringe el elemento evaluado *)
pila=InsertaHijos[pila,current,fringe]; (* se forman en la pila los hijos del elemento evaluado *)
i=i+1];
Print[Length[fringe]];
current
]

Ejercicio:  Implementar insertaHijos, recuerde que éste no debe insertar hijos que ya esten el fringe y/o en la pila

InsertaHijos[p_,c_,f_]:=Module[{pila=p,fringe=f,current=c,hijos},
	hijos=GeneraHijosN[current];
         Map[If[ FreeQ[fringe,#] && FreeQ[pila,#], pila=Join[{#},pila]]&,hijos];
	pila
	
]

InsertaHijosN[p_,c_,f_]:=Module[{pila=p,fringe=f,current=c,hijos,n=1},
	hijos=GeneraHijosN[current];
	While[n<=Length[hijos], If[ FreeQ[fringe,hijos[[n]]] && FreeQ[pila,hijos[[n]]], pila=Join[{hijos[[n]]},pila]]; n++
];
pila	
]

BusquedaPorProfundidadNQ[4]

Ejercicos de autoevaluación:

1. Crear un método o modificar BusquedaPorProfundidadNQ para que utilizando un manipulate muestre todos los tableros evaluados
2. Crear una función que implemente búsqueda por amplitud (BusquedaPorAmplitudNQ) para el problema de las n reinas. 
3. Implementar funciones BusquedaCiega  general, que pueda realizar búsqueda sobre cualquier espacio. ya sea por profundidad o por amplitud.  Hint: debe pasar como párametros a la función que genera los elementos del espacio de búsqueda, la función que evalua si un elemento dado es o no una solución para el problema, la función que forma los elementos y el estado inicial.

InsertaHijos[{},{0,0},{{0,0}}]

InsertaHijos[{{1,0},{1,1}},{0,1},{{0,0},{0,1}}]

Print["algo: ",2]