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);
}
}
}
}
