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.

21 Diciembre, 2020, 04:51 pm
Leído 924 veces

martiniano

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

Llevo unos días dándole a la programación en Java. Resulta que un socio y yo estamos intentando hacer un programilla que te coloque en un tablero de ajedrez de tamaño \( n\times{n} \) diferentes piezas (torres, alfiles, caballos, reinas y reyes) con la condición de que las piezas no se amenacen entre ellas. Las cantidades de cada tipo de pieza y el tamaño del tablero son parámetros que introduce el usuario. El algoritmo utiliza la técnica del "backtracking". Es decir, asume que se puede colocar una cierta pieza en una cierta casilla y sigue colocando las demás llamándose recursivamente a sí mismo. Si después de comprobar todos los casos no ha aparecido ninguna solución entonces cambia de tipo de pieza. Y si ya ha probado con todos los tipos de pieza, entonces cambia de casilla.

Parece que ya casi lo tenemos. No obstante, nos queda arreglar algunos detalles de la interfaz y estudiar alguna posible mejora algorítmica. Entre ellas está la de reconocer algunos casos que es evidente que no tienen solución e impedir así que el algoritmo haga miles de millones de comprobaciones a lo tonto. Por ejemplo, está claro que en un tablero de \( n\times{n} \) el número de reinas más torres no puede ser superior a \( n \), ya que en cada fila (o columna) podemos colocar, a lo sumo, una pieza de este tipo.

Una cota parecida se podría sacar con el número de reinas más alfiles, que no puede exceder al número de diagonales del tablero, \( 2n-1 \), ni posiblemente tampoco a \( 2n-2 \).

Para el tema de los caballos tenemos que al colocar un caballo en una casilla éste sólo amenaza a casillas del otro color. Entonces, para cada \( n \) se puede encontrar solución para un número de caballos igual a la parte entera de \( \displaystyle\frac{n^2+1}{2} \), ya que este es el número máximo de casillas de un mismo color que contiene el tablero. De hecho, no parece nada descabellado aceptar que éste es el número máximo de caballos que se pueden colocar en el tablero. No obstante hay una excepción, que es \( n=2 \), caso para el que se pueden colocar caballos en las cuatro casillas. Intuyo que esta excepción es la única pero no veo cómo demostrarlo. De hecho, el caso \( n=3 \) también tiene una particularidad, y es que se pueden colocar caballos en la casilla central, que sería blanca, y en las cuatro negras.

Me gustaría preguntar si alguien sabe algo sobre cotas máximas en el número de un determinado tipo de piezas o si se han analizado otros casos particulares sin solución de este problema y que se puedan descartar de entrada.

Cuando el código esté acabado lo compartiremos en el foro, como no.

Gracias de antemano por cualquier comentario o aportación. Un saludo.

21 Diciembre, 2020, 08:56 pm
Respuesta #1

Pie

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 294
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
  • \(\pi e\)
Pues por aportar algo más, el número máximo de reyes parece que es
Spoiler
\(  (n - 1)^2  \) si \( n \) es impar, y \(  (n - 2)^2  \) si \( n \) es par.
[cerrar]
Está mal. Quería decir que para \(  n = 1/2 \) es \( 1 \), para \( n = 3 \)/\( 4 \) es \( 4 \), para \( 5 \)/\( 6 \) es \( 9 \), etc..

Saludos.

Hay dos tipos de personas, los que piensan que hay dos tipos de personas y los que no.

21 Diciembre, 2020, 09:34 pm
Respuesta #2

martiniano

  • Moderador Global
  • Mensajes: 1,511
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola. Muchas gracias Pie por contestar.

La verdad es que a mí me parecen muchos reyes los que propones. ¿Cómo colocas 16 reyes en un cuadrado de 5 por 5? A mí sólo me caben 9.

De todas formas, ahora que lo dices, creo que una cota para el número de reyes se obtendría de colocarlos por filas en casillas de un mismo color y alternando fila sí y fila no. Creo que quedaría así: \( (\displaystyle\frac{n+1}{2})^2 \) si \( n \) es impar y \( (\displaystyle\frac{n}{2})^2 \) si \( n \) es par. Tal vez fuera eso lo que querías decir, ¿verdad? De hecho esto me parece más asequible demostrarlo formalmente que la cota de los caballos, por ejemplo.

Gracias. Un saludo.

PD. Vale. Creo que ya te has dado cuenta del error.

21 Diciembre, 2020, 09:48 pm
Respuesta #3

Pie

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 294
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
  • \(\pi e\)
Sí, sí. Me lié de mala manera.. Sería como dices. Y sí, creo que sería más fácil de demostrar que la de los caballos (probablemente la pieza más "rara", en cuanto a movimientos, etc.. del Ajedrez XD)

Saludos.
Hay dos tipos de personas, los que piensan que hay dos tipos de personas y los que no.

22 Diciembre, 2020, 11:45 am
Respuesta #4

Richard R Richard

  • Ingeniero Industrial
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 614
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Oh Oh!!! me contestó... y ahora qué le digo...
Una pregunta las piezas de un color amenazan a las piezas del mismo color?
Otra pregunta los dos reyes están presentes en el tablero,?
Sí las dos respuestas son no entonces la costa es n cuadrado piezas del mismo color
Sí sólo la primera es negativa entonces la cota es n cuadrado menos 1 hay forma de disponer las piezas, de modo que incluso estando contiguas al rey enemigo no lo estén amenazando.
Si el problema es dada una x cantidad de piezas de un bando y de otro disponerlas sin que ninguna se amenace la cota va variando en función del tipo de pieza y la cantidad de cada una.
Si la primera pregunta a resultado positivo entonces el número de pieza posible de disponer el tablero se reduce apreciablemente
La cantidad máxima de reinas que se pueden poner en el tablero sin que ninguna se amenacé con otra sea del mismo color o no es n para un tablero de nxn con n mayor a 4
Saludos  \(\mathbb {R}^3\)

22 Diciembre, 2020, 12:45 pm
Respuesta #5

martiniano

  • Moderador Global
  • Mensajes: 1,511
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola. Gracias Richard por responder.

En el problema que se pretende resolver es indiferente el color de las piezas, como en el famoso problema de colocar \( n \) reinas sobre un tablero de \( n\times{n} \). Es decir, el número de piezas que se puede colocar se reduce en comparación a los otros casos. Se trata de colocar piezas de diferente tipo en cantidades variables sin que ninguna de ellas amenace a ninguna otra.

Gracias. Un saludo.

22 Diciembre, 2020, 02:32 pm
Respuesta #6

ciberalfil

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 351
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Una pregunta, ¿todas las piezas en el tablero deben ser iguales o pueden estar mezclados alfiles, con caballos, reinas etc.?

22 Diciembre, 2020, 02:57 pm
Respuesta #7

martiniano

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

Puede haber cualquier número de piezas de cada tipo. En plan, 2 torres, 18 caballos, 3 alfiles y un rey, por ejemplo.

Un saludo.

31 Diciembre, 2020, 06:26 pm
Respuesta #8

martiniano

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

Aquí está el código. Los gamusinos son una pieza que nos hemos tenido que inventar. Se pueden mover como un caballo y como una torre.

La verdad es que con la tontería llega a enganchar el programilla. En plan... ¿Se pueden colocar dos torres, diez caballos, un alfil y una dama sin que nadie se amenace? ¿Y once caballos, y doce, y trece...?



Un saludo.  ;)

IMPORTANTE. El código tiene errores. Lo comento y actualizo más abajo.

31 Diciembre, 2020, 09:28 pm
Respuesta #9

Bobby Fischer

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 646
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
    • chess.com
Hola.

Aquí está el código. Los gamusinos son una pieza que nos hemos tenido que inventar. Se pueden mover como un caballo y como una torre.

La verdad es que con la tontería llega a enganchar el programilla. En plan... ¿Se pueden colocar dos torres, diez caballos, un alfil y una dama sin que nadie se amenace? ¿Y once caballos, y doce, y trece...?



Un saludo.  ;)

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