Página 1 de 1

Problema de las 1000 Reinas

NotaPublicado: 09 Sep 2017 22:49
por andres
He leido este articulo sobre el problema de las damas que no se pueden comer
entre si,la diferencia es que no son 8 sino mil damas.Dejo este Link por si no conoceis
la noticia .

https://elpais.com/elpais/2017/09/04/ci ... 82169.html

Re: Problema de las 1000 Reinas

NotaPublicado: 11 Sep 2017 17:43
por Kupelwieser
Gracias Andres, muy interesante! Un saludo.

Re: Problema de las 1000 Reinas

NotaPublicado: 11 Sep 2017 22:21
por andres
Hola Kupelwieser,

¿Crees que tendra solucion ? Un millon de dolares es un buen premio. Intentare poner un mate con 7 piezas un poco largo ,mas de 500 movimientos (demasiado para nosotros ),.https://timkr.home.xs4all.nl/chess2/diary.htm

Saludos Andres.

Re: Problema de las 1000 Reinas

NotaPublicado: 13 Sep 2017 08:36
por Kupelwieser
Hola Andrés. Me parece que el problema de las reinas, tal como se contó en la prensa, está muy simplificado para que el público en general lo entienda, pero lo que se busca es una solución al caso general (y eso es mucho más complicado). Saludos!

Re: Problema de las 1000 Reinas

NotaPublicado: 16 Sep 2017 22:26
por Moztruitu
Debe ser una noticia sensacionalista, el problema se resolvió hace mucho y está publicado en la wikipedia.

https://es.wikipedia.org/wiki/Problema_de_las_ocho_reinas

De hecho aquí está el código en c++ para hacerlo con las reinas que quieras.

Código: Seleccionar todo
#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define NREINAS 8 // dimensiones del tablero y número de reinas
using namespace std;
vector<int> sol;
int nro_sol=1;


inline bool contiene(const vector<int>& v, const int val)
{
    return find(v.begin(), v.end(), val) != v.end();
}

void reinas(int k, vector<int> col, vector<int> diag45, vector<int> diag135)
{
    if( k == NREINAS )
    {
   printf("%3d:", nro_sol++);
        for(int j=0; j<NREINAS; j++)
       cout << " (" << j+1 << "," << sol[j] << ")";
        cout << endl;
    }
    else
    {
        for(int j=1; j<=NREINAS; j++)
            if( !contiene(col, j) && !contiene(diag45, j-k) && !contiene(diag135, j+k) )
            {
                sol[k] = j;

                col.push_back(j);
                diag45.push_back(j-k);
                diag135.push_back(j+k);

                reinas(k+1,col, diag45, diag135);

                col.pop_back();
                diag45.pop_back();
                diag135.pop_back();
            }
    }
}

int main() {
    cout << "SOLUCIONES AL PROBLEMA DE LAS " << NREINAS << " REINAS"<<endl;
    sol.resize(NREINAS);
    reinas(0, vector<int>(), vector<int>(), vector<int>());

    return 0;
}


Debe ser de estas noticias que se traducen mal del inglés o parecido, convendría saber cual es la noticia original porque lo mismo ni hay un millón de premio.

Re: Problema de las 1000 Reinas

NotaPublicado: 17 Sep 2017 11:51
por andres
Hola Moztruitu.
Si el problema ya esta resuelto, el Pais ha tenido un fallo al dar la informacion ( atribuida al Instituto Clay de Matematicas ) sin comprobar que ya se soluciono. Saludos Andres.