1

Estaba aburrido y hacia rato que no usaba C, así que agarré un ejercicio para calentar los motores, me puse a resolver el problema de las 8 reinas (consiste en encontrar todas las posiciones posibles en las que N reinas están en un tablero de NxN sin amenazarse entre sí).

En principio creí que todo había salido bien, el programa me mostraba un montón de resultados, revisé algunos en parteas aleatorias de la lista que devolvió y todos estaban bien, para saber exactamente cuantos resultados encontró mi programa puse un contador, después de ejecutar revisé el contador y este tenía un valor de 260, googlee cuantos resultados posibles había y resulta que solo hay poco más de 90 soluciones posibles (12 soluciones y sus variaciones rotadas y trasladadas).

Estuve revisando el código y los resultados pero no encuentro errores en el código ni en los resultados.

¿Existe la posibilidad de que haya más resultados posibles de los que Wikipedia dice?

¿O será que hay algún error en mi código?

#include <iostream>
#include <stdlib.h>
#include <windows.h>

using namespace std;


int tablero[8][8];

int contador_tableros = 0;

void inicializar();
void mostrar_tablero();
void principal(int);
bool colocar(int, int);


int main(){
    principal(0);
    system("pause");
    return 0;
    
}

bool colocar(int a, int b){
    int aux = 1;
    //diagonal superior izquierda
    while (a-aux >= 0 && b-aux >= 0){
        if(tablero[a - aux][b - aux] == 1){
            return false;
        }
        aux ++;
    }
    
    //diagonal superior derecha
    aux = 1;
    while (a-aux >= 0 && b+aux <= 7){
        if(tablero[a - aux][b + aux] == 1){
            return false;
        }
        aux++;
    }
    
    //diagonal inferior izquierda
    aux = 1;
    while (a+aux <= 7 && b-aux >= 0){
        if(tablero[a + aux][b - aux] == 1){
            return false;
        }
        aux++;
    }
    
    //diagonal inferior derecha
    aux = 1;
    while (a+aux <= 7 && b+aux <= 7){
        if(tablero[a + aux][b + aux] == 1){
            return false;
        }
        aux++;
    }
    
    //marcar rectas
    
    //sup
    aux = 1;
    while(a - aux >= 0){
        if(tablero[a - aux][b] == 1){
            return false;
        }
        aux++;
    }
    
    //inf
    aux = 1;
    while(a + aux <= 7){
        if(tablero[a + aux][b] == 1){
            return false;
        }
        aux++;
    }
    
    //izq
    aux = 1;
    while(b - aux >= 0){
        if(tablero[a][b - aux] == 1){
            return false;
        }
        aux++;
    }
    //der
    aux = 1;
    while(b + aux <= 7){
        if(tablero[a][b + aux] == 1){
            return false;
        }
        aux++;
    }
    
    return true;
}

void inicializar(){
    for (int i = 0; i<8 ; i++){
        for (int j = 0 ; j < 8 ; j++){
            tablero[i][j] = 0;
        }
    }
}

void mostrar_tablero(){
    for (int i = 0; i<8 ; i++){
        for (int j = 0 ; j < 8 ; j++){
            cout<<" ";
            switch (tablero[i][j]){
                case 0: cout << "-"; break;
                case 1: cout << "R"; break;
                default: cout << tablero[i][j]; break;
            }
            
        }
        cout<<endl;
    }
}

void principal(int nreina){
    for (int i=0; i<=8 ; i++){
        if (i>0) tablero[i - 1][nreina] = 0;
        if(colocar(i, nreina)){
            tablero[i][nreina] = 1;
            
            if(nreina == 7){
                mostrar_tablero();
                Sleep(10);
                contador_tableros++;
                cout<<endl<<contador_tableros<<endl;
            }
            else{
                principal(nreina + 1);
            }
        }
        
    }
}
2
  • 1
    Pues si que hay error en tu código, de eso no hay duda. Matemáticamente hablando sólo existen 92 posibilidades de las cuales 12 son únicas e irrepetibles (distintas) para un tablero de tamaño 8x8. el 7 jul. 2020 a las 8:35
  • 4
    Así sin mirar mucho, en la función principal haces un for de 0 hasta 8 (incluido porque la condición es <=) y tu array es de 8x8, con lo que te estás saliendo fuera del array. Pero tampoco he seguido el código. Te recomiendo depurar.
    – SuperG280
    el 7 jul. 2020 a las 8:54

2 respuestas 2

5

Estás contando como solución al problema de las 8 reinas soluciones que tienen menos de 8 reinas, en concreto tus soluciones:

1 3 4 5 7 8 9 10 11 13 15 16 17 18 19 20 22 23 26 29 30 32 33 35 36 37 38 39 41 42 43 45 50 54 58 59 61 62 64 65 66 67 68 69 71 72 74 75 76 77 78 98 101 102 103 104 106 107 108 109 113 115 116 117 118 119 122 124 125 126 127 128 129 130 133 134 135 136 140 141 143 144 145 146 147 148 149 151 153 154 155 157 158 159 161 163 164 165 168 169 171 172 175 176 177 178 179 181 182 185 187 188 189 191 193 195 197 198 199 200 201 202 203 205 206 207 209 210 212 215 216 217 218 219 220 221 222 223 224 225 226 227 230 231 232 233 234 236 237 238 239 241 242 243 244 245 247 248 249 250 251 252 254 256 257 258 259 260

Descontadas las soluciones incorrectas, tienes 92.

Otras cosas a tener en cuenta

  • Estás programando en C++, así que no debes incluir la cabecera <stdlib.h> que por otro lado no usas. Lee este hilo para saber más.

  • No necesitas inicializar "manualmente" el tablero con un bucle en una función, puedes añadir llaves vacías a tu formación y se inicializará toda a cero.

    int tablero[8][8]{};
    
  • Es una mala práctica usar variables globales, evita hacerlo. Lee este hilo para saber más.

  • Favorece el pre-íncremento frente al post-incremento. Lee este artículo para saber más.

  • No abuses de std::endl. Lee este hilo para saber más.

  • No abuses de using namespace std o si lo usas, que sea en el ámbito lo más pequeño posible. Lee este hilo para saber más.

1
2

Hay dos errores:

 for (int i=0; i<=8 ; i++){  

Debe ser 7.

 tablero[i][nreina] = 1;

Necesitas eliminar una reina antes de ponerla en el siguiente cuadrado. Esta linea

 if (i>0) tablero[i - 1][nreina] = 0;

intenta hacer eso, pero es incorrecta. Una manera correcta es

    if(colocar(i, nreina)){
        tablero[i][nreina] = 1; // poner
        ...
        ...
        tablero[i][nreina] = 0; // eliminar
    }

Estos dos correcciones resultan en 92 soluciones.

1

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.