Foro de elhacker.net

Buenas.

Estoy trabajando en el problema de las 8 reinas y el problema clásico ya lo tengo resuelto. Basicamente consiste en colocar 8 reinas en un tablero sin que se amenacen, esto es que no esten ni en la misma diagonal ni en la misma columna y fila. Hasta ahí todo bien, ahora, quiero añadir una condición más y es que las reinas no estén alineadas. Es decir,

(http://i65.tinypic.com/2rps9pw.jpg)

Esas reinas no se amenazan pero están alineadas, se puede trazar una línea recta sobre ellas. Sinceramente es que le he dado vueltas y no se me ocurre como aproximarlo sin hacer un código que compruebe mil posiciones, y además no tengo muy claro en que posiciones las reinas pueden estar alineadas. Solo quiero la idea porque al final en el código solo tengo que meter una condición más. Muchas gracias de antemano.

La alineación se refiere, cómo has dicho, en la misma diagonal, columna o fila. Para lo demás está bien. Si ya lo tienes resuelto así ya has terminado.

Pero además de eso, quiero que no estén alineadas. Con alineadas no me refiero a que no estén en la misma fila, columna o diagonal. Si no a que no se pueda trazar una linea recta que las corte, como las de la imagen. No se amenazan entre ellas, pero están "alineadas", se puede trazar una linea sobre ellas.

Igual no tiene solución pero me extraña porque es una práctica de la universidad y la verdad que estamos todos comiéndonos el coco.

no hay imagen...

pero sobre "estar alineadas" esto es una ecuación de la recta sobre un mundo de baja resolucion

es decir, tu cuadro es 8 x 8

tienes una reina en 1,1 y una en 8,4 (pegada a la derecha a medio tablero de altura), tu ecuacion es

(https://wikimedia.org/api/rest_v1/media/math/render/svg/fd8d2a77d438b6ed2b42233b61dac75703295713)

entonces
sabiendo que
p1 = (1,1)
y
p2 = (8,4)

(https://latex.codecogs.com/gif.latex?%5Cbg_white%20y%20%3D%20%5Cfrac%7B4-1%7D%7B8-1%7D%28x-1%29%20+%201)

entonces

(https://latex.codecogs.com/gif.latex?%5Cbg_white%20y%20%3D%20%5Cfrac%7B5x+2%7D%7B7%7D)

cualquier reina que cumpla con esa condición está "alineada" (en realidad se consideraría "atravesada en camino de tiro)

por ejemplo, se asume que la que está en (1,2) etá

Que use el agoritmo de bezier, es sencillo de implementar y podría servirle para saber si hay piezas dentro de un punto hasta otro punto. Eso si, me imagino que tendrá hecho el algoritmo de tal forma que ahogue todas las reinas de distintas formas, uqe no siempre genere las mismas posiciones, yo hace muchos años hice un algoritmo para resolver este problema y no siempre me posicionaba las reinas en el mismo sitio, lo cual es una ventaja.

https://es.wikipedia.org/wiki/Curva_de_B%C3%A9zier#Curvas_lineales_de_B%C3%A9zier

Sigo creyendo que es un problema de mala interpretación. Viendo algunas soluciones al tablero de las 8 reinas siempre hay algunas de ellas alineadas, aunque sea a dos saltos de caballo.

---

Se me ha ocurrido. A ver si en línea recta no quiere decir que el intervalo de de tres reinas significa la misma función de recta entre las tres:
Por ejemplo un salto de caballo [+2, -1], o un salto un poco más largo [+3, +2]. Entonces sí se podría decir que están alineadas por una recta, pero tal y como muestras en el ejemplo de tu ejercicio pues no es una recta; es una línea pero no es recta.