ClubEnsayos.com - Ensayos de Calidad, Tareas y Monografias
Buscar

PROBLEMA DE LAS 8 REINAS


Enviado por   •  19 de Noviembre de 2018  •  Ensayos  •  3.507 Palabras (15 Páginas)  •  276 Visitas

Página 1 de 15

[pic 1]

SIMULACION DE SISTEMAS

Problema de las 8 reinas

[pic 2][pic 3]


PROBLEMA DE LAS 8 REINAS

El problema de las ocho reinas es un pasatiempo que consiste en poner ocho reinas en el tablero de ajedrez sin que se amenacen. Fue propuesto por el ajedrecista alemán Max Bezzel en 1848[cita requerida]. En el juego del ajedrez la reina amenaza a aquellas piezas que se encuentren en su misma fila, columna o diagonal. El juego de las 8 reinas consiste en poner sobre un tablero de ajedrez ocho reinas sin que estas se amenacen entre ellas. Para resolver este problema emplearemos un esquema vuelta atrás (o Backtracking).

Como cada reina puede amenazar a todas las reinas que estén en la misma fila, cada una ha de situarse en una fila diferente. Podemos representar las 8 reinas mediante un vector[1-8], teniendo en cuenta que cada índice del vector representa una fila y el valor una columna. Así cada reina estaría en la posición (i, v[i]) para i = 1-8.

[pic 4]

Ejemplo de dos reinas amenazadas en el tablero de 4 por 4.

El vector { (3,1,6,2,8,6,4,7} significa que la reina 1 esta en la fila 3, columna 1; la reina 2 en la fila 1, columna 2; la reina 3 en la fila 6, columna 3; la reina 4 en la fila 2, columna 4; etc... Como se puede apreciar esta solución es incorrecta ya que la reina 3 y la 6 estarían en la misma fila. Por tanto el vector correspondería a una permutación de los ocho primeros números enteros.

El problema de las filas y columnas lo tenemos resuelto, pero ¿qué ocurre con las diagonales? Para las posiciones sobre una misma diagonal descendente, se cumple que tienen el mismo valor { fila-columna} { fila-columna}; mientras que para las posiciones en la misma diagonal ascendente, se cumple que tienen el mismo valor { fila+columna} fila+columna}. Así, si tenemos dos reinas colocadas en posiciones { (i,j)} (i,j) y { (k,l)} { (k,l)} entonces están en la misma diagonal si y solo si cumple:

{ i-j=k-l} { i-j=k-l} o { i+j=k+l} { i+j=k+l}

{ j-l=i-k} { j-l=i-k} o { j-l=k-i} { j-l=k-i}

Teniendo en cuenta todas estas consideraciones, podemos aplicar el esquema retroactivamente para colocar las ocho reinas de una manera realmente eficiente. Para ello, reformulamos el problema como problema de búsqueda en un árbol. Decimos que en un vector { V_{1_ k} { V_{1_k} de enteros entre 1 y 8 es { k}-prometedor, para { 0<=k<= 8} { 0\leq k\leq 8} , si ninguna de las { k} k reinas colocadas en las posiciones { (1,V_{1}),(2,V_{2})…(k,V_{k})} { (1,V_{1}),(2,V_{2})….(k,V_{k})} amenaza a ninguna de las otras. Las soluciones a nuestro problema se corresponden con aquellos vectores que son 8-prometedores.

[pic 5]

Implementación

A continuación se muestra una posible implementación del anterior algoritmo en C++.

#include 

#include 

#include 

#include 

#include 

#define NREINAS 8 // dimensiones del tablero y número de reinas

using namespace std;

vector<int> sol;

int nro_sol=1;

inline bool contiene(const vector<int>& v, const int val)

{

    return find(v.begin(), v.end(), val) != v.end();

}

void reinas(int k, vector<int> col, vector<int> diag45, vector<int> diag135)

{

    if( k == NREINAS )

    {

        printf("%3d:", nro_sol++);

        for(int j=0; j<NREINAS; j++)

            cout << " (" << j+1 << "," << sol[j] << ")";

        cout << endl;

    }

    else

    {

        for(int j=1; j<=NREINAS; j++)

            if( !contiene(col, j) && !contiene(diag45, j-k) && !contiene(diag135, j+k) )

            {

                sol[k] = j;

                col.push_back(j);

                diag45.push_back(j-k);

                diag135.push_back(j+k);

                reinas(k+1,col, diag45, diag135);

                col.pop_back();

...

Descargar como (para miembros actualizados)  txt (15.9 Kb)   pdf (310.1 Kb)   docx (99.5 Kb)  
Leer 14 páginas más »
Disponible sólo en Clubensayos.com