El rompecabezas de las ocho reinas es el problema de colocar ocho reinas de ajedrez en un tablero de ajedrez de 8 × 8 para que no haya dos reinas que se amenacen entre sí; por lo tanto, una solución requiere que no haya dos reinas que compartan la misma fila, columna o diagonal. El rompecabezas de las ocho reinas es un ejemplo del problema más general de las n reinas de colocar n reinas no atacantes en un tablero de ajedrez n × n , para el cual existen soluciones para todos los números naturales n con la excepción de n = 2 y n = 3. [ 1]
a | B | C | D | mi | F | gramo | h | ||
8 | 8 | ||||||||
7 | 7 | ||||||||
6 | 6 | ||||||||
5 | 5 | ||||||||
4 | 4 | ||||||||
3 | 3 | ||||||||
2 | 2 | ||||||||
1 | 1 | ||||||||
a | B | C | D | mi | F | gramo | h |
Historia
El compositor de ajedrez Max Bezzel publicó el rompecabezas de las ocho reinas en 1848. Franz Nauck publicó las primeras soluciones en 1850. [2] Nauck también extendió el rompecabezas al problema de las n reinas, con n reinas en un tablero de ajedrez de n × n cuadrados.
Desde entonces, muchos matemáticos , incluido Carl Friedrich Gauss , han trabajado tanto en el rompecabezas de las ocho reinas como en su versión generalizada de las n reinas. En 1874, S. Gunther propuso un método que utiliza determinantes para encontrar soluciones. [2] JWL Glaisher refinó el enfoque de Gunther.
En 1972, Edsger Dijkstra utilizó este problema para ilustrar el poder de lo que llamó programación estructurada . Publicó una descripción muy detallada de un algoritmo de retroceso en profundidad . 2
Construyendo y contando soluciones
El problema de encontrar todas las soluciones al problema de las 8 reinas puede ser bastante costoso computacionalmente, ya que hay 4,426,165,368 (es decir, 64 C 8 ) posibles arreglos de ocho reinas en un tablero de 8 x 8, pero solo 92 soluciones. Es posible utilizar atajos que reduzcan los requisitos computacionales o reglas prácticas que eviten técnicas computacionales de fuerza bruta . Por ejemplo, al aplicar una regla simple que restringe a cada reina a una sola columna (o fila), aunque todavía se considera fuerza bruta, es posible reducir el número de posibilidades a 16.777.216 (es decir, 8 8 ) combinaciones posibles. La generación de permutaciones reduce aún más las posibilidades a solo 40,320 (¡es decir, 8! ), Que luego se revisan para detectar ataques diagonales.
Soluciones
El rompecabezas de las ocho reinas tiene 92 soluciones distintas. Si las soluciones que difieren solo por las operaciones de simetría de rotación y reflexión del tablero se cuentan como una, el rompecabezas tiene 12 soluciones. Éstas se denominan soluciones fundamentales ; los representantes de cada uno se muestran a continuación.
Una solución fundamental suele tener ocho variantes (incluida su forma original) que se obtienen al girar 90, 180 o 270 ° y luego reflejar cada una de las cuatro variantes de rotación en un espejo en una posición fija. Sin embargo, si una solución fuera equivalente a su propia rotación de 90 ° (como sucede con una solución con cinco reinas en un tablero de 5 × 5), esa solución fundamental tendrá solo dos variantes (ella misma y su reflejo). Si una solución es equivalente a su propia rotación de 180 ° (pero no a su rotación de 90 °), tendrá cuatro variantes (ella misma y su reflexión, su rotación de 90 ° y la reflexión de eso). Si n > 1, no es posible que una solución sea equivalente a su propio reflejo porque eso requeriría que dos reinas se enfrenten entre sí. De las 12 soluciones fundamentales al problema con ocho reinas en un tablero de 8 × 8, exactamente una (la solución 12 a continuación) es igual a su propia rotación de 180 °, y ninguna es igual a su rotación de 90 °; por tanto, el número de soluciones distintas es 11 × 8 + 1 × 4 = 92.
Todas las soluciones fundamentales se presentan a continuación:
|
|
|
|
|
|
|
|
|
|
|
|
La solución 10 tiene la propiedad adicional de que no hay tres reinas en línea recta . Las soluciones 1 y 8 tienen una línea de 4 reinas.
Existencia de soluciones
Estos algoritmos de fuerza bruta para contar el número de soluciones son computacionalmente manejables para n = 8 , pero serían intratables para problemas de n ≥ 20 , ¡como 20! = 2,433 × 10 18 . Si el objetivo es encontrar una única solución, se puede demostrar que existen soluciones para todo n ≥ 4 sin búsqueda alguna. [3] Estas soluciones presentan patrones escalonados, como en los siguientes ejemplos para n = 8, 9 y 10:
|
|
|
Los ejemplos anteriores se pueden obtener con las siguientes fórmulas. [3] Sea ( i , j ) el cuadrado de la columna i y la fila j del tablero de ajedrez n × n , k un número entero.
Un enfoque [3] es
- Si el resto de dividir n entre 6 no es 2 o 3, entonces la lista es simplemente todos los números pares seguidos de todos los números impares no mayores que n .
- De lo contrario, escriba listas separadas de números pares e impares (2, 4, 6, 8 - 1, 3, 5, 7).
- Si el resto es 2, intercambie 1 y 3 en la lista impar y mueva 5 al final ( 3, 1 , 7, 5 ).
- Si el resto es 3, mueva 2 al final de la lista par y 1,3 al final de la lista impar (4, 6, 8, 2 - 5, 7, 1, 3 ).
- Agregue la lista impar a la lista par y coloque las reinas en las filas dadas por estos números, de izquierda a derecha (a2, b4, c6, d8, e3, f1, g7, h5).
Para n = 8, esto da como resultado la solución fundamental 1 anterior. A continuación se muestran algunos ejemplos más.
- 14 reinas (resto 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
- 15 reinas (resto 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
- 20 reinas (resto 2): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 9, 11, 13, 15, 17, 19, 5.
Contando soluciones
Las siguientes tablas dan el número de soluciones para colocar n reinas en un tablero n × n , tanto fundamentales (secuencia A002562 en la OEIS ) como todas (secuencia A000170 en la OEIS ).
norte | fundamental | todas |
---|---|---|
1 | 1 | 1 |
2 | 0 | 0 |
3 | 0 | 0 |
4 | 1 | 2 |
5 | 2 | 10 |
6 | 1 | 4 |
7 | 6 | 40 |
8 | 12 | 92 |
9 | 46 | 352 |
10 | 92 | 724 |
11 | 341 | 2680 |
12 | 1,787 | 14.200 |
13 | 9.233 | 73,712 |
14 | 45,752 | 365,596 |
15 | 285,053 | 2,279,184 |
dieciséis | 1.846.955 | 14,772,512 |
17 | 11,977,939 | 95,815,104 |
18 | 83,263,591 | 666,090,624 |
19 | 621,012,754 | 4.968.057.848 |
20 | 4.878.666.808 | 39,029,188,884 |
21 | 39,333,324,973 | 314,666,222,712 |
22 | 336,376,244,042 | 2.691.008.701.644 |
23 | 3,029,242,658,210 | 24,233,937,684,440 |
24 | 28,439,272,956,934 | 227,514,171,973,736 |
25 | 275,986,683,743,434 | 2.207.893.435.808.352 |
26 | 2,789,712,466,510,289 | 22,317,699,616,364,044 |
27 | 29,363,495,934,315,694 | 234,907,967,154,122,528 |
El rompecabezas de las seis reinas tiene menos soluciones que el rompecabezas de las cinco reinas.
No existe una fórmula conocida para el número exacto de soluciones, ni siquiera para su comportamiento asintótico. El tablero de 27 × 27 es el tablero de orden más alto que se ha enumerado por completo. [4]
Problemas relacionados
- Mayores dimensiones
- Encuentre el número de reinas no atacantes que se pueden colocar en un espacio de ajedrez d- dimensional de tamaño n . Se pueden colocar más de n reinas en algunas dimensiones más altas (el ejemplo más pequeño son cuatro reinas que no atacan en un espacio de ajedrez de 3 × 3 × 3), y de hecho se sabe que para cualquier k , hay dimensiones más altas donde n k las reinas no son suficientes para atacar todos los espacios. [5] [6]
- Usando piezas que no sean reinas
- En un tablero de 8 × 8 se pueden colocar 32 caballos , o 14 alfiles , 16 reyes u ocho torres , de modo que no haya dos piezas que se ataquen entre sí. Las piezas de ajedrez de hadas también han sido sustituidas por reinas. En el caso de los caballeros, una solución fácil es colocar uno en cada casilla de un color determinado, ya que se mueven solo al color opuesto. La solución también es fácil para torres y reyes. Se pueden colocar ocho torres a lo largo de una diagonal larga (entre miles de otras soluciones), y se colocan 16 reyes en el tablero dividiéndolo en 2 cuadrados por 2 y colocando los reyes en puntos equivalentes en cada cuadrado.
- Variaciones de ajedrez
- Se pueden solicitar problemas relacionados para variaciones de ajedrez como shogi . Por ejemplo, el problema de n + k reyes dragones pide colocar k peones shogi y n + k reyes dragones que no atacan mutuamente en un tablero de n × n shogi. [7]
- Matriz de permutación
- En matemáticas, una matriz de permutación puede considerarse geométricamente como un conjunto de n puntos que se encuentran en los cuadrados de un tablero de ajedrez de n × n , de modo que cada fila o columna contiene solo un punto. Por lo tanto, una matriz de permutación de orden- n es una solución a un rompecabezas de n- curvas.
- Tableros no estándar
- Pólya estudió el problema de n reinas en un tablero toroidal ("en forma de rosquilla") y demostró que hay una solución en un tablero n × n si y solo si n no es divisible por 2 o 3. [8] En 2009 Pearson y Pearson llenó algorítmicamente tableros tridimensionales ( n × n × n ) con n 2 reinas, y propuso que múltiplos de estos pueden producir soluciones para una versión tetradimensional del rompecabezas. [9] [se necesita una mejor fuente ]
- Dominación
- Dado un tablero de n × n , el número de dominación es el número mínimo de reinas (u otras piezas) necesarias para atacar u ocupar cada casilla. Para n = 8, el número de dominio de la reina es 5. [10] [11]
- Reinas y otras piezas
- Las variantes incluyen mezclar reinas con otras piezas; por ejemplo, colocando m reinas ym caballos en un tablero de n × n para que ninguna pieza ataque a otra [12] o colocando reinas y peones para que no haya dos reinas que se ataquen entre sí. [13] [se necesita una mejor fuente ]
- Cuadrados magicos
- En 1992, Demirörs, Rafraf y Tanik publicaron un método para convertir algunos cuadrados mágicos en soluciones de n reinas y viceversa. [14]
- Cuadrados latinos
- En una matriz de n × n , coloque cada dígito del 1 al n en n ubicaciones de la matriz para que no haya dos instancias del mismo dígito en la misma fila o columna.
- Cobertura exacta
- Considere una matriz con una columna principal para cada uno de los n rangos del tablero, una columna principal para cada uno de los n archivos y una columna secundaria para cada una de las 4 n - 6 diagonales no triviales del tablero. La matriz tiene n 2 filas: una para cada posible ubicación de reina, y cada fila tiene un 1 en las columnas correspondientes al rango, archivo y diagonales de ese cuadrado y un 0 en todas las demás columnas. Entonces, el problema de las n reinas equivale a elegir un subconjunto de las filas de esta matriz de modo que cada columna principal tenga un 1 precisamente en una de las filas elegidas y cada columna secundaria tenga un 1 como máximo en una de las filas elegidas; este es un ejemplo de un problema de cobertura exacta generalizado , del cual el sudoku es otro ejemplo.
- n -Queens Finalización
- Un artículo de 2017 [15] investigó el problema "Dado un tablero de ajedrez n × n en el que ya están colocadas algunas reinas, ¿se puede colocar una reina en cada fila restante para que no haya dos reinas que se ataquen entre sí?" y varios problemas relacionados. Los autores afirmaron que estos problemas son NP-completo [16] y # P-completo .
Ejercicio de diseño de algoritmos
Encontrar todas las soluciones al acertijo de las ocho reinas es un buen ejemplo de un problema simple pero no trivial. Por esta razón, a menudo se usa como un problema de ejemplo para varias técnicas de programación, incluidos enfoques no tradicionales como la programación con restricciones , la programación lógica o los algoritmos genéticos . La mayoría de las veces, se usa como un ejemplo de un problema que se puede resolver con un algoritmo recursivo , formulando el problema de n reinas de manera inductiva en términos de agregar una sola reina a cualquier solución al problema de colocar n −1 reinas en una n. × n tablero de ajedrez. La inducción toca fondo con la solución al 'problema' de colocar 0 reinas en el tablero de ajedrez, que es el tablero de ajedrez vacío.
Esta técnica se puede utilizar de una manera mucho más eficiente que el algoritmo de búsqueda de fuerza bruta ingenua , que considera las 64 8 = 2 48 = 281,474,976,710,656 posibles ubicaciones ciegas de ocho reinas, y luego las filtra para eliminar todas las ubicaciones que colocan dos reinas en el mismo cuadrado (dejando solo 64! / 56! = 178,462,987,637,760 posibles ubicaciones) o en posiciones de ataque mutuo. Este algoritmo muy pobre, entre otras cosas, producirá los mismos resultados una y otra vez en todas las diferentes permutaciones de las asignaciones de las ocho reinas, además de repetir los mismos cálculos una y otra vez para los diferentes subconjuntos de cada una. solución. Un mejor algoritmo de fuerza bruta coloca una única reina en cada fila, lo que lleva a solo 8 8 = 2 24 = 16.777.216 ubicaciones ciegas.
Es posible hacerlo mucho mejor que esto. Un algoritmo resuelve el rompecabezas de las ocho torres generando las permutaciones de los números del 1 al 8 (¡de los cuales hay 8! = 40,320), y usa los elementos de cada permutación como índices para colocar una reina en cada fila. Luego rechaza aquellas tablas con posiciones de ataque diagonales. El programa de búsqueda de retroceso en profundidad primero , una ligera mejora en el método de permutación, construye el árbol de búsqueda considerando una fila del tablero a la vez, eliminando la mayoría de las posiciones del tablero que no son de solución en una etapa muy temprana de su construcción. Debido a que rechaza los ataques de torre y diagonales incluso en tableros incompletos, examina solo 15.720 posibles colocaciones de damas. Una mejora adicional, que examina solo 5.508 posibles colocaciones de reinas, es combinar el método basado en la permutación con el método de poda temprana: las permutaciones se generan primero en profundidad y el espacio de búsqueda se poda si la permutación parcial produce un ataque diagonal. La programación de restricciones también puede ser muy eficaz en este problema.
Una alternativa a la búsqueda exhaustiva es un algoritmo de 'reparación iterativa', que normalmente comienza con todas las reinas en el tablero, por ejemplo, con una reina por columna. [17] Luego cuenta el número de conflictos (ataques) y usa una heurística para determinar cómo mejorar la ubicación de las reinas. La heurística de ' conflictos mínimos ' - mover la pieza con el mayor número de conflictos al cuadrado en la misma columna donde el número de conflictos es menor - es particularmente efectiva: encuentra una solución al problema de 1,000,000 de reinas en menos de 50 pasos. de media. [ cita requerida ] Esto asume que la configuración inicial es 'razonablemente buena' - si un millón de reinas comienzan en la misma fila, se necesitarán al menos 999,999 pasos para arreglarlo. Un punto de partida "razonablemente bueno" se puede encontrar, por ejemplo, poniendo cada reina en su propia fila y columna de modo que entre en conflicto con el menor número de reinas que ya haya en el tablero.
A diferencia de la búsqueda de retroceso descrita anteriormente, la reparación iterativa no garantiza una solución: como todos los procedimientos codiciosos , puede atascarse en un óptimo local. (En tal caso, el algoritmo puede reiniciarse con una configuración inicial diferente). Por otro lado, puede resolver problemas de tamaño que son varios órdenes de magnitud más allá del alcance de una búsqueda en profundidad.
Esta animación ilustra el retroceso para resolver el problema. Una reina se coloca en una columna que se sabe que no causa conflicto. Si no se encuentra una columna, el programa vuelve al último estado correcto y luego intenta con una columna diferente.
Como alternativa al retroceso, las soluciones se pueden contar enumerando de forma recursiva las soluciones parciales válidas, una fila a la vez. En lugar de construir posiciones de tablero completas, las diagonales y columnas bloqueadas se rastrean con operaciones bit a bit. Esto no permite la recuperación de soluciones individuales. [18] [19]
Programa de muestra
El siguiente es un programa de Pascal de Niklaus Wirth en 1976. [20] Encuentra una solución al problema de las ocho reinas.
programa eightqueen1 ( salida ) ; var i : número entero ; q : booleano ; a : matriz [ 1 .. 8 ] de booleano ; b : matriz [ 2 .. 16 ] de booleano ; c : matriz [ - 7 .. 7 ] de booleano ; x : matriz [ 1 .. 8 ] de entero ; procedimiento try ( i : integer ; var q : boolean ) ; var j : entero ; comenzar j : = 0 ; repetir j : = j + 1 ; q : = falso ; si a [ j ] y b [ i + j ] y c [ i - j ] entonces comience x [ i ] : = j ; a [ j ] : = falso ; b [ i + j ] : = falso ; c [ i - j ] : = falso ; si i < 8 entonces empiece intente ( i + 1 , q ) ; si no es q, entonces comienza a [ j ] : = verdadero ; b [ i + j ] : = verdadero ; c [ i - j ] : = verdadero ; end end else q : = verdadero fin hasta q o ( j = 8 ) ; terminar ; empezar para i : = 1 a 8 hacer a [ i ] : = verdadero ; para i : = 2 a 16 hacen b [ i ] : = verdadero ; para i : = - 7 a 7 hacer c [ i ] : = verdadero ; prueba ( 1 , q ) ; si q entonces para i : = 1 a 8 hacen de escritura ( x [ i ] : 4 ) ; final escrito .
En la cultura popular
En el juego The 7th Guest , el 8th Puzzle: "The Queen's Dilemma" en la sala de juegos de la mansión Stauf es el rompecabezas de las ocho reinas de facto . [21] ( págs . 48-49 )
Ver también
- Juego de matematicas
- Rompecabezas matemático
- No hay problema de tres en línea
- Polinomio de torre
- Matriz de costas
Referencias
- ^ EJ Hoffman et al., "Construcción de las soluciones del problema de m Queens". Revista de matemáticas , vol. XX (1969), págs. 66–72. [1]
- ^ a b W. W. Rouse Ball (1960) "El problema de las ocho reinas", en Ensayos y recreaciones matemáticas , Macmillan, Nueva York, págs. 165-171.
- ↑ a b c Bo Bernhardsson (1991). "Soluciones explícitas al problema de N-Queens para todos los N". Toro SIGART . 2 (2): 7. doi : 10.1145 / 122319.122322 .
- ^ El proyecto Q27
- ^ J. Barr y S. Rao (2006), El problema de las n-reinas en dimensiones superiores, Elemente der Mathematik, vol 61 (4), págs. 133-137.
- ^ Martin S. Pearson. "Reinas en un tablero de ajedrez - Más allá de la segunda dimensión" (php) . Consultado el 27 de enero de 2020 .
- ^ Chatham, Doug (1 de diciembre de 2018). "Reflexiones sobre el problema de los reyes dragones n + k" . Revista Recreativa de Matemáticas . 5 (10): 39–55. doi : 10.2478 / rmm-2018-0007 .
- ^ G. Pólya, Uber die "doppelt-periodischen" Losungen des n-Damen-Problems, George Pólya: Collected papers Vol. IV, GC. Rota, ed., MIT Press, Cambridge, Londres, 1984, págs. 237–247
- ^ [2]
- ^ Burger, AP; Cockayne, EJ; Mynhardt, CM (1997), "Dominación e irredundancia en el gráfico de las reinas", Matemáticas discretas , 163 (1-3): 47-66, doi : 10.1016 / 0012-365X (95) 00327-S , hdl : 1828 / 2670 , MR 1428557
- ^ Weakley, William D. (2018), "Reinas alrededor del mundo en veinticinco años", en Gera, Ralucca; Haynes, Teresa W .; Hedetniemi, Stephen T. (eds.), Teoría de grafos: Conjeturas favoritas y problemas abiertos - 2 , Libros de problemas en matemáticas, Cham: Springer, págs. 43–54, doi : 10.1007 / 978-3-319-97686-0_5 , Señor 3889146
- ^ "Problema de reinas y caballeros" . Archivado desde el original el 16 de octubre de 2005 . Consultado el 20 de septiembre de 2005 .
- ^ Problema de nueve reinas
- ↑ O. Demirörs, N. Rafraf y MM Tanik. Obtener soluciones de n-reinas a partir de cuadrados mágicos y construir cuadrados mágicos a partir de soluciones de n-reinas. Journal of Recreational Mathematics, 24: 272–280, 1992
- ^ Gent, Ian P .; Jefferson, Christopher; Nightingale, Peter (agosto de 2017). "Complejidad de la finalización de n- reinas" . Revista de Investigación en Inteligencia Artificial . 59 : 815–848. doi : 10.1613 / jair.5512 . ISSN 1076-9757 . Consultado el 7 de septiembre de 2017 .
- ^ "El rompecabezas de las 8 reinas" . www.claymath.org . Instituto Clay de Matemáticas . 2 de septiembre de 2017.
- ↑ A Polynomial Time Algorithm for the N-Queen Problem por Rok Sosic y Jun Gu, 1990. Describe el tiempo de ejecución de hasta 500.000 Queens, que era el máximo que podían ejecutar debido a limitaciones de memoria.
- ^ Qiu, Zongyan (febrero de 2002). "Codificación de vector de bits del problema n-queen". Avisos ACM SIGPLAN . 37 (2): 68–70. doi : 10.1145 / 568600.568613 .
- ^ Richards, Martin (1997). Algoritmos de retroceso en MCPL usando patrones de bits y recursividad (PDF) (Informe técnico). Laboratorio de Computación de la Universidad de Cambridge. UCAM-CL-TR-433.
- ^ Wirth, 1976, p. 145
- ^ DeMaria, Rusel (15 de noviembre de 1993). El séptimo invitado: la guía oficial de estrategia (PDF) . Prima Games. ISBN 978-1-5595-8468-5. Consultado el 22 de abril de 2021 .
Otras lecturas
- Bell, Jordan; Stevens, Brett (2009). "Una encuesta de resultados conocidos y áreas de investigación para n- reinas". Matemáticas discretas . 309 (1): 1–31. doi : 10.1016 / j.disc.2007.12.043 .
- Watkins, John J. (2004). Al otro lado del tablero: las matemáticas de los problemas de ajedrez . Princeton: Prensa de la Universidad de Princeton. ISBN 978-0-691-11503-0.
- O.-J. Dahl , EW Dijkstra , Programación estructurada CAR Hoare , Academic Press, Londres, 1972 ISBN 0-12-200550-3 véanse las págs. 72-82 para la solución de Dijkstra del problema de las 8 reinas.
- Allison, L .; Yee, CN; McGaughey, M. (1988). "Problemas tridimensionales de NxN-Queens" . Departamento de Ciencias de la Computación, Universidad de Monash, Australia.
- Nudelman, S. (1995). "El problema de N-Queens modular en dimensiones superiores". Matemáticas discretas . 146 (1-3): 159-167. doi : 10.1016 / 0012-365X (94) 00161-5 .
- Engelhardt, M. (agosto de 2010). "Der Stammbaum der Lösungen des Damenproblems (en alemán, significa El cuadro genealógico de soluciones al problema de las 8 reinas" . Spektrum der Wissenschaft : 68–71.
- Sobre El Problema Modular N-Reina en Dimensiones Superiores , Ricardo Gómez, Juan José Montellano y Ricardo Strausz (2004), Instituto de Matematicas, Área de la Investigación Científica, Circuito Exterior, Ciudad Universitaria, México.
- Wirth, Niklaus (1976), "Algoritmos + Estructuras de datos = Programas" , Serie Prentice-Hall en Computación Automática , Prentice-Hall, Bibcode : 1976adsp.book ..... W , ISBN 978-0-13-022418-7
- Wirth, Niklaus (2004) [actualizado en 2012]. "El problema de las ocho reinas". Algoritmos y estructuras de datos (PDF) . Versión de Oberon con correcciones y modificaciones autorizadas. págs. 114-118.
enlaces externos
- Weisstein, Eric W. "Problema de Queens" . MathWorld .
- queens-cpm en GitHub Rompecabezas de ocho reinas en Turbo Pascal para CP / M
- eight-queens.py en GitHub Eight Queens Puzzle solución de una línea en Python
- Soluciones en más de 100 lenguajes de programación diferentes (en Rosetta Code )