N-Queens en sí es solo un problema de juguete; son los métodos para resolver lo que se supone que debes aprender. Debido a que es un problema fácil de entender pero no trivial, puede demostrar no solo la solución “estándar” con retroceso, sino también técnicas como la reducción del espacio de búsqueda utilizando simetría, programación de restricciones o algoritmos evolutivos. Todos estos métodos son ampliamente aplicables.
No es tanto “la técnica X puede resolver N-Queens, por lo tanto, también es útil para el problema Y” y “la técnica X es útil para problemas lógicos basados en restricciones, déjenme demostrarlo en N-Queens”.
La dificultad que tuve al encontrar un análogo del mundo real es que los problemas del mundo real a menudo se refieren a problemas de optimización en lugar de encontrar una solución cuyos parámetros ya se conocen. Por ejemplo, un problema en el trabajo es “¿qué conjunto de pruebas se deben ejecutar para cubrir los cambios realizados en el código fuente?” conjunto mínimo de pruebas) en lugar de encontrar exactamente N pruebas. Pero podríamos ejecutarlo como un problema de restricción para un número cada vez menor de pruebas permitidas.
- ¿Qué son los algoritmos de clasificación y búsqueda?
- Cómo hacer un proyecto de chatbot
- ¿Cuál es el libro correcto para comprar algoritmos de Amazon y para alguien que no tiene idea sobre el algoritmo?
- ¿Cuál es el máximo común divisor de 55 y 75 usando el algoritmo euclidiano?
- ¿Tengo que estudiar matemáticas discretas, algoritmos y estructura de datos para convertirme en un buen desarrollador de Android?
Puede pensar en los problemas de SAT (satisfacción) como la clase general de problemas lógicos para los cuales se desea una solución o una demostración de que no hay soluciones. (Las N-reinas se pueden alimentar fácilmente a un solucionador SAT, ver por ejemplo Resolver un problema de N-Queens usando un solucionador SAT). Los ejemplos del mundo real que se traducen en problemas SAT incluyen:
* ¿Hay algún contraejemplo de tamaño N o menos, a la afirmación que hice sobre mi diseño? (es decir, verificación de modelos de sistemas de estado finito o estructuras de datos)
* ¿Puedo programar estos N elementos de trabajo que requieren que esta matriz de recursos compartidos se complete a tiempo? (Sin embargo, a menudo esto se resuelve mediante programación lineal entera).
* Enrutamiento de circuito en FPGA (existe un conjunto fijo de recursos para un chip dado, y hay un conjunto de restricciones sobre qué elementos deben vincularse con qué otros elementos).
