Autor Tema: Colocar piezas en un tablero de ajedrez sin que se amenacen entre ellas.

0 Usuarios y 1 Visitante están viendo este tema.

01 Enero, 2021, 12:23 am
Respuesta #10

martiniano

  • Moderador Global
  • Mensajes: 1,510
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

Hombre, Bobby. En este hilo no podías faltar  ;)

Parece divertido. Algún día me gustaría aprender a programar en serio.

Pues como yo. Llevo hechas las cuatro cosas típicas, y seguro que llenas de fallos  ;D. Pero bueno, sí. Una cosa curiosa lo de la programación.

Un saludo. Y feliz año  ;)

14 Marzo, 2021, 09:13 pm
Respuesta #11

Carlos Cao

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 3
  • País: es
  • Karma: +0/-0
¡Muy buenas!

Aprovecho este hilo para postear sobre una curiosidad que lleva rondándome la mente un tiempo. Hace ya unos años descubría sobre la existencia del Problema de las N reinas (dejo por aquí https://youtu.be/WOZ4wDt-iYA un enlace). El asunto es que me puse a investigar entre las soluciones si existía algún nexo común (a lo demás del hecho de que no se atacan, claro está). Sorpresa la mía que tras analizar varia situaciones para tamaños distintos resulta que si nos fijamos tan solo en las diagonales descritas por las reinas, restando el número de casillas atacadas 2 veces menos las que no están atacadas ninguna vez, el número siempre se mantienen constante para ese N. Por ejemplo, creo recordar que para N=8 siempre daba 12.

La cuestión es que conociendo esto, se debería poder encontrar un algoritmo que en vez de ir comprobando paso a paso que no se atacan como se hace con el backtracking, analizando la relación existente entre "casilla libre-casilla doblemente atacada" se debería poder conocer esa constante y por lo tanto, averiguar que valor toma la constante para cada N sin necesitar de una solución previa. Partiendo de esa condición final (en el sentido de que no es algo que se tenga que ir comprobando paso a paso como el hecho de que no se ataquen) se podría construir un algoritmo basado en ella ¿no? Tipo: ¿qué configuraciones cumplen esta constante? Habría que sumarle el hecho de que no se ataquen en horizontal ni vertical claro está

Después de planteada la cuestión, pido disculpas por si esa constante no es tan constante como yo creo (ya que no pude analizar todos los casos de un N determinado) y ¡agradezco de antemano cualquier respuesta!

Un saludo.

17 Marzo, 2021, 06:55 pm
Respuesta #12

martiniano

  • Moderador Global
  • Mensajes: 1,510
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

Disculpa la tardanza en contestar. Vi el mensaje hace unos días, pero entre que no tengo mucha idea del problema de las N reinas y que ando muy hasta arriba de trabajo lo he ido dejando.

Como te digo, la verdad es que no estoy muy familiarizado con el problema de las N reinas. El trabajo que compartí es algo que me propusieron como para practicar algoritmos que utilizasen la técnica del backtracking, pero de ahí no paso.

Ahora bien, a mí todas estas cosas me encantan, y lo que dices suena interesante, lo que pasa es que no estoy seguro de haber entendido cómo defines la constante de la que hablas. ¿Podrías poner algún ejemplo concreto?

Un saludo y gracias por el aporte.

02 Abril, 2021, 05:25 pm
Respuesta #13

martiniano

  • Moderador Global
  • Mensajes: 1,510
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

Dos cosas.

Por un lado, que he escrito un nuevo código a partir del que ya subí que, supuestamente, encuentra todas las soluciones del problema de las \[ N \] reinas salvo giros y simetrías. Sigue siendo un algoritmo basado en el backtracking, es decir, que para tamaños de tablero grandes resulta ineficaz, pero de momento es lo que hay ;D. Yo lo he ejecutado para un tablero de tamaño 14 y tarda unos treinta segundos (en un ordenador sobremesa de gama baja). No me he atrevido a meter un tablero de 15x15, si algún valiente se atreve, adelante.

Por cierto, que me mosquea un poco que en wikipedia ponga que para \[ n=12 \] haya 1787 soluciones. Mi código sólo encuentra \[ 1785 \]. En las demás que he probado coincide en todas. Si alguien sabe algo al respecto que lo comente a ver si aclaramos algo...

Y por si alguien quiere jugar con esto, el programa visualiza, para cada solución encontrada, el número de casillas amenazadas 0, 1 y 2 veces en diagonal excluyendo las casillas en las que se han colocado las damas. Creo que Carlos Cao andaba detrás de algo que tenía que ver con estos valores.

Por otro lado, mientras enredaba con esto que os he contado, he detectado dos errores del código original. El primer error consistía en que si le proponías que resolviese un problema que no admitía solución con alguna de las esquinas ocupadas ya no podía encontrar ninguna solución. Esto lo hacía ineficaz, por ejemplo, a la hora de resolver el problema de colocar 4 damas en un tablero 4x4, ya que la única solución a este problema deja las 4 esquinas libres como se puede comprobar de manera sencilla. El segundo error hacía que el algoritmo no dejase de analizar algunas pocas situaciones de las que ya había analizado por simetría y sin éxito.

Aquí están los dos códigos.  ;)

Un saludo.

02 Abril, 2021, 10:27 pm
Respuesta #14

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 49,070
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Por cierto, que me mosquea un poco que en wikipedia ponga que para \[ n=12 \] haya 1787 soluciones. Mi código sólo encuentra \[ 1785 \]. En las demás que he probado coincide en todas. Si alguien sabe algo al respecto que lo comente a ver si aclaramos algo...

 En todos los documentos que he encontrado al respecto, para \( n=12 \) pone \( 1787 \) soluciones. Digo esto por descartar (o al menos dejar en muy improbable) que fuese una errata de la Wikipedia.

 Por ejemplo:

https://camo.ici.ro/journal/vol19/v19b11.pdf
http://web.math.ucsb.edu/~padraic/ucsb_2014_15/ccs_problem_solving_w2015/N-Queens%20presentation.pdf

Saludos.

03 Abril, 2021, 04:42 am
Respuesta #15

martiniano

  • Moderador Global
  • Mensajes: 1,510
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
 
Hola

Por cierto, que me mosquea un poco que en wikipedia ponga que para \[ n=12 \] haya 1787 soluciones. Mi código sólo encuentra \[ 1785 \]. En las demás que he probado coincide en todas. Si alguien sabe algo al respecto que lo comente a ver si aclaramos algo...

 En todos los documentos que he encontrado al respecto, para \( n=12 \) pone \( 1787 \) soluciones. Digo esto por descartar (o al menos dejar en muy improbable) que fuese una errata de la Wikipedia.

 Por ejemplo:

https://camo.ici.ro/journal/vol19/v19b11.pdf
http://web.math.ucsb.edu/~padraic/ucsb_2014_15/ccs_problem_solving_w2015/N-Queens%20presentation.pdf

Gracias por contestar Luis. Ya veo... Bueno, pues si encuentro el gazapo ya os contaré.

Un saludo.  ;)

04 Abril, 2021, 04:44 am
Respuesta #16

Richard R Richard

  • Ingeniero Industrial
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 607
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Oh Oh!!! me contestó... y ahora qué le digo...
Hola He tratado varias veces de aportar algo, sobre como cual seria la maxima cantidad de piezas a disponer en el tablero de 8x8 sin que ninguna este "tocando"(pueda comer) a otra, pero me enrollo con que si respeto como puede comer , debería respetar que en esa posición jamas podría llegar a ocuparse por la pieza, es decir los peones de las filas 1 y 8 son un ejemplo, los de la 1 porque parten de la 2 en adelante , y los de la 8 porque coronan.  así creo que la cantidad máxima de piezas a colocar en el tablero son 48 peones, y respetando la regla de 1 y 8 son 32.
ej siguen 26 caballos,16 reyes, 14 alfiles, 8 torres , 8 damas
has desarrollado el soft que te permite calcular cual es ese numero máximo?
Saludos  \(\mathbb {R}^3\)

04 Abril, 2021, 12:49 pm
Respuesta #17

martiniano

  • Moderador Global
  • Mensajes: 1,510
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

Hola He tratado varias veces de aportar algo, sobre como cual seria la maxima cantidad de piezas a disponer en el tablero de 8x8 sin que ninguna este "tocando"(pueda comer) a otra, pero me enrollo con que si respeto como puede comer , debería respetar que en esa posición jamas podría llegar a ocuparse por la pieza, es decir los peones de las filas 1 y 8 son un ejemplo, los de la 1 porque parten de la 2 en adelante , y los de la 8 porque coronan.  así creo que la cantidad máxima de piezas a colocar en el tablero son 48 peones, y respetando la regla de 1 y 8 son 32.
ej siguen 26 caballos,16 reyes, 14 alfiles, 8 torres , 8 damas
has desarrollado el soft que te permite calcular cual es ese numero máximo?

En un principio, el problema para el que quería encontrar un algoritmo era el de colocar piezas sobre un tablero de ajedrez sin que se amenacen entre ellas sin tener en cuenta el color de las piezas. Es una generalización del conocido problema de las N reinas (hay enlaces más arriba con abundante información sobre el mismo).

En el programa no incluí la opción de introducir peones porque como ya apuntas el asunto se complicaba. Entre otras cosas habría que definir una dirección en la que se moviesen los peones y se hace raro definir eso sin asignarles un color a los peones.

Sin tener en cuenta a los peones, yo creo que la cantidad máxima de piezas que se pueden colocar es \[ E(\displaystyle\frac{n\color{red} ^2\color {black} +1}{2})  \] donde \[ E \] quiere decir parte entera, que sería el máximo de casillas de un mismo color, ya que colocando caballos en esas casillas no se amenazan entre ellos. Ahora bien, no sé cómo se demuestra formalmente que esa es la cantidad máxima de piezas que se pueden colocar.

No sé si esto contesta a tu pregunta, ya me dices si eso.

Un saludo.

04 Abril, 2021, 02:19 pm
Respuesta #18

Richard R Richard

  • Ingeniero Industrial
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 607
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Oh Oh!!! me contestó... y ahora qué le digo...
Si ha eso me referia , los peones al tener color pueden ubicarse de espaldas digamos y usar dos filas contiguas sin amenazarse.  si usan las filas 1 y 8 te permite hasta 48 peones,
pero claro he tirado todo a prueba y error y me gustaba conocer si había una teoría de máxima probada, como por ejemplo la de los caballos en sobre las casilla de un mismo color.
Hay algun resultado similar para los alfiles?, para reinas y torres ya sabemos por pura logica que de haber solucion detiene que ser igual a numero e filas y columnas.
Saludos  \(\mathbb {R}^3\)

04 Abril, 2021, 04:01 pm
Respuesta #19

sugata

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,069
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Si ha eso me referia , los peones al tener color pueden ubicarse de espaldas digamos y usar dos filas contiguas sin amenazarse.  si usan las filas 1 y 8 te permite hasta 48 peones,
pero claro he tirado todo a prueba y error y me gustaba conocer si había una teoría de máxima probada, como por ejemplo la de los caballos en sobre las casilla de un mismo color.
A no ser que permitas comer al paso...