8 reinas en un tablero de ajedrez sin que se ataquen entre si

Alguna vez alguien me dijo, ¿puedes acomodar 8 reinas en un tablero de ajedrez sin que se ataquen?, lo intente, y despues de unas cuantas horas y de repetidos errores logré acomodarlas. Hoy les voy a enseñar como ésto puede ser mucho más rápido usando programación.

Sabemos que la reina se puede mover asi:

Movimientos de la reina

Entonces una de las formas que hay para que esten 8 reinas en un tablero de ajedrez es la siguiente:

[kml_flashembed movie="http://blog.amarello.com.mx/wp-content/uploads/2007/01/reinas.swf" height="550" width="550" /]

No voy a explicar línea por línea pero la idea general es que visualizemos todo en diferentes arrays o arreglos o matrices o como le quieran llamar, pensando que un tablero mide 8 x 8 entonces hacemos una matriz de 8 x 8 en la cual solamente tenga un número, hacemos que un bucle o ciclo pase por cada una de las posiblidades (fila, columna) (0,0), (0,1), (0,2)….(2,1), (2,2)….. (6,7),(7,0)…(7,7) asi que va a haber 8×8 = 64 posibles casillas, lo que haremos es que todas las casillas valgan cero en un principio, entonces ponemos la primer reina en (0,0) cambiandole el valor de 0 que tienen todas las casillas inicialmente a uno para marcar que hay una reina y le restamos uno a cada una de las casillas que puede atacar.

ataque1.jpg

Luego seguimos casilla por casilla hasta que encontremos la siguiente que no esta siendo atacada por la reina1 (o sea que vale cero) y ponemos ahi la siguiente reina cambiandole el valor a 1 y volvemos a restarle uno a cada una de las posibles casillas que ataca la reina2, esta marcado en negritas las casillas que he cambiado para que las vean más fácil.

ataque2.jpg

El caso es que se siguen poniendo reinas hasta que se acabe el tablero, y probablemente al primer intento no podemos llenarla bien, cuando pasa ésto lo que hacemos es regresarnos a la reina anterior y en lugar de dejarla en el primer cero la movemos al siguiente y asi intentamos hasta que llegue a la que debe de ser.

Tal vez sea un poco dificil para algunos de darse cuenta de lo que digo, pero la idea es como si estuvieramos crackeando un password, o sea adivinandolo empezamos con aaaa, luego aaab, luego aaac, asi hasta que en algun momento llegamos a aaaz y sigue sin funcionar asi que cambiamos la letra anterior y seguimos aaba, aabb, y hasta que llegamos a la aabz, y cambiamos a aaca, y asi una por una hasta que en algun momento encontramos el password que era por ejemplo beto, para llegar a este tendríamos que probar una por una de las posibilidades que realmente serían muchísimos calculos, a este método se le conoce como “fuerza bruta”, lo mismo hacemos con las reinas ir probando una por una hasta que en algun momento las 8 reinas esten en el tablero y podamos cambiar el 8tavo cero a un uno para indicar, es ahi cuando termina el programa.

Ésto lo programé hace unos años, creo que no es la mejor forma de hacerlo, tal vez luego pondré un código en java que tome muchisimo menos tiempo que éste de actionscript, pero pues esta es la idea:
Código en ActionScript (también podría funcionar en JavaScript)

tablero = new Array(
new Array(), 
new Array(), 
new Array(), 
new Array(), 
new Array(), 
new Array(), 
new Array(), 
new Array()
);

restricciones = new Array();
var cosa = new Array();
var solucion = 0;
var limite = 0;
var reinas = 0;
for (i=0; i<8; i++) {
	for (k=0; k<8; k++) {
		tablero[i][k] = 0;
	}
	restricciones[i] = -1;
	cosa[i] = "";
}
for (i=0; i<8; i++) {
	for (k=0; k<8; k++) {
		if (restricciones[i]<k && tablero[i][k] == 0) {
			tablero[i][k] = 1;
			if (i == 7) {
				return 0;
			}
			for (x=0; x<8; x++) {
				if (x != k) {
					tablero[i][x]--;
				}
				if (x != i) {
					tablero[x][k]--;
				}
			}
			y = i;
			for (x=k; x<8; x++) {
				if (tablero[y][x]<=0) {
					tablero[y][x]--;
				}
				y++;
			}
			y = i;
			for (x=k; x>=0; x--) {
				if (tablero[y][x]<=0) {
					tablero[y][x]--;
				}
				y--;
			}
			y = i;
			for (x=k; x>=0; x--) {
				if (tablero[y][x]<=0) {
					tablero[y][x]--;
				}
				y++;
			}
			y = i;
			for (x=k; x<8; x++) {
				if (tablero[y][x]<=0) {
					tablero[y][x]--;
				}
				y--;
			}
			break;
		} else if (k == 7) {
			restricciones[i] = -1;
			i--;
			
			for (k=0; k<8; k++) {
				if (tablero[i][k]>0) {
					for (x=0; x<8; x++) {
						if (x != k) {
							tablero[i][x]++;
						}
						if (x != i) {
							tablero[x][k]++;
						}
					}
					y = i;
					for (x=k; x<8; x++) {
						if (tablero[y][x]<0) {
							tablero[y][x]++;
						}
						y++;
					}
					y = i;
					for (x=k; x>=0; x--) {
						if (tablero[y][x]<0) {
							tablero[y][x]++;
						}
						y--;
					}
					y = i;
					for (x=k; x>=0; x--) {
						if (tablero[y][x]<0) {
							tablero[y][x]++;
						}
						y++;
					}
					y = i;
					for (x=k; x<8; x++) {
						if (tablero[y][x]<0) {
							tablero[y][x]++;
						}
						y--;
					}
					tablero[i][k] = 0;
					restricciones[i] = k;
				}
			}
			k = -1;
		}
	}
}

Cabe destacar que el flash que se muestra aqui realmente lo hace en tiempo real, no es una imagen ni nada, sino usa éste código para hacerlo, es muy rápido porque realmente no son tantos calculos pero pues si tuvieramos una computadora muy lenta veríamos que se detiene un poco todo para hacer calculos.

Commentarios (7)
  1. Pepelu

    25 noviembre 2006

    Hola,

    Este comentario es para decirte que publico un par de blogs de ajedrez que agradecería que enlazases desde tu blog. Los blogs son:

    Compuntoes – Noticias de ajedrez.

    y

    Problemas de Ajedrez.

    De ser posible me gustaría que para el blog de noticias usaras para el anchor del enlace sólo la palabra “compuntoes” y si quieres indicar que se trata de un blog de noticias de ajedrez, este dato lo pusieras fuera del anchor tal y como yo he hecho en este comentario.

    Si puedo ayudarte en algo sólo tienes que decírmelo poniendo un comentario en el blog de problemas.

    Saludos y gracias,
    Pepelu.

  2. eduardo

    25 noviembre 2006

    Gracias por tu comentario, estarémos atentos a tu blog, y estamos pensando hacer una sección más adelante de vínculos de nuestros lectores, ahí tendremos un lugar para tus blogs, y de todas maneras estaremos checando tus bogs por si algo nos llama la atención, gracias.

  3. Seth

    2 diciembre 2006

    epa! me gustan estos tipos de posts que hacen en relación al ajedrez, igual y es porque me gusta este interente juego de estrategia y ociosidad.

    Saludos!

  4. Paco

    2 diciembre 2006

    Uy Seth entonces eres igual de ocioso para este juego que nosotros…

    A ver que día jugamos una partida, po lo menos en yahoo games. Nosotros desde hace mucho no jugamos y por lo tanto hemos perdido práctica, pero esto es reto formal :D .

  5. Juan Cabrera

    19 noviembre 2007

    Hola a todos
    por favor necesito ayuda para hacer el juego de las ocho reinas en netbeans si alguien me pude enviar el codigo del juego se lo agradeceria mucho

  6. Fher

    25 junio 2008

    Hola, xfa necesito ayuda en la definicion de matrices en JS, de NxM.. con datos y vacias… xfavor.. cualquier ayuda es importante y urgente.. gracias.. gracias

  7. Lyagushkka

    11 septiembre 2009

    Who knows where to download XRumer 5.0 Palladium?
    Help, please. All recommend this program to effectively advertise on the Internet, this is the best program!

Deja un comentario