La mejor solución es 15.
Con solo 64 celdas, este problema puede resolverse fácilmente mediante la fuerza bruta. Una buena opción de implementación es utilizar el rastreo inverso: podremos podar grandes partes del espacio de búsqueda de manera eficiente.
Aquí hay un truco para simplificar la implementación: multiplique todas las coordenadas de celda por 2 y represente las paredes en un mapa de bits simple de la siguiente manera:
- Supongamos que tenemos el recorrido de preorden de un árbol de expresión. ¿El árbol que creamos con este recorrido es único?
- ¿Dónde debería comenzar si quiero implementar un algoritmo de detección de movimiento en FPGA?
- Cómo calcular la similitud semántica entre un automóvil y una bicicleta mediante el algoritmo Jian y Conrath
- ¿Cómo puede el paralelismo mejorar el algoritmo de fuerza bruta?
- ¿Por qué la programación dinámica se llama programación dinámica?
char board[17][18] = { "#################", "#?.?.?.?.?.?#?.?#", "#...........#...#", "#?.?.?.?#?.?#?.?#", "######..#.......#", "#?.?.?.?#?.?.?.?#", "#......#####....#", "#?.?.?.?.?#?.?.?#", "#.........#.....#", "#?.?#?.?.?#?.?.?#", "#...#.....#######", "#?.?#?.?.?.?.?.?#", "#...######......#", "#?.?.?.?.?.?#?.?#", "###.........#...#", "#?#?.?.?.?.?#?.?#", "#################", };
Los signos de interrogación son las celdas. Tenga en cuenta que dos signos de interrogación se ven (horizontal, vertical o diagonalmente) si y solo si las dos celdas correspondientes se ven en la imagen en los detalles de la pregunta. (Permito pasar a través de un punto donde termina una sola pared, pero no a través de una esquina donde se unen dos o más paredes).
Y aquí hay una solución con 15 reinas:
################# #Q .......... # Q .. # # ........... # ... # # .... Q .. # Q .. # ... # ###### .. # ....... # #Q ...... # ...... Q # # ...... ##### .... # # .... Q .... # Q .... # # ......... # ..... # # ... # .... Q # ..... # # ... # ..... ####### # .. Q # ...... Q .... # # ... ###### ...... # # .... Q ...... # .. Q # ### ......... # ... # #Q # ...... Q .. # ... # #################