EDICIóN GENERAL
158 meneos
4439 clics
El problema de las 1000 reinas. ¡Un millón de dólares en juego!

El problema de las 1000 reinas. ¡Un millón de dólares en juego!  

Investigadores de la Universidad de St. Andrews ofrecen una recompensa de un millón de dólares para quien pueda desarrollar un algoritmo que supere al viejo acertijo del ajedrez conocido como “el problema de las ocho reinas”.

| etiquetas: 1000 reinas , problema , ajedrez , recompensa , pnp
Si no hubiera discriminación positiva se movería una puta casilla y ya estaría resuelto.
#1 Uhmmmm, usando pensamiento lateral eh?, se puede?
¿Puede una partida normal de ajedrez llegar a 8 reinas (la original y 7 peones promocionados)?
#2 No creo que sea posible que tantos peones puedan llegar...
#2 Si claro. La última partida que tuve con una niña de 5 años, me llegó a coronar todos los peones, el osito, la figura del roscón y perdí la partida porque el perro se llevó mi rey. :-)
#4 Bueno, omití la parte "sin jugar solo, con animales o similar" pero crep que la palabra normal de mi comentario daba pistas. xD
#4 ¡ah!, la clásica maniobra del perro se lleva rey. Así es como Kasparov derrotó a Deep Blue la primera vez.
#22 Ya te digo, menudo listo estaba hecho el puto Kasparov >:-(
#2 No hay ninguna regla que lo impida, podrías tener nueve damas... o diez caballos. Pero desde luego no sería una partida "normal".
#9 Me surge la duda de tener en cuenta que el rey contrario no puede estar en jaque y llegará un momento con X reinas que sea casi imposible que no lo esté y eso teniendo en cuenta que las otras piezas no hayan caído.
#11 No necesariamente... el rey rival puede (o más bien debe) estar parapetado detrás de sus piezas.

De todad formas lo que esta gente pregunta tiene poco que ver con el ajedrez.

#10 De hecho el premio no es por conseguir una solución (eso es facilísimo). El premio es por diseñar un algoritmo generalizable para NxN que demuestre que funciona siendo aplicado a 1000 x 1000.... entre otras.
#11 Con 9 reinas colocadas en las 9 casillas de una esquina ya no hacen jaque a mucha zona del tablero.
A ver si lo puedo resolver yo. Ya. Siguiente problema
Cuando se da un premio de este tipo suele ser por uno de estos motivos.
1.- lo necesitan para resolver un problema que tienen.
2.- quieren saber si alguien es capaz de resolverlo porque les reventaría algún sistema criptográfico o similar.
#6 Realmente este es un problema concreto del problema ¿P = NP?, que es por lo que te dan un millón de leuros.

Hay problemas que (ahora mismo) no se pueden resolver en un tiempo polinomial, es decir, que siendo n los datos de entrada se tarda por ejemplo 2n segundos en resolverlo. Pero la comprobación del resultado tiene un coste polinómico, por ejemplo n segundos en realizar la comprobación.

La pregunta que subyace es si los algoritmos no polinómicos que se pueden…   » ver todo el comentario
#7 ah... los problemas del milenio (www.claymath.org/millennium-problems).
#7 Realmente este es un problema concreto del problema ¿P = NP?, que es por lo que te dan un millón de leuros.

Lo que piden es un algoritmo mejor, no necesariamente uno polinomial.

Ahora mismo nadie sabe si hay una solución mejor para el algoritmo de las 1000 reinas, si la encuentras acabas de transformar un algoritmo NP a P, por lo que probablemente puedas demostrar que P = NP.

Si consigues un algoritmo polinomial para cualquier problema NP-completo (y el de las reinas lo es) ya has demostrado que P = NP porque no es complicado transformar cualquier otro problema NP al ya resuelto y sobre esto ya está el trabajo hecho.
Erróneo porque la Universidad de St. Andrews no ofrece ninguna recompensa. Unos investigadores de la universidad han demostrado que el problema de las reinas es "NP hard". Nada mas. Si alguien es capaz de resolver el problema de N reinas (no 1000!) en tiempo polinomial, entonces puede ganar el premio Millennium de un millón de collares, como bien explica el #7.
Voto negativo porque el problema de las 8 reinas ya esta resuelto:

en.wikipedia.org/wiki/Eight_queens_puzzle

Imagino que esto se referira a una solucion generalizada (NxN), o 8x8 con alguna condicion en especial... Pero tal como lo explica la entradilla, ya esta resuelto. Esto me parece clickbait.

Edito: El titular dice una cosa, la entradilla otra.
#10 Hay 10 tipos de personas en el mundo: los que saben binario y los que no.
#10 el titular dice 1000 reinas
Esto me recuerda a un pedazo problema que nos puso el profesor de fundamentos de la programación en la facultad en primero. Era el problema de las ocho reinas devolviendo el número de soluciones, pero en un tablero NxM (no hay problema hasta aquí, backtraking a tope y listo, además era parte de la asignatura) pero con la condición de que si M=N había que eliminar todas las soluciones simétricas (giradas en todos los planos), Vamos, que o se te aparecía la musa para encontrar algún algoritmo…   » ver todo el comentario
#13 seguro que tenía truco
#13 demasiado complejo me parece a mi todo eso para ser un examen de fundamentos en primer curso.
#16 Era un gran profesor. Explicaba muy bien y ya avisaba que en sus exámenes siempre había una parte dependiente de que, como decía él, "se te apareciese la virgen". Decía que la programación y la algoritmia era saber usar y enteder una serie de métodos para resolver un problema y si era necesario inventar un nuevo método (de ahí lo de eliminar las simétricas). El resto del examen era bastante normalillo, pero si querías nota tenias que demostrar que sabías usar la cabeza para…   » ver todo el comentario
#39 Parte está respondido en #30. La cursé en el año 92-93. Era anual y se complementaba con un laboratorio de programación (el primer cuatrimestre QuickBasic y el segundo Pascal). La verdad es que daban caña.
En aquella época estaban cambiando los planes de estudios a cuatrimestrales. Por cosas de la vida me cambié de universidad y me pilló el lío el cambio de planes . Mientras esperaba que me convalidaran las asignaturas y por que me salia mas barato el curso completo decidí no tener que…   » ver todo el comentario
#13 Puff me has recordado lo que me costó a mi aprobar la asignatura de Algoritmos y Estructuras de Datos, era con diferencia la más chunga de la carrera, al menos en la EUITIO de Oviedo donde yo estudié. La aprobé la última, por poco, y después de dedicarme un año entero sólo a ella. Eso fué en 2002, me hago viejuno...
<ironic>
Saludos a mi profesor, Oliverio... que majete era... siempre con una sonrisa en la cara...
</ironic>
#13 Yo recuerdo un examen en Diciembre de programación. De todos los que nos presentabamos, solo uno saco un 80% de la nota, dos sacaron un 40% y varios entre ello yo, un 20%. El problema valio 3 ó 4 puntos y aunque me pase una hora dandole vueltas, nada. Y luego lo repitieron en el examen de febrero de Algoritmos y Estructuras de Datos.

Creo que solo buscaban suspender al mayor número de alumnos.
#20 y por qué no vas a una tutoría a que te lo expliquen, para eso están
#23 No solo a una tutoría sino además a las revisiones. Yo siempre iba aunque no fuera porque me hiciera falta subir nota, iba para saber en qué me había equivocado, o para saber como corregía ese profesor los exámenes. Muchas veces te das cuenta de que el profesor se equivoca al corregir, y en algunas ocasiones incluso que las soluciones que ellos proponían no eran válidas, en una de ellas porque el ejercicio directamente no tenía solución con las restricciones del examen. Así que no le quedó más remedio que aceptar el medio párrafo que le escribí durante el examen justificando una solución de dos líneas.
#23 Algunos profesores solo sabian soltar su rollo y comparar el examen con la solución que otro profesor habia propuesto...

Tuve un profesor de C, que la licenciatura que tenia era de Química.

Si en un examen con 100 alumnos, solo uno consigue un 80% de la nota. ¿Tu crees que el problema de que los alumnos no estudian o de que los profesores no saben explicar (o directamente van a suspender para que el proximo año te tengas que volver a matricular)?
#13 ¿En qué año la cursaste? A mi me parece algo totalmente exagerado, y seguramente propio de un mal profesor, y no creo que se pueda hacer en un tiempo razonable teniendo en cuenta que tendrías los 7 puntos del resto del examen en juego ( y que requieran su tiempo). También es un problema en el que es muy fácil confundirse con los índices y dudo que en primero sea razonable exigir backtracking, aunque depende de la intensidad horaria o d si la asignatura era anual.

Simplificándolo al…   » ver todo el comentario
En el mundo no hay tantas monarquías para que haya 1000 reinas en el tablero, ¡Glub!, así que mejor la denominamos Dama.
Si no hay límite de tiempo con reglas y encadenamiento hacia delante vale...
Ahora.... Va a tardar.
Madre mía, como marea el video, con el zoom palante, zoom patras... hazte un cursillo de videos, tio... :-S
Doy la solución en el mensaje mil.
Creo que el de Derivando ha sido víctima de la confusión de otros, según este otro artículo theconversation.com/why-the-worlds-toughest-maths-problems-are-much-ha
La noticia es falsa y sensacionalista. Ni la Universidad de Sant Andrews ofrece recompensa, ni hay recompensa de un millón por la solución de este juego.

Sencillamente, el problema planteado de las 1000 reinas es parecido a lo que en matemáticas llaman complegidad P vs NP, que se producen cálculos tan elevados que ni la tecnología actual no es capaz de hacerlos, por lo que encontrar un sistema o algoritmo que facilitase esos cálculos sería revolucionario.

La confuión viene, a que el…   » ver todo el comentario
#32 El que dice cosas falsas y sensacionalistas eres tú (¿ves?, yo también se usar negritas)

Mira: www.st-andrews.ac.uk/news/archive/2017/title,1539813,en.php
#33 Se nota que no te has leido el link que has puesto, porque reafirma lo que he dicho.

Es el "Clay Mathematics Institute in America" quien ofrece 1 millón de dólares de recompensa (no el Sant Andrews), que es una institución/fundación matemática fundada en la Universidad de Cambridge y ofrece premios e incentivos para matemáticos. Y no está el de las 1000 damas entre ellos.

El premio es, como he escrito antes, por refutar o encontrar un algoritmo que de una

…   » ver todo el comentario
#33 Como ya te han comentado, al resolver ese problema de convertir un problema NP en P, se estaría resolviendo uno de los problemas del milenio. No es que se busque una solución al problema de las n reinas en concreto. En esa propia noticia que pones, cuando hablan del premio, enlazan al problema del milenio P vs NP:

«Visit the Clay Institute website for more information on the US$1m prize.»

El enlace:

www.claymath.org/millennium-problems/p-vs-np-problem

Y por si queda alguna duda,…   » ver todo el comentario
No he terminado de ver todo el vídeo porque se dedica principalmente a explicar el problema, y parece que no mucho a hablar del titular. Quizás se refiera a resolver el problema de P=NP o quizás se refiera a esta otra noticia:

elpais.com/elpais/2017/09/04/ciencia/1504535610_082169.html
El reto consiste en colocar 1.000 reinas en un tablero de 1.000x1.000 sin que se coman unas a otras. Es decir, que no haya dos reinas en la misma fila, columna y diagonal. Varios científicos

…   » ver todo el comentario
De matemática sabrá un güevo, pero de comunicar....menudo ladrillo de vídeo. ¿Y porqué no parpadea?

menéame