×

A survey of known results and research areas for \(n\)-queens. (English) Zbl 1228.05002

Summary: We survey known results for the \(n\)-queens problem of placing \(n\) nonattacking queens on an \(n\times n\) chessboard and consider extensions of the problem, e.g., other board topologies and dimensions. For all solution constructions, we either give the construction, an outline of it, or a reference. In our analysis of the modular board, we give a simple result for finding the intersections of diagonals. We then investigate a number of open research areas for the problem, stating several existing and new conjectures.
Along with the known results for \(n\)-queens that we discuss, we also give a history of the problem. In particular, we note that the first proof that \(n\) nonattacking queens can always be placed on an \(n\times n\) board for \(n>3\) is by E. Pauls [“Das Maximalproblem der Damen auf dem Schachbrette. II,” Deutsche Schachzeitung. Organ für das Gesamte Schachleben 29, No.9, 257–267 (1874)], rather than by W. Ahrens [Mathematische Unterhaltungen und Spiele, Leipzig: B.G. Teubner (1901; JFM 31.0220.02), Chapter IX] who is typically cited. We have attempted in this paper to discuss all the mathematical literature in all languages on the \(n\)-queens problem. However, we look only briefly at computational approaches.

MSC:

05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05-03 History of combinatorics
01A55 History of mathematics in the 19th century
05C85 Graph algorithms (graph-theoretic aspects)

Citations:

JFM 31.0220.02

Software:

OEIS; FreeSquares
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahrens, W., Mathematische Unterhaltungen und Spiele, vol. 1 (1901), B.G. Teubner: B.G. Teubner Leipzig, (Chapter IX)
[2] Ahrens, W., Mathematische Spiele, (Meyer, W. F., Encyklopädie der mathematischen Wissenschaften mit Einschluss ihrer Anwendungen, vol. 1 (1904), B.G. Teubner: B.G. Teubner Leipzig), 1080-1093
[3] Alavi, Y.; Lick, D. R.; Liu, J., Strongly diagonal Latin squares and permutation cubes, (Proceedings of the Twenty-fifth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1994), vol. 102 (1994)), 65-70 · Zbl 0835.05010
[4] L. Allison, C. Yee, M. McGaughey, Three dimensional queens problem, Technical Report 89/130, Dept. Computer Science, Monash University, Victoria, Australia, August 1989; L. Allison, C. Yee, M. McGaughey, Three dimensional queens problem, Technical Report 89/130, Dept. Computer Science, Monash University, Victoria, Australia, August 1989
[5] Alvis, D.; Kinyon, M., Birkhoff’s theorem for panstochastic matrices, Amer. Math. Monthly, 108, 1, 28-37 (2001) · Zbl 1004.15024
[6] Ambrus, G.; Barát, J., A contribution to queens graphs: A substitution method, Discrete Math., 306, 12, 1105-1114 (2006) · Zbl 1094.05037
[7] Andrews, W. S., Magic Squares and Cubes (With chapters by other writers) (1960), Dover Publications Inc.: Dover Publications Inc. New York · Zbl 1003.05500
[8] Atkin, A. O.L.; Hay, L.; Larson, R. G., Enumeration and construction of pandiagonal Latin squares of prime order, Comput. Math. Appl., 9, 2, 267-292 (1983) · Zbl 0528.05007
[9] Barr, J.; Rao, S., The \(n\)-queens problem in higher dimensions, Elem. Math., 61, 4, 133-137 (2006) · Zbl 1130.05002
[10] Barwell, B., Solution to problem 811, J. Recreational Math., 13, 1, 61 (1980-1981)
[11] Beasley, J. D., (The mathematics of games. The mathematics of games, Recreations in Mathematics, vol. 5 (1989), The Clarendon Press Oxford University Press: The Clarendon Press Oxford University Press New York)
[12] Behmann, H., Das gesamte Schachbrett unter Beachtung der Regeln des Achtköniginnenproblems zu besetzen, Mathematisch-Naturwissenschaftliche Blätter. Organ des Arnstädter Verbandes mathematischer und naturwissenschaftlicher Vereine an Deutschen Hochschulen, 8, 87-89 (1910)
[13] Beineke, L. W.; Broere, I.; Henning, M. A., Queens graphs, Discrete Math., 206, 1-3, 63-75 (1999), Combinatorics and number theory (Tiruchirappalli, 1996) · Zbl 0935.05064
[14] J. Bell, B. Stevens, Results for the \(n\); J. Bell, B. Stevens, Results for the \(n\) · Zbl 1175.05027
[15] Bell, J.; Stevens, B., Constructing orthogonal pandiagonal Latin squares and panmagic squares from modular \(n\)-queens solutions, J. Combin. Des., 15, 3, 221-234 (2007) · Zbl 1117.05016
[16] Bennett, B. T.; Potts, R. B., Arrays and brooks, J. Austral. Math. Soc., 7, 23-31 (1967) · Zbl 0143.02502
[17] Bennett, G. T., Superimposable solutions for 8×8 board, Messenger Math., 39, 19 (1910)
[18] Berge, C., (Graphes et hypergraphes. Graphes et hypergraphes, Monographies Universitaires de Mathématiques (1970), Dunod: Dunod Paris), No. 37 · Zbl 0213.25702
[19] Bernhardsson, B., Explicit solutions to the n-queens problem for all \(n\), SIGART Bull., 2, 2, 7 (1991)
[20] Bezzel, M., Proposal of 8-queens problem, Berliner Schachzeitung, 3, 363 (1848), Submitted under the author name “Schachfreund”
[21] Blumenthal, L. M., An extension of the Gauss problem of eight queens, Amer. Math. Monthly, 35, 6, 307-309 (1928)
[22] Bode, J.-P.; Harborth, H., Independent chess pieces on Euclidean boards, J. Combin. Math. Combin. Comput., 33, 209-223 (2000), Papers in honour of Ernest J. Cockayne · Zbl 0953.05057
[23] Bruen, A.; Dixon, R., The \(n\)-queens problem, Discrete Math., 12, 4, 393-395 (1975) · Zbl 0365.05017
[24] Burger, A. P.; Mynhardt, C. M.; Cockayne, E. J., Queens graphs for chessboards on the torus, Australas. J. Combin., 24, 231-246 (2001) · Zbl 0979.05080
[25] Burger, A. P.; Mynhardt, C. M.; Cockayne, E. J., Regular solutions of the \(n\)-queens problem on the torus, Util. Math., 65, 219-230 (2004) · Zbl 1052.05057
[26] Bussey, W. H., A note on the problem of eight queens, Amer. Math. Monthly, 29, 7, 252-253 (1922)
[27] Cadoli, M.; Schaerf, M., Partial solutions with unique completion, (Stock, O.; Schaerf, M., Reasoning, Action and Interaction in AI Theories and Systems. Essays Dedicated to Luigia Carlucci Aiello. Reasoning, Action and Interaction in AI Theories and Systems. Essays Dedicated to Luigia Carlucci Aiello, Lecture Notes in Computer Science, vol. 4155 (2006), Spinger)
[28] Cairns, G., Pillow chess, Math. Mag., 75, 3, 173-186 (2002)
[29] Cairns, G., Queens on non-square tori, Electron. J. Combin., 8, N, 6 (2004)
[30] Campbell, P. J., Gauss and the eight queens problem: A study in miniature of the propagation of historical error, Historia Math., 4, 4, 397-404 (1977) · Zbl 0384.01008
[31] Carter, T. A.; Weakley, W. D., The \(n\)-queens problem with diagonal constraints, J. Combin. Math. Combin. Comput., 53, 165-178 (2005) · Zbl 1146.05310
[32] Chandra, A. K., Independent permutations, as related to a problem of Moser and a theorem of Pólya, J. Combin. Theory Ser. A, 16, 111-120 (1974) · Zbl 0273.05008
[33] R.D. Chatham, M. Doyle, G.H. Fricke, J. Reitmann, R.D. Skaggs, M. Wolff, Independence and domination separation on chessboard graphs, J. Comb. Math. Comb. Comput. (in press); R.D. Chatham, M. Doyle, G.H. Fricke, J. Reitmann, R.D. Skaggs, M. Wolff, Independence and domination separation on chessboard graphs, J. Comb. Math. Comb. Comput. (in press) · Zbl 1176.05051
[34] Chatham, R. D.; Fricke, G. H.; Skaggs, R. D., The Queens separation problem, Util. Math., 69, 129-141 (2006) · Zbl 1101.05023
[35] Chen, M., The maximum number of mutually uncapturable strong queens, J. of Qinghai Normal University (Natural Science), 1, 9-12 (1991)
[36] M. Chen, R. Sun, J. Zhu, Partial \(nn\); M. Chen, R. Sun, J. Zhu, Partial \(nn\)
[37] Chen, M.; Sun, R.; Zhu, J., Partial \(n\)-solutions to the modular \(n\)-queen problem, Chinese Sci. Bull., 37, 17, 1422-1425 (1992) · Zbl 0764.05017
[38] Chen, M.; Sun, R.; Zhu, J., Partial \(n\)-solution to the modular \(n\)-queens problem. II, (Combinatorics and graph theory (Hefei, 1992) (1993), World Sci. Publishing: World Sci. Publishing River Edge, NJ), 1-4 · Zbl 0833.05014
[39] V. Chvátal, Colouring the queen graphs. http://www.cs.concordia.ca/ chvatal/queengraphs.html; V. Chvátal, Colouring the queen graphs. http://www.cs.concordia.ca/ chvatal/queengraphs.html
[40] Clark, D. S., A combinatorial theorem on circulant matrices, Amer. Math. Monthly, 92, 10, 725-729 (1985) · Zbl 0604.05009
[41] Clark, D. S.; Shisha, O., Proof without words: Inductive construction of an infinite chessboard with maximal placement of nonattacking queens, Math. Mag., 61, 2, 98 (1988)
[42] Clark, D. S.; Shisha, O., Invulnerable queens on an infinite chessboard, (Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985). Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985), Ann. New York Acad. Sci., vol. 555 (1989), New York Acad. Sci.: New York Acad. Sci. New York), 133-139 · Zbl 0714.05005
[43] Colbourn, C. J.; Rosa, A., (Triple systems. Triple systems, Oxford Mathematical Monographs (1999), The Clarendon Press Oxford University Press: The Clarendon Press Oxford University Press New York) · Zbl 0938.05009
[44] Cull, P.; Pandey, R., Isomorphism and the \(n\)-queens problem, SIGCSE Bull., 26, 3, 29-36 (1994)
[45] Cvetković, D., Some remarks on the problem of \(n\) queens, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz. No., 274-301, 290, 100-102 (1969) · Zbl 0215.33904
[46] Dean, D. S.; Parisi, G., Statistical mechanics of a two-dimensional system with long-range interactions, J. Phys. A, 31, 17, 3949-3960 (1998) · Zbl 0905.60080
[47] Del Manzano, H. A.; Echevaria, C.; Steinberg, L., Quantum algorithm for \(n\)-queens problem, (Computing Research Conference (2002), Mayagüez: Mayagüez Puerto Rico)
[48] Demirörs, O.; Rafraf, N.; Tanik, M. M., Obtaining \(N\)-queens solutions from magic squares and constructing magic squares from \(n\)-queens solutions, J. Recreational Math., 24, 4, 272-280 (1992)
[49] O. Demirörs, M.M. Tanik, Peaceful queens and magic squares. Technical Report 91-CSE-7, Dept. of Comp. Sci. and Eng., Southern Methodist University, 1991; O. Demirörs, M.M. Tanik, Peaceful queens and magic squares. Technical Report 91-CSE-7, Dept. of Comp. Sci. and Eng., Southern Methodist University, 1991
[50] Dietrich, H.; Harborth, H., Independence on triangular triangle boards, Abh. Braunschw. Wiss. Ges., 54, 73-87 (2005) · Zbl 1079.05019
[51] Dudeney, H. E., Amusements in Mathematics (1959), Dover Publications Inc.: Dover Publications Inc. New York
[52] Eickenscheidt, B., Das \(n\)-Damen-Problem auf dem Zylinderbrett, Feenschach, 50, 382-385 (1980)
[53] C. Erbas, N. Rafraf, M.M. Tanik, Magic squares constructing by the uniform step method provide solutions to the \(n\); C. Erbas, N. Rafraf, M.M. Tanik, Magic squares constructing by the uniform step method provide solutions to the \(n\)
[54] C. Erbas, S. Sarkeshik, M.M. Tanik, Algorithmic and constructive approaches to the \(n\); C. Erbas, S. Sarkeshik, M.M. Tanik, Algorithmic and constructive approaches to the \(n\)
[55] Erbas, C.; Sarkeshik, S.; Tanik, M. M., Different perspectives of the \(n\)-queens problem, (Proceedings of the 1992 ACM Annual Conference on Communications (1992), ACM Press), 99-108
[56] C. Erbas, M.M. Tanik, \(N\); C. Erbas, M.M. Tanik, \(N\) · Zbl 0858.05002
[57] C. Erbas, M.M. Tanik, \(N\); C. Erbas, M.M. Tanik, \(N\) · Zbl 0858.05002
[58] C. Erbas, M.M. Tanik, Storage schemes for parallel memory systems and the \(n\); C. Erbas, M.M. Tanik, Storage schemes for parallel memory systems and the \(n\)
[59] Erbas, C.; Tanik, M. M., Generating solutions to the \(N\)-queens problem using 2-circulants, Math. Mag., 68, 5, 343-356 (1995) · Zbl 0858.05002
[60] Erbas, C.; Tanik, M. M.; Aliyazicioglu, Z., Linear congruence equations for the solutions of the \(N\)-queens problem, Inform. Process. Lett., 41, 6, 301-306 (1992) · Zbl 0764.68102
[61] C. Erbas, M.M. Tanik, Z. Aliyazicioglu, A note on Falkowski’s \(N\); C. Erbas, M.M. Tanik, Z. Aliyazicioglu, A note on Falkowski’s \(N\) · Zbl 0764.68102
[62] Erbas, C.; Tanik, M. M.; Nair, V. S.S., A circulant matrix based approach to storage schemes for parallel memory systems, (Proceedings of the Fifth IEEE Symposium on Parallel and Distributed Processing (Dallas, Texas, Dec. 1-4, 1993) (1993), IEEE), 92-99
[63] Erdem, E.; Lifschitz, V., Tight logic programs, Programming with Answer Sets. Programming with Answer Sets, Theory Pract. Log. Program., 3, 4-5, 499-518 (2003), (special issue) · Zbl 1079.68014
[64] Falkowski, B.-J.; Schmitz, L., A note on the Queens’ problem, Inform. Process. Lett., 23, 1, 39-46 (1986)
[65] Finch, S. R., (Mathematical Constants. Mathematical Constants, Encyclopedia of Mathematics and Its Applications, vol. 94 (2003), Cambridge University Press) · Zbl 1054.00001
[66] Foulds, L. R.; Johnston, D. G., An application of graph theory and integer programming: Chessboard nonattacking puzzles, Math. Mag., 57, 2, 95-104 (1984) · Zbl 0546.05036
[67] Franel, J., \(n\)-queens solution, L’Intermédiaire des mathématiciens Ser. 1, 1, 140-141 (1894), Article no. 123
[68] Fricke, G. H.; Hedetniemi, S. M.; Hedetniemi, S. T.; McRae, A. A.; Wallis, C. K.; Jacobson, M. S.; Martin, H. W.; Weakley, W. D., Combinatorial problems on chessboards: a brief survey, (Graph theory, combinatorics, and algorithms, Vol. 1, 2 (Kalamazoo, MI, 1992) (1995), Wiley-Intersci. Publ.: Wiley-Intersci. Publ. Wiley, New York), 507-528 · Zbl 0843.05061
[69] Gardner, M., Patterns in primes are a clue to the strong law of small numbers, Sci. Am., 243, 6, 18-28 (1980)
[70] Gardner, M., Further Mathematical Diversions: The Paradox of the Unexpected Hanging and Others (1995), Mathematical Association of America · Zbl 0842.00006
[71] Gardner, M., Chess queens and maximum unattacked cells, Math. Horizons, 7, November, 12-16 (1999)
[72] Garey, M. R.; Johnson, D. S., Computers and intractability (1979), W.H. Freeman and Co.: W.H. Freeman and Co. San Francisco, CA, A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences · Zbl 0411.68039
[73] Garner, C. W.L.; Herzberg, A. M., On McCarty’s queen squares, Amer. Math. Monthly, 88, 8, 612-613 (1981) · Zbl 0476.05019
[74] Gauß, C. F., Werke. Band XII (1973), Georg Olms Verlag, Hildesheim, Reprint of the 1929 original · Zbl 0924.01032
[75] Gik, E. Y., Matematika na shakhmatnoi doske (1976), Nauchno-populiarnaia seriia.: Nauchno-populiarnaia seriia. Nauka, Moscow
[76] E.Y. Gik, Shakhmaty i matematika, vol. 24, Bibliotechka Kvant, Nauka, Moscow, 1983; E.Y. Gik, Shakhmaty i matematika, vol. 24, Bibliotechka Kvant, Nauka, Moscow, 1983 · Zbl 0561.90099
[77] Ginsburg, T., Gauss’s arithmetization of the problem of 8-queens, I, Scripta Math., 5, 1, 63-66 (1938)
[78] Glaisher, J. W.L., On the problem of eight queens, Phil. Mag. Ser. 4, 48, 320, 457-467 (1874)
[79] Goldberg, M., Coloring a chessboard. E1782, Amer. Math. Monthly, 73, 6, 670-671 (1966)
[80] Goldstein, R. A., Toroidal n-queens problem, E2698, Amer. Math. Monthly, 86, 4, 309-310 (1979)
[81] Golomb, S. W., Sphere packing, coding metrics, and chess puzzles, (Proc. Second Chapel Hill Conf. on Combinatorial Mathematics and its Applications (Univ. North Carolina, Chapel Hill, NC, 1970) (1970), Univ. North Carolina: Univ. North Carolina Chapel Hill, NC), 176-189 · Zbl 0218.05016
[82] Golomb, S. W.; Taylor, H., Constructions and properties of Costas arrays, Proc. IEEE, 72, 9, 1143-1163 (1984) · Zbl 1200.05043
[83] (Golombeck, H., Golombeck’s Encyclopedia of Chess (1977), Crown Publishers: Crown Publishers New York)
[84] R. Gómez, On the \(dn\); R. Gómez, On the \(dn\)
[85] R. Gómez, J.J. Montellano, R. Strausz, On the modular \(n\); R. Gómez, J.J. Montellano, R. Strausz, On the modular \(n\)
[86] Gosset, T., The eight queens problem, Messenger Math., 44, 48 (1914)
[87] Gu, J., On a general framework for large-scale constraint-based optimization, SIGART Bull., 2, 2, 8 (1991)
[88] Günther, S., Zur mathematischen Theorie des Schachbretts, Arch. Math. Phys., 56, 3, 281-292 (1874)
[89] Guy, R. K., (Unsolved Problems in Number Theory. Unsolved Problems in Number Theory, Problem Books in Mathematics (1994), Springer-Verlag: Springer-Verlag New York), Unsolved Problems in Intuitive Mathematics, I · Zbl 0805.11001
[90] Hansche, B.; Vucenic, W., On the \(n\)-queens problems, 73T-A262, Notices Amer. Math. Soc., 20, 568 (1973)
[91] Harborth, H.; Kultan, V.; Nyaradyova, K.; Spendelova, Z., Independence on triangular hexagon boards, (Proceedings of the Thirty-Fourth Southeastern International Conference on Combinatorics, Graph Theory and Computing, vol. 160 (2003)), 215-222 · Zbl 1050.05097
[92] Hayes, P., A problem of chess queens, J. Recreational Math., 24, 264-271 (1992)
[93] Hedayat, A., A complete solution to the existence and nonexistence of Knut Vik designs and orthogonal Knut Vik designs, J. Combin. Theory Ser. A, 22, 3, 331-337 (1977) · Zbl 0353.05025
[94] Heden, O., On the modular \(n\)-queen problem, Discrete Math., 102, 2, 155-161 (1992) · Zbl 0752.05022
[95] Heden, O., Maximal partial spreads and the modular \(n\)-queen problem, Discrete Math., 120, 1-3, 75-91 (1993) · Zbl 0784.51007
[96] Heden, O., Maximal partial spreads and the modular \(n\)-queen problem. II, Discrete Math., 142, 1-3, 97-106 (1995) · Zbl 0831.51006
[97] Heden, O., Maximal partial spreads and the modular \(n\)-queen problem. III, Discrete Math., 243, 1-3, 135-150 (2002) · Zbl 0993.51002
[98] Hedetniemi, S. M.; Hedetniemi, S. T.; Reynolds, R., Combinatorial problems on chessboards: II, (Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Domination in Graphs (1998), Marcel Dekker: Marcel Dekker New York), 133-162 · Zbl 0888.05036
[99] Hernández, J.; Robert, L., Figures of constant width on a chessboard, Amer. Math. Monthly, 112, 1, 42-50 (2005) · Zbl 1120.05300
[100] Herzberg, A. M.; Garner, C. W.L., Latin queen squares, Util. Math., 20, 143-154 (1981) · Zbl 0449.05008
[101] Hoffman, E. J.; Loessi, J. C.; Moore, R. C., Constructions for the solution of the \(m\) queens problem, Math. Mag., 42, 66-72 (1969) · Zbl 0331.05017
[102] Hollander, D. H., An unexpected two-dimensional space-group containing seven of the twelve basic solutions to the eight queens problem, J. Recreational Math., 6, 4, 287-291 (1973) · Zbl 0312.05006
[103] Hsiang, J.; Hsu, D. F.; Shieh, Y.-P., On the hardness of counting problems of complete mappings, Discrete Math., 277, 1-3, 87-100 (2004) · Zbl 1069.68050
[104] J. Hsiang, Y. Shieh, Y. Chen, The cyclic complete mapppings counting problems. Federated Logic Conference, 2002, July 20-August 1, Copenhagen; J. Hsiang, Y. Shieh, Y. Chen, The cyclic complete mapppings counting problems. Federated Logic Conference, 2002, July 20-August 1, Copenhagen
[105] Huff, G. B., On pairings of the first \(2 n\) natural numbers, Acta. Arith., 23, 117-126 (1973) · Zbl 0228.10012
[106] Hukushima, K., Extended ensemble Monte Carlo approach to hardly relaxing problems, Comput. Phys. Commun., 147, 77-82 (2002) · Zbl 0996.82057
[107] Hwang, F. K.; Lih, K. W., Latin squares and superqueens, J. Combin. Theory Ser. A, 34, 1, 110-114 (1983) · Zbl 0507.05022
[108] Iyer, M. R.; Menon, V. V., On coloring the \(n \times n\) chessboard, Amer. Math. Monthly, 73, 721-725 (1966) · Zbl 0144.23202
[109] Katzman, M., Counting monomials, J. Algebraic Combin., 22, 3, 331-341 (2005) · Zbl 1111.13021
[110] Kazarin, L. S.; Kopylov, G. N.; Timofeev, E. A., The chromatic number of a special class of graphs, Vestnik Jaroslav Univ., Vyp. 9, 37-46 (1975)
[111] Khan, S. U., Combinatorial games: Modular \(n\)-queen, Geombinatorics, 12, 4, 217-221 (2003) · Zbl 1061.05023
[112] Kim, S., Problem 811, J. Recreational Math., 12, 1, 53 (1979/1980)
[113] K. Kise, T. Katagiri, H. Honda, T. Yuba, Solving the 24-queens problem using MPI on a PC cluster, Technical Report UEC-IS-2004-6, Graduate School of Information Systems, The University of Electro-Communication, June 2004; K. Kise, T. Katagiri, H. Honda, T. Yuba, Solving the 24-queens problem using MPI on a PC cluster, Technical Report UEC-IS-2004-6, Graduate School of Information Systems, The University of Electro-Communication, June 2004
[114] Klarner, D. A., The problem of reflecting queens, Amer. Math. Monthly, 74, 953-955 (1967) · Zbl 0168.26202
[115] Klarner, D. A., Queen squares, J. Recreational Math., 12, 3, 177-178 (1979/1980)
[116] Kløve, T., The modular \(n\)-queen problem, Discrete Math., 19, 3, 289-291 (1978,1977) · Zbl 0378.05026
[117] Kløve, T., The modular \(n\)-queen problem. II, Discrete Math., 36, 1, 33-48 (1981) · Zbl 0465.05021
[118] Knuth, D., Dancing links, (Davies, J.; Roscoe, B.; Woodcock, J., Millenial Perspectives in Computer Science (2000), Palgrave: Palgrave Houndmills, Basingstoke, Hampshire), 187-214
[119] Koshy, T., Elementary Number Theory with Applications (2001), Harcourt Academic Press: Harcourt Academic Press San Diego
[120] V. Kotěšovec, Mezi šachovnicí a počítačem, 1996. Self-published book. Available online at http://web.iol.cz/vaclav.kotesovec/; V. Kotěšovec, Mezi šachovnicí a počítačem, 1996. Self-published book. Available online at http://web.iol.cz/vaclav.kotesovec/
[121] Kovalenko, Ī. N., On an upper bound for the number of complete mappings, Cybernet. Syst. Anal., 32, 1, 65-68 (1996) · Zbl 0877.05003
[122] Kraitchik, M., Mathematical recreations (1953), Dover Publications Inc.: Dover Publications Inc. New York, NY · Zbl 0051.00607
[123] Kreuzer, M.; Robbiano, L., Computational commutative algebra. 2 (2005), Springer-Verlag: Springer-Verlag Berlin · Zbl 1090.13021
[124] Kunde, M.; Gürtzig, K., Efficient sorting and routing on reconfigurable meshes using restricted bus length, (Proceedings of the 11th International Parallel Processing Symposium (IPPS 1997), April 1-5, 1997, Geneva, Switzerland (1997), IEEE Computer Society), 713-720
[125] Laparewicz, A., Królowe na szachnownicy, Wektor. Mathematische-physikalische Zeitschrift, 1, 6, 326-336 (1912/1913)
[126] Larson, L. C., A theorem about primes proved on a chessboard, Math. Mag., 50, 2, 69-74 (1977) · Zbl 0357.10003
[127] R. Laskar, A. McRae, C. Wallis, Domination in triangulated chessboard graphs. In: Proceedings of the Thirty-Fourth Southeastern International Conference on Combinatorics, Graph Theory and Computing, vol. 163, 2003, pp. 107-123; R. Laskar, A. McRae, C. Wallis, Domination in triangulated chessboard graphs. In: Proceedings of the Thirty-Fourth Southeastern International Conference on Combinatorics, Graph Theory and Computing, vol. 163, 2003, pp. 107-123 · Zbl 1046.05056
[128] Laskar, R.; Wallis, C., Chessboard graphs, related designs, and domination parameters, J. Statist. Plann. Inference, 76, 1-2, 285-294 (1999) · Zbl 0939.05065
[129] Le, M. H.; Li, W.; Wang, E. T., A generalization of the \(n\) queen problem, J. Systems Sci. Math. Sci., 9, 2, 158-168 (1989) · Zbl 0688.05015
[130] Le, M. H.; Li, W.; Wang, E. T., A generalization of the \(n\)-queen problem, Systems Sci. Math. Sci., 3, 2, 183-192 (1990) · Zbl 0733.05022
[131] Li, P.; Guangxi, Z.; Xiao, L., The low-density parity-check codes based on the \(n\)-queen problem, (NRBC’04: Proceedings of the 2004 ACM Workshop on Next-Generation Residential Broadband Challenges (2004), ACM Press: ACM Press New York, NY, USA), 37-41
[132] Lionnet, F. J.E., Question 963, Nouvelles Annales de Mathématiques Ser. 2, 8, 560 (1869)
[133] Lucas, E., Question 123, L’Intermédiaire des mathématiciens Ser. 1, 1, 67 (1894)
[134] E. Lucas, Récréations mathématiques. 2ième éd., nouveau tirage. Librairie Scientifique et Technique Albert Blanchard, Paris, 1973; E. Lucas, Récréations mathématiques. 2ième éd., nouveau tirage. Librairie Scientifique et Technique Albert Blanchard, Paris, 1973 · Zbl 0088.00101
[135] Madachy, J. S., Madachy’s Mathematical Recreations (1979), Dover: Dover New York
[136] McCarty, C. P., Queen squares, Amer. Math. Monthly, 85, 5, 578-580 (1978) · Zbl 0379.05003
[137] McKay, B. D.; McLeod, J. C.; Wanless, I. M., The number of transversals in a Latin square, Des. Codes Cryptogr., 40, 3, 269-284 (2006) · Zbl 1200.05039
[138] Monsky, P., (Superimposable solutions) E2698, Amer. Math. Monthly, 85, 2, 116-117 (1978)
[139] Monsky, P., (Partial solutions) E3162, Amer. Math. Monthly, 93, 7, 565-566 (1986)
[140] Monsky, P., (Partial solutions) E3162, Amer. Math. Monthly, 96, 3, 258-259 (1989)
[141] Nauck, F., Briefwechseln mit allen für alle, Illustrirte Zeitung, 15, 377, 182 (1850), September 21 ed
[142] Nivasch, G.; Lev, E., Nonattacking queens on a triangle, Math. Mag., 78, 5, 399-403 (2005) · Zbl 1081.05003
[143] Nudelman, S. P., The modular \(n\)-queens problem in higher dimensions, Discrete Math., 146, 1-3, 159-167 (1995) · Zbl 0837.05009
[144] Okunev, L. Y., Kombinatornye zadachi na shakhmatnoi doske (1935), ONTI: ONTI Moscow, Leningrad
[145] Panayotopoulos, A., Generating stable permutations, Discrete Math., 62, 2, 219-221 (1986) · Zbl 0611.05001
[146] T. Parmentier, Probléme des \(n\); T. Parmentier, Probléme des \(n\)
[147] Pauls, E., Das Maximalproblem der Damen auf dem Schachbrete, Deutsche Schachzeitung. Organ für das Gesammte Schachleben, 29, 5, 129-134 (1874)
[148] Pauls, E., Das Maximalproblem der Damen auf dem Schachbrete, II, Deutsche Schachzeitung. Organ für das Gesammte Schachleben, 29, 9, 257-267 (1874)
[149] Petković, M., Mathematics and Chess (1997), Dover Publications Inc.: Dover Publications Inc. Mineola, NY, 110 entertaining problems and solutions
[150] Pickover, C. A., The Zen of Magic Squares, Circles, and Stars (2002), Princeton University Press: Princeton University Press Princeton, NJ, An exhibition of surprising structures across dimensions · Zbl 1002.00003
[151] Planck, C., The \(n\) queens problem, British Chess Mag., 20, 4, 94-97 (1900), March 1
[152] Polster, B., A Geometrical Picture Book (1998), Springer · Zbl 0914.51001
[153] Pólya, G., Über die “doppelt-periodischen” Losüngen des \(n\)-Damen-Problems, (Ahrens, W., Mathematische Unterhaltungen und Spiele, vol. 2 (1918), B.G. Teubner), 364-374
[154] Poulet, P., Suites de nombres, L’Intermédiaire des mathématiciens Ser. 2, 1, 92-93 (1922)
[155] Qiu, W. S., The \(n\) queens problem, J. Math. (Wuhan), 6, 2, 117-130 (1986) · Zbl 0614.05011
[156] Reichling, M., A simplified solution of the \(n\) Queens’ problem, Inform. Process. Lett., 25, 4, 253-255 (1987) · Zbl 0637.05003
[157] Rivin, I.; Vardi, I.; Zimmermann, P., The \(n\)-queens problem, Amer. Math. Monthly, 101, 7, 629-639 (1994) · Zbl 0825.68479
[158] Rouse Ball, W. W., Mathematical Recreations and Problems of Past and Present Times (1892), Macmillan and Co.: Macmillan and Co. London
[159] Sagols, F.; Colbourn, C. J., NS1D0 sequences and anti-Pasch Steiner triple systems, Ars Combin., 62, 17-31 (2002) · Zbl 1074.05018
[160] Sainte-Laguë, A., (Les réseaux (ou graphes). Les réseaux (ou graphes), Mémorial des sciences mathématiques, vol. 18 (1926), Gauthier-Villars: Gauthier-Villars Paris)
[161] Scheid, F., Some packing problems, Amer. Math. Monthly, 67, 3, 231-235 (1960) · Zbl 0092.01304
[162] K. Schlude, E. Specker, Zum Problem der Damen auf dem Torus, Technical Report 412, Departement Informatik, Eidgenössische Technische Hochschule Zürich (ETH Zürich), July 2003; K. Schlude, E. Specker, Zum Problem der Damen auf dem Torus, Technical Report 412, Departement Informatik, Eidgenössische Technische Hochschule Zürich (ETH Zürich), July 2003 · Zbl 1235.05028
[163] Schroeder, M., Fractals, Chaos, Power Laws: Minutes from an Infinite Paradise (1991), W.H. Freeman and Company: W.H. Freeman and Company New York · Zbl 0758.58001
[164] Sebastian, J. D., Some computer solutions to the reflecting queens problem, Amer. Math. Monthly, 76, 399-400 (1969) · Zbl 0322.05003
[165] Selfridge, J. L., Abstract 63T-80, Notices Amer. Math. Soc., 10, 195 (1963)
[166] Sforza, G., Una regola pel gioco della \(n\) regine quando \(n\) è primo, Periodico di matematiche. Organo della Mathesis, Società Italiana di Scienze Mathematiche e Fisiche, 5, 4, 107-109 (1925)
[167] Shapiro, H. D., Generalized Latin squares on the torus, Discrete Math., 24, 1, 63-77 (1978) · Zbl 0409.05017
[168] Shapiro, H. D., Theoretical limitations on the efficient use of parallel memories, IEEE Transactions on Computers, C-27, 5, 421-428 (1978) · Zbl 0379.68043
[169] Shen, M.-K.; Shen, T.-P., Problem 39, Bull. Amer. Math. Soc., 68, 557 (1962)
[170] Yang, S.-W.; Wang, C.-N.; Liu, C.-M.; Chiang, T.-H., (Shum, H.-Y., Fast motion estimation using N-queen pixel decimation. Fast motion estimation using N-queen pixel decimation, Lecture Notes in Computer Science, vol. 2195 (2001), Spring-Verlag: Spring-Verlag Berlin) · Zbl 1031.68963
[171] Slater, M., Research problem 1, Bull. Amer. Math. Soc, 69, 333 (1963)
[172] N.J.A. Sloane, The on-line encyclopedia of integer sequences. http://www.research.att.com/ njas/sequences/; N.J.A. Sloane, The on-line encyclopedia of integer sequences. http://www.research.att.com/ njas/sequences/ · Zbl 1274.11001
[173] Sprague, T. B., On the eight queens problem, Proc. Edinburgh Math. Soc., 17, 43-68 (1899)
[174] Stanley, R. P., Enumerative Combinatorics, Volume I, (The Wadsworth & Brooks/Cole Mathematics Series (1986), Wadsworth & Brooks/Cole Advanced Books & Software: Wadsworth & Brooks/Cole Advanced Books & Software Monterey, California) · Zbl 0978.05002
[175] Stern, E., Über irreguläre pandiagonale lateinische Quadrate mit Primzahlseitenlänge und ihre Bedeutung fur das \(n\)-Königinnenproblem sowie für die Bildung magischer Quadrate, Nieuw Archief voor Wiskunde, 19, 257-270 (1938)
[176] Stern, E., General formulas for the number of magic squares belonging to certain classes, Amer. Math. Monthly, 46, 555-581 (1939)
[177] Stoffel, A., Totally diagonal Latin squares, Stud. Cerc. Mat., 28, 1, 113-119 (1976) · Zbl 0325.05013
[178] A. Sumitaka, Explicit solutions of the \(n\); A. Sumitaka, Explicit solutions of the \(n\)
[179] M.M. Tanik, A graph model for deadlock prevention, Ph.D. Thesis, Texas A & M University, 1978; M.M. Tanik, A graph model for deadlock prevention, Ph.D. Thesis, Texas A & M University, 1978
[180] Tarry, H., Problème des reines, L’Intermédiaire des mathématiciens Ser. 1, 2, 205 (1895), Problem 605
[181] H. Tarry, Problème des \(n n^2\); H. Tarry, Problème des \(n n^2\)
[182] Taylor, H., Florentine rows or left-right shifted permutation matrices with cross-correlation values \(\leq 1\), Discrete Math., 93, 2-3, 247-260 (1991) · Zbl 0758.05031
[183] Taylor, H., Singly periodic Costas arrays are equivalent to polygonal path Vatican squares, (Mathematical properties of sequences and other combinatorial structures (Los Angeles, CA, 2002) (2003), Kluwer Acad. Publ.: Kluwer Acad. Publ. Boston, MA), 45-53 · Zbl 1026.05014
[184] Theron, W. F.D.; Burger, A. P., Queen domination of hexagonal hives, J. Combin. Math. Combin. Comput., 32, 161-172 (2000) · Zbl 0947.05060
[185] Tolpygo, A., Queens on a cylinder, Quantum, 6, May/June, 38-42 (1996)
[186] Vaderlind, P.; Guy, R. K.; Larson, L. C., (The Inquisitive Problem Solver. The Inquisitive Problem Solver, MAA Problem Books Series (2002), Mathematical Association of America: Mathematical Association of America Washington, DC) · Zbl 1067.00006
[187] Van Rees, G. H.J., On Latin queen squares, (Proceedings of the Tenth Manitoba Conference on Numerical Mathematics and Computing, Vol. II (Winnipeg, Man., 1980), vol. 31 (1981)), 267-273 · Zbl 0513.05024
[188] Vardi, I., Computational recreations in Mathematica (1991), Addison-Wesley Publishing Company Advanced Book Program: Addison-Wesley Publishing Company Advanced Book Program Redwood City, CA · Zbl 0786.11002
[189] Vasquez, M., New result on the queens \(n^2\) graph coloring problem, J. Heuristics, 10, 407-413 (2004)
[190] M. Vasquez, On the queen graph coloring problem, in: Proceedings of the 3rd International Conference on Information INFO’04, Tokyo, Japan, November 29-December 2, 2004, pages 109-112, 2004; M. Vasquez, On the queen graph coloring problem, in: Proceedings of the 3rd International Conference on Information INFO’04, Tokyo, Japan, November 29-December 2, 2004, pages 109-112, 2004
[191] Vasquez, M., Coloration des graphes de reines, C. R. Math. Acad. Sci. Paris, 342, 3, 157-160 (2006) · Zbl 1082.05042
[192] M. Vasquez, D. Habet, Complete and incomplete algorithms for the queen graph coloring problem. In: Proceedings of the 16th European Conference on Artificial Intelligence (ECAI’04), Valencia, Spain, August 22-27, 2004, pages 226-230, 2004; M. Vasquez, D. Habet, Complete and incomplete algorithms for the queen graph coloring problem. In: Proceedings of the 16th European Conference on Artificial Intelligence (ECAI’04), Valencia, Spain, August 22-27, 2004, pages 226-230, 2004
[193] Wang, C.-N.; Yang, S.-W.; Liu, C.-M.; Chiang, T., A hierarchical decimation lattice based on \(n\)-queen with an application for motion estimation, IEEE Signal Processing Lett., 10, 8, 228-231 (2003)
[194] Wang, C.-N.; Yang, S.-W.; Liu, C.-M.; Chiang, T., A hierarchical \(n\)-queen decimation lattice and hardware architecture for motion estimation, IEEE Trans. Circuits Syst. Video Technol., 14, 4, 429-440 (2004)
[195] Watkins, J. J., Across the Board: The Mathematics of Chessboard Problems (2004), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 1108.00007
[196] Wu, J. B., A solution to the \(n\) queens problem, J. Huazhong Univ. Sci. Tech., 22, Suppl., 195-198 (1994)
[197] Yaglom, A. M.; Yaglom, I. M., Challenging Mathematical Problems with Elementary Solutions. Vol. I: Combinatorial Analysis and Probability Theory (1964), Holden-Day Inc.: Holden-Day Inc. San Francisco, CA, Revised and edited by Basil Gordon · Zbl 0123.24201
[198] Yamamoto, K.; Kitamura, Y.; Yoshikura, H., Computation of statistical secondary structure of nucleic acids, Nucleic Acids Res., 12, 1, 335-346 (1984)
[199] K. Zhao, The combinatorics of chessboards, Ph.D. Thesis, City University of New York, 1998; K. Zhao, The combinatorics of chessboards, Ph.D. Thesis, City University of New York, 1998
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.