Algunos rompecabezas famosos en la lista de los rompecabezas clásicos de la informática son :
- Filósofos comedores (Concurrencia y Deadlocks)
- Cinco filósofos se sientan alrededor de una mesa circular. Delante de cada filósofo hay un gran plato de arroz. Los filósofos alternan su tiempo entre comer y pensar. Hay un palillo entre cada filósofo, a su derecha e izquierda inmediatas. Para comer, un filósofo debe utilizar ambos palillos. ¿Cómo se puede garantizar que todos los filósofos puedan comer de forma fiable sin morir de hambre?
- ¿Cómo resolverlo? Hay varias soluciones que van desde el propio planteador del problema, Edsger W. Dijkstra, hasta otras respuestas arbitrarias.
- Vendedor ambulante (P=NP)
- Un vendedor tiene una ruta de ciudades que conforman su ritmo. ¿Cuál es la ruta de ventas más eficiente que visita cada ciudad exactamente una vez, y luego regresa a la ciudad de origen?
- Tenemos una heurística pero aún no se sabe si se puede resolver con un algoritmo de tiempo polinomial.
- Ocho reinas (diseño de algoritmos)
- Dado ocho reinas en un tablero de ajedrez estándar de 8 x 8, ¿cuántas posiciones únicas -excluyendo rotaciones e imágenes en espejo- pueden ocupar esas ocho reinas sin atacarse entre sí?
- Solución: El retroceso es una, la bifurcación y la unión otra.
- Dos generales (protocolos de comunicación)
- Dos ejércitos, cada uno dirigido por un general, se preparan para atacar una ciudad. Los ejércitos están acampados fuera de la ciudad en dos montañas separadas por un gran valle. Para capturar la ciudad, los generales deben atacar exactamente al mismo tiempo. La única manera de que los generales se comuniquen es enviando mensajeros a través del valle. Por desgracia, el valle está ocupado por los defensores de la ciudad, por lo que existe la posibilidad de que cualquier mensajero sea capturado. Cada general no tiene forma de saber si su mensajero llegó. ¿Cómo coordinan los generales su ataque?
- Torres de Hanoi (Recursion)
- Tienes una pila de discos, de mayor a menor, que se deslizan sobre la primera clavija de un tablero de tres clavijas. Tu objetivo es mover toda la pila de discos desde la primera clavija hasta la tercera. Sin embargo, sólo puedes mover el disco más alto de cualquier clavija, y los discos más pequeños deben colocarse siempre sobre los discos más grandes. ¿Cuántos movimientos serán necesarios?
- Respuesta : Para [math]n[/math] discos, tenemos [math]2^n-1[/math] pasos/movimientos para resolver, lo que se puede hacer usando la recursividad.
Fuente : Puzzles clásicos de informática
Un libro realmente bueno es The Science of Programming de David Gries en el que discute varias ideas detrás de los puzzles de Dijkstra y otras ideas clásicas de puzzles. Por ejemplo esto : Un rompecabezas combinatorio clásico :
Una bolsa contiene algunas bolas blancas y negras. El siguiente proceso debe repetirse el mayor tiempo posible (suponiendo que tenemos un suministro infinito de bolas blancas y negras).
- Selecciona aleatoriamente dos bolas de la bolsa. Si son del mismo color, tíralas, pero pon una bola negra de más.
- Si son de distinto color, vuelve a colocar la blanca en la bolsa y tira la negra.
Intenta resolverlo, es mucho más sencillo cuando lo haces en papel.