ALGORITMO 8 REINAS
Páginas: 2 (340 palabras)
Publicado: 5 de marzo de 2014
ALGORITMO 8 REINAS
Sabiendo el movimiento de la pieza de la reina en un tablero de ajedrez encontrar las posiciones de 8 reinas en el mismo tablero para que ninguna pueda comer a las otras 7 ypor tanto tampoco ser comida. (Investigando un poco encuentro que para este problema clásico hay 92 soluciones)
Primera valoración del ejercicio
No se puede repetir fila ni columna
No se puede repetir diagonal
En cada fila solo 1 reina
En cada columnasólo 1 reina
Marcar filas y columnas ocupadas
El algoritmo se podría definir con dos líneas como.
“Probar a colocar la reina de la fila i-ésima en cada una de las posiciones disponibles.”“Colocar las reinas restantes operando de modo recursivo.”
Estado Inicial
Las reinas que hay
Estado final
Las posiciones que quedan libres
Procesamiento
Colocar ficha en lugar permitido y noocupado
ENT Columnas ocupadas por vacías anteriores
SALIDA Columnas disponibles
Creación del pseudocódigo
Disponibles(ocup). //recibe un vector o una lista con
d=[0,1,2,3,4,5,6,7]
k=tamaño(ocup)
Para cada c en ocup:
Eliminar c de d
Eliminar (c+k) de d
Eliminar (c-k) de d
K - -
devolver d
caso concreto
ocup=[3 5 0 4]
k=4 3 2 1
d=[0 1 2 3 4 5 6 7]
Date: 2010-07-29IMPLEMENTACIÓN ALGORITMO 8 REINAS EN JAVA
Implementamos el método disponibles y comprobamos si funciona para un caso concreto.
import java.util.Iterator;
import java.util.LinkedList;
importjava.util.List;
/** * @author nessy* */
public class OchoReinas {
//PSEUDOCODIGO
// Disponibles(ocup). //recibe un vector o una lista con
// d=[0,1,2,3,4,5,6,7]
// k= tamaño(ocup)
// Paracada c en ocup:
// Eliminar c de d
// Eliminar (c+k) de d
// Eliminar (c-k) de d
// K - -
// devolver d
/**Este método sirve para determinar las columnas en las que
* se...
ALGORITMO 8 REINAS
Sabiendo el movimiento de la pieza de la reina en un tablero de ajedrez encontrar las posiciones de 8 reinas en el mismo tablero para que ninguna pueda comer a las otras 7 ypor tanto tampoco ser comida. (Investigando un poco encuentro que para este problema clásico hay 92 soluciones)
Primera valoración del ejercicio
No se puede repetir fila ni columna
No se puede repetir diagonal
En cada fila solo 1 reina
En cada columnasólo 1 reina
Marcar filas y columnas ocupadas
El algoritmo se podría definir con dos líneas como.
“Probar a colocar la reina de la fila i-ésima en cada una de las posiciones disponibles.”“Colocar las reinas restantes operando de modo recursivo.”
Estado Inicial
Las reinas que hay
Estado final
Las posiciones que quedan libres
Procesamiento
Colocar ficha en lugar permitido y noocupado
ENT Columnas ocupadas por vacías anteriores
SALIDA Columnas disponibles
Creación del pseudocódigo
Disponibles(ocup). //recibe un vector o una lista con
d=[0,1,2,3,4,5,6,7]
k=tamaño(ocup)
Para cada c en ocup:
Eliminar c de d
Eliminar (c+k) de d
Eliminar (c-k) de d
K - -
devolver d
caso concreto
ocup=[3 5 0 4]
k=4 3 2 1
d=[0 1 2 3 4 5 6 7]
Date: 2010-07-29IMPLEMENTACIÓN ALGORITMO 8 REINAS EN JAVA
Implementamos el método disponibles y comprobamos si funciona para un caso concreto.
import java.util.Iterator;
import java.util.LinkedList;
importjava.util.List;
/** * @author nessy* */
public class OchoReinas {
//PSEUDOCODIGO
// Disponibles(ocup). //recibe un vector o una lista con
// d=[0,1,2,3,4,5,6,7]
// k= tamaño(ocup)
// Paracada c en ocup:
// Eliminar c de d
// Eliminar (c+k) de d
// Eliminar (c-k) de d
// K - -
// devolver d
/**Este método sirve para determinar las columnas en las que
* se...
Leer documento completo
Regístrate para leer el documento completo.