• Author / Uploaded
• Abraham Garcia

• Categories
• Ajedrez
• Algoritmos
• Matemáticas Aplicadas
• Informática
• Tecnología

Citation preview

Juego de las 4 Reinas Para solucionar esto es necesario implementar una técnica básica llamada búsqueda en profundidad o búsqueda en anchura, que consiste en explorar las diferentes opciones de forma ordenada con el fin de obtener una solución a nuestro problema. La regla es la misma que en el ajedrez, las reinas comen en horizontal en vertical y diagonal. El objetivo es colocar n reinas en un tablero de NxN sin que se maten. Condición inicial en el punto 1-1 porque es más sencillo iniciar en orden que con métodos aleatorios. Solución: •

Paso 1: en el nivel 1 siendo y los movimientos verticales se suma 1 ya que se comienza en colocar la primera reina en 1-1. 1 2 3 4

•

2

3 4

Paso 2: en el nivel siguiente es necesario buscar la primera posición x en horizontal donde sea posible colocar una reina y sumar un nivel en y. 1 2 3 4

•

1 R

1 R

2

3

4 R

Paso 3: si no se puede obtener una solución es necesario restar un nivel borrar la reina del lugar donde se colocó anteriormente y probar con la siguiente opción de X y repetir el paso 2 y 3. 1 2 3 4

1 2 3 4 Se repiten de nuevo los pasos:

1 R

2

3

4 R

R

1 R

2

3

4 R

R

1 1 2 3 4

2 R

3

4 R

R

Por ende, la solución final será: 1 1 2 3 4

2 R

3

4 R

R R

Este metido no asegura la solución más optima, pero garantiza una solución y se puede implementar para buscar la salida de un lugar o plantear una ruta para llegar a un lugar no solo para solucionar el juego de colocar n reinas en un tablero de NxN.

Árboles: •

Primero en Profundidad: Inicio

3

2

1

Dirección del barrido

4

1 3

4

4

2 2

1

3

•

Primero en Anchura: Inicio

Dirección de Barrido

3

1

2

3

4

4

4

1

1

2

1

4

3

2

1

2

Pseudocódigo: El código en Prolog que resuelve el juego de las 4 reinas es: domains lista=integer* predicates rango(integer, integer, lista) nondeterm dame(integer, lista, lista) nondeterm permuta(lista, lista) atacada(integer, integer, lista) correcta(lista) nondeterm reina(integer, lista) clauses rango(N, N, [N]):-!. rango(N, M, [N|Cola]):-N