N reinas, X por Y Junta decisión problema entrevista pregunta

Me hicieron la siguiente pregunta en una entrevista hoy y he estado pensando en eso desde entonces. No pude responderlo y no pude encontrar una solución en línea.

Dado un tablero de ajedrez con dimensiones X por Y y N reinas, determine si es posible organizar estas reinas en el tablero de modo que no puedan atacarse entre sí.

Una placa de 2 x 3 con 2 reinas tiene una solución, por lo que el algoritmo devolvería verdadero:

Q . .
. . Q

Estoy buscando un enfoque de programación para este rompecabezas, no solo formas de resolverlo en papel, por ejemplo.

Este no es (IMO) un problema muy interesante desde el punto de vista de la programación. Podría llegar a un algoritmo recursivo que intente cada arreglo, algo como esto:

bool try_queens(Board board, int n)
{
    if (n == 0) {
        // no queens left to place, so we're done
        return true
    }
    // try each open position until we find one that works
    for each position on the board {
        if (is_empty(board, position) and not is_attacked(board, position)) {
            place_queen(board, position)
            if (try_queens(board, n-1)) {
                return true
            }
            remove_queen(board, position)
        }
    }
    // if we get this far, there's no available position
    return false
}

main()
{
    initialize board(X,Y)
    return try_queens(board, N)
}

Si piensas un poco en el problema, te darás cuenta de que no hay forma de colocar N reinas en un tablero donde X <N o Y <N porque eso requeriría que al menos dos reinas terminen en el mismo rango o archivo, y por lo tanto se atacarían entre sí. Si lees sobre el problema de las n reinas, aprenderás rápidamente que siempre es posible colocar N reinas en un tablero NxN para N> 3. Ahora sabemos que la respuesta es NO para (X <N o Y <N) y SÍ para (X> = N e Y> = N, N> 3). Todo lo que queda son los casos especiales:

• N = 1 (SÍ)
• N = 2 (SÍ para X> = 2 e Y> 2 o viceversa)
• N = 3 (SÍ para X> = 3 e Y> 3 o viceversa)

Entonces, nuestra agradable función recursiva se convierte en una función simple que solo compara N con X e Y y devuelve un resultado fijo. Eso es excelente desde el punto de vista del rendimiento, ya que puede obtener una respuesta en tiempo constante. No es tan bueno desde el punto de vista de la programación porque te das cuenta, en este punto, que la pregunta es realmente más sobre qué tan bien puedes resolver acertijos que sobre tu habilidad para escribir una función recursiva.

(Y chico, chico, realmente espero no haber cometido un error tonto en mi respuesta de smarty-pants. ;-)

Si el entrevistador le ha pedido que escriba el código del problema, creo que no es justo. El algoritmo requiere trabajo. Sin embargo, si la idea era mostrarle al entrevistador las clases, los métodos o algunos conceptos que necesitaría usar o algo similar, entonces puede ser una pregunta justa.

El problema es un problema clásico de informática y se discute en muchos de esos libros. Aquí se puede encontrar una excelente explicación, con animación y 12 soluciones diferentes junto con algo de código:

http://en.wikipedia.org/wiki/Eight_queens_puzzle

También se puede encontrar el código aquí: http://www.codeproject.com/KB/java/EightQueen.aspx

No se sienta mal por esto, como dije, no es fácil.

Esto es más un comentario realmente, pero no encaja allí ...

Un tablero de ajedrez tiene 8x8 cuadrados, ni más ni menos (estas preguntas siempre me molestan con ese enfoque de un tablero de ajedrez personalizado).

Pero de todos modos, si tienes un tablero de ajedrez x * y, y n reinas y tomando eso, la reina "toma" estos campos

¿podría crear una matriz bidimensional y "marcar" todos los campos que ataca una reina? Luego coloque el otro (desde el centro del tablero), marque los campos restantes, y así sucesivamente ... hasta que ejecute cualquiera de los campos o reinas.

Este es, por supuesto, un enfoque muy simplificado, ya que si se coloca de una manera mala, creo que el número máximo de reinas variaría.

Hmm, acabo de encontrar esto también - problema de 8 reinas.

Básicamente, el algoritmo de retroceso funciona así:

1. Crea una matriz X por Y. Establecer todos los cuadrados para vaciar.

2. Establecer el recuento de la reina a cero.

3. Establezca su posición actual en (1,1)

4. Vea si puede colocar una reina en la posición actual.

5. Si puede, configure la matriz (X, Y) en reina, incremente el recuento de reina. Si colocaste toda la reina, detente , tienes una solución.

6. Si la posición actual no es (X, Y), incremente la posición actual y vaya al paso 4.

7. Encuentra a la reina en la última posición (la que viene última en el orden en que incrementas las posiciones). Establece la posición actual en la posición de esa reina, quítala y disminuye el recuento de reina.

8. Si el recuento de la reina es cero, deténgase , no hay solución.

9. Incrementar la posición actual.

10. Ve al paso 4.

Agregando a las otras respuestas: crear una matriz bidimensional solo complica el código.

Solo necesita un vector de tamaño 8 para un tablero de ajedrez normal. O 8 + 1 si, como C, la primera posición es 0, solo para simplificar el código, y tratar con 1-8 y no con 0-7.

Si piensa que x es su posición en la matriz, yy es el contenido de la posición. Por ejemplo, el tablero [1] = 8 significa que la primera reina está en [1,8].

De esa manera, solo necesita verificar la validación de las columnas.

En la facultad, me encontré con un libro muy antiguo (¿60?), Sobre algoritmos implementados en Dartmouth BASIC, que implementaba el problema de las 8 reinas usando la menor memoria posible (siendo tan viejo, tiene sentido).

Hasta donde recuerdo, usó la idea del vector, y esencialmente bruto forzó todas las posiciones en el tablero con dos ciclos FOR. Para verificar la validez de la posición, usó un tercer ciclo, un ciclo MIENTRAS en cada posición retrocede en el vector, y busca un número igual, o una fórmula que usa una operación tangente para verificar las diagonales.

Lamentablemente, perdí el rastro de ese libro ...

Dicho algoritmo encontró todas las soluciones para el problema de n-queen.

Si solo tiene que escribir un algoritmo para determinar si existe tal disposición, mire la investigación existente:
El rompecabezas de las ocho reinas en Wikipedia .

Puede devolver trivialmente falso si N> min (X, Y).
Después de leer esa página, sabe que devuelve verdadero si N <= min (X, Y) y 2, 3! = Min (X, Y).

Lo que deja 2, 3 == min (X, Y) y N <= min (X, Y).

Bueno, si N <min (X, Y), encontrar una solución es trivial.
Si N == min (X, Y), solo hay una solución si max (X, Y)> N.

f(X, Y, N)
    if X < Y => f(Y, X, N)
    if Y > N => false
    => (Y < N) or (Y != 2 and Y != 3) or (X > N)

Obviamente no hay solución si N> min (X, Y). De lo contrario, puede mostrar fácilmente que no hay solución para N = X = Y = 2, N = X = Y = 3. Para todos los demás casos, parece haber una solución. El número de soluciones parece aumentar a medida que N crece.

Puede encontrar una solución a través de una búsqueda exhaustiva con retroceso: ponga una reina en la primera fila, columna 1. Coloque una reina en la segunda fila, en la primera columna que la reina en la fila 1 no puede alcanzar. Pon una reina en la segunda fila, etc. Si una reina no se puede poner en la fila k, entonces la quitas y mueves a la reina en la fila k-1 a la siguiente posición desocupada.