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

Avatar de Usuario
badapower
Mensajes: 351
Registrado: 16 Oct 2012 00:16
Agradecido : 29 veces
Agradecimiento recibido: 13 veces

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

Mensajepor badapower » 07 Sep 2017 22:08

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.

Avatar de Usuario
minter
Mensajes: 1304
Registrado: 22 Jul 2014 18:51
Agradecido : 525 veces
Agradecimiento recibido: 271 veces

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

Mensajepor minter » 07 Sep 2017 22:23

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

Avatar de Usuario
apple2man
Mensajes: 257
Registrado: 03 Jun 2011 13:53
Agradecimiento recibido: 4 veces

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

Mensajepor apple2man » 07 Sep 2017 22:25

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!

Avatar de Usuario
luiscoco
Mensajes: 2328
Registrado: 15 May 2011 04:23
Ubicación: Caracas, Venezuela
Agradecido : 30 veces
Agradecimiento recibido: 44 veces
Contactar:

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

Mensajepor luiscoco » 08 Sep 2017 00:51

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 8 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

Avatar de Usuario
ron
Mensajes: 17110
Registrado: 28 Oct 2010 14:20
Ubicación: retrocrypta
Agradecido : 491 veces
Agradecimiento recibido: 499 veces

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

Mensajepor ron » 08 Sep 2017 10:00

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 496 veces

Avatar de Usuario
explorer
Mensajes: 82
Registrado: 10 Ene 2016 18:43
Ubicación: Valladolid, España
Agradecido : 3 veces
Agradecimiento recibido: 62 veces
Contactar:

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

Mensajepor explorer » 08 Sep 2017 18:18

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.

Avatar de Usuario
badapower
Mensajes: 351
Registrado: 16 Oct 2012 00:16
Agradecido : 29 veces
Agradecimiento recibido: 13 veces

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

Mensajepor badapower » 08 Sep 2017 19:39

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.

Avatar de Usuario
Chema
Mensajes: 1512
Registrado: 21 Jun 2012 20:13
Ubicación: Gijón
Agradecido : 403 veces
Agradecimiento recibido: 179 veces
Contactar:

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

Mensajepor Chema » 08 Sep 2017 19:48

Es lo que dice badapower.. para números pequeños es sencillo. Yo creo que lo hice como práctica en la carrera :)

Avatar de Usuario
luiscoco
Mensajes: 2328
Registrado: 15 May 2011 04:23
Ubicación: Caracas, Venezuela
Agradecido : 30 veces
Agradecimiento recibido: 44 veces
Contactar:

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

Mensajepor luiscoco » 08 Sep 2017 23:41

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

Avatar de Usuario
Chema
Mensajes: 1512
Registrado: 21 Jun 2012 20:13
Ubicación: Gijón
Agradecido : 403 veces
Agradecimiento recibido: 179 veces
Contactar:

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

Mensajepor Chema » 09 Sep 2017 00:45

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.

Avatar de Usuario
luiscoco
Mensajes: 2328
Registrado: 15 May 2011 04:23
Ubicación: Caracas, Venezuela
Agradecido : 30 veces
Agradecimiento recibido: 44 veces
Contactar:

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

Mensajepor luiscoco » 09 Sep 2017 03:49

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

Avatar de Usuario
Luis
Mensajes: 840
Registrado: 03 Nov 2010 19:00
Agradecido : 30 veces
Agradecimiento recibido: 19 veces

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

Mensajepor Luis » 09 Sep 2017 18:04

No se por qué, cuando he leído el titular de este post, me ha venido a la cabeza lo del orgullo gay
AHA! YOU GOT THE WUMPUS!
HEE HEE HEE - THE WUMPUS'LL GET YOU NEXT TIME!!

Avatar de Usuario
gflorez
Mensajes: 739
Registrado: 12 Sep 2014 19:58
Agradecido : 12 veces
Agradecimiento recibido: 96 veces

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

Mensajepor gflorez » 09 Sep 2017 19:48

¿Reinonas?

Avatar de Usuario
Perro
Mensajes: 909
Registrado: 14 Nov 2012 19:18
Ubicación: QuijoRetro
Agradecido : 2 veces
Agradecimiento recibido: 25 veces

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

Mensajepor Perro » 10 Sep 2017 02:43

XD

Avatar de Usuario
ron
Mensajes: 17110
Registrado: 28 Oct 2010 14:20
Ubicación: retrocrypta
Agradecido : 491 veces
Agradecimiento recibido: 499 veces

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

Mensajepor ron » 10 Sep 2017 11:28

Reinona. Del Astur , reina magnificada en alguno de sus aspectos.

Que hay que entender la ironia !!!! jusjuasjuaw


Volver a “Off Topic”

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 2 invitados