Página 1 de 1

Si resuelves el enigma de las 8 reinas puedes ganar 1 millón de $

Publicado: 07 Sep 2017 22:08
por badapower
Acabo de leer una noticia en la Vanguardia y como en el fondo se trata de crear un algoritmo informático capaz de resolver un enigma he querido compartirlo con vosotros, por si hay algún genio aficionado al ajedrez entre nosotros que sea capaz de resolver el enigma planteado, que tiene premio, 1 millón de $.

La noticia :

http://www.lavanguardia.com/deportes/otros-deportes/20170906/431089708625/ocho-reinas-ajedrez-millon-dolares.html

Imaginaos que alguien del foro lo resolviera y encima lo hiciese con uno de nuestros queridos cacharros de 8 o 16 bits, pa morirse.

Re: Si resuelves el enigma de las 8 reinas puedes ganar 1 millón de $

Publicado: 07 Sep 2017 22:23
por minter
eso esta chupado!
y daniquest te lo hace en una linea de basic para el zx80.
y pere en 6809.
y wilco con logica cableada.
y badapower con su atari.
y amigawave con Amos.
y ron yablo tiene grabado en el disco del pakupaku.
y Chema lo tiene incorporado como puzzle en el blakes7

yo creo que quieren nuestro algoritmo para minar bitcoins. -507

Re: Si resuelves el enigma de las 8 reinas puedes ganar 1 millón de $

Publicado: 07 Sep 2017 22:25
por apple2man
Buen reto!
Hoy los programas de ajedrez ganan a los grandes maestros, hay algoritmos, bases de datos de partidas y potencia de cálculo para caer de espaldas.
Aún así no resuelven este problema.
Debe ser difícil de verdad!

Re: Si resuelves el enigma de las 8 reinas puedes ganar 1 millón de $

Publicado: 08 Sep 2017 00:51
por luiscoco
Yo lo tengo en basic, puedes compilarlo con QB64
También lo tengo en recursivo, si lo queréis

REINAS.zip
(361.38 KiB) Descargado 7 veces


Código: Seleccionar todo

DECLARE SUB Ensayar (i%)
DECLARE SUB Imprimir ()
DEFINT A-Z
CLS
DIM a(8), b(16), c(-7 TO 7), x(20)
FOR i = 1 TO 8: a(i) = 1: NEXT
FOR i = 2 TO 16: b(i) = 1: NEXT
FOR i = -7 TO 7: c(i) = 1: NEXT
Ensayar 1

SUB Ensayar (i)
SHARED a(), b(), c(), x()

FOR j = 1 TO 8
    IF a(j) AND b(i + j) AND c(i - j) THEN
        x(i) = j
        a(j) = 0: b(i + j) = 0: c(i - j) = 0
        IF i < 8 THEN Ensayar i + 1 ELSE Imprimir
        a(j) = 1: b(i + j) = 1: c(i - j) = 1
    END IF
NEXT
END SUB

SUB Imprimir
SHARED a(), b(), c(), x()
STATIC s

CLS
FOR i = 1 TO 8
    PRINT x(i);
NEXT
PRINT
PRINT "ÉÍÍÑÍÍÑÍÍÑÍÍÑÍÍÑÍÍÑÍÍÑÍÍ»"

FOR a = 0 TO 6
    PRINT "º  ³  ³  ³  ³  ³  ³  ³  º"
    PRINT "ÇÄÄÅÄÄÅÄÄÅÄÄÅÄÄÅÄÄÅÄÄÅÄĶ"
NEXT
PRINT "º  ³  ³  ³  ³  ³  ³  ³  º"
PRINT "ÈÍÍÏÍÍÏÍÍÏÍÍÏÍÍÏÍÍÏÍÍÏÍͼ"
FOR i = 1 TO 8
    LOCATE x(i) * 2 + 1, i * 3
    PRINT "X";
NEXT
LOCATE 20, 1
s = s + 1
PRINT "LAS DOCE PRIMERAS SOLUCIONES SON LAS AUTENTICAS"
PRINT "LAS DEMAS HASTA 92 SON SIMETRIAS"
PRINT "SOLUCION Nro.:"; s
INPUT aa$
END SUB

Re: Si resuelves el enigma de las 8 reinas puedes ganar 1 millón de $

Publicado: 08 Sep 2017 10:00
por ron
Todavía recuerdo cuando tras aquellos aburridos campeonatos entre Karpov y Kasparov .... que de aburridos no tenían nada, siempre descubrías partidas que eran geniales, lo que pasa que eran un tostón porque duraban horas y horas, a veces algún puntapié p'a despistar por debajo de la mesa y la cosa siempre estaba entre Anatoli y Gary.

Pues el señor Kasparov, descubrió un micro que se llama Atari ST y si tiráis de la cuerda ya veréis que cantidad de software profesional de ajedrez os podréis encontrar, de hecho creo que en algún post ya lo hemos tratado. Sirva como dato.

Creo que se llamaba ChessBase, pero hay toda una linea de productos ...

Kasparov.jpg
Kasparov.jpg (43.52 KiB) Visto 481 veces

Re: Si resuelves el enigma de las 8 reinas puedes ganar 1 millón de $

Publicado: 08 Sep 2017 18:18
por explorer
En realidad, el problema no es el de las 8 reinas, sino para un número mayor: 1000 reinas en un tablero de 1000×1000.

Re: Si resuelves el enigma de las 8 reinas puedes ganar 1 millón de $

Publicado: 08 Sep 2017 19:39
por badapower
Se trata de desarrollar un algoritmo capaz de resolver el rompecabezas en cualquier tipo de tablero, es decir, que ése mismo algoritmo funcione tanto en un tablero de 150 x 150 como en uno de 500 x 500 o uno de 1000 x 1000.

luiscoco escribió:Yo lo tengo en basic, puedes compilarlo con QB64
También lo tengo en recursivo, si lo queréis


Solo te falta generalizar el algoritmo para cualquier tamaño de tablero y millón de $ pa la saca.

Según el artículo el principal problema es que cuando los tableros pasan de 100 x 100 los ordenadores tienen complicaciones a la hora de hacer frente a números tan grandes.

Re: Si resuelves el enigma de las 8 reinas puedes ganar 1 millón de $

Publicado: 08 Sep 2017 19:48
por Chema
Es lo que dice badapower.. para números pequeños es sencillo. Yo creo que lo hice como práctica en la carrera :)

Re: Si resuelves el enigma de las 8 reinas puedes ganar 1 millón de $

Publicado: 08 Sep 2017 23:41
por luiscoco
No se que tanto, lo reviso, ahora, se pueden marcar por bits, y ahorras mucho, ya el algoritmo que puse funciona para cualquier tamaño, y si es grande solo hay que mejorar el almacenamiento y/o la velocidad

Re: Si resuelves el enigma de las 8 reinas puedes ganar 1 millón de $

Publicado: 09 Sep 2017 00:45
por Chema
Luis, es un tema de complejidad algorítmica. El problema de las N reinas tiene una complejidad del orden del factorial de N.

Esto es que en la mejor implementación para 8 hay que realizar 8*7*6*5*4*3*2 comprobaciones. Mira como se dispara para 100 o 1000.

Sin embargo, comprobar si una solución es válida, es rápido (de orden polinomial en N). Es lo que se llama un problema NP-completo. Si alguien encuentra un algoritmo de complejidad polinomial, se resolvería un problema que lleva volviendo locos a los expertos décadas. De ahí el premio.

https://en.m.wikipedia.org/wiki/P_versus_NP_problem

Bueno, creo que era algo así, que todo esto lo tengo muy oxidado.

Re: Si resuelves el enigma de las 8 reinas puedes ganar 1 millón de $

Publicado: 09 Sep 2017 03:49
por luiscoco
Modifiqué el original para que sirva a cualquier tamaño (sin mucho esfuerzo), dibuja mal, (Ya lo arreglare) pero hasta 31x31 lo hace en menos de 1 minuto, y al parecer al 100 x 100 no da problemas pero tardara años, jeje, ahora lo mejorare.

REINAS.zip
(361.7 KiB) Descargado 4 veces

Re: Si resuelves el enigma de las 8 reinas puedes ganar 1 millón de $

Publicado: 09 Sep 2017 18:04
por Luis
No se por qué, cuando he leído el titular de este post, me ha venido a la cabeza lo del orgullo gay

Re: Si resuelves el enigma de las 8 reinas puedes ganar 1 millón de $

Publicado: 09 Sep 2017 19:48
por gflorez
¿Reinonas?

Re: Si resuelves el enigma de las 8 reinas puedes ganar 1 millón de $

Publicado: 10 Sep 2017 02:43
por Perro
XD

Re: Si resuelves el enigma de las 8 reinas puedes ganar 1 millón de $

Publicado: 10 Sep 2017 11:28
por ron
Reinona. Del Astur , reina magnificada en alguno de sus aspectos.

Que hay que entender la ironia !!!! jusjuasjuaw