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.
