主题
Search

皇后问题

下载 Mathematica 笔记本下载 Wolfram 笔记本
QueensMax

在 n×n 棋盘上最多可以放置多少个皇后，使得它们互不攻击？答案是对于 n-1 个皇后（当 n=2 或 n=3 时），否则为 n 个皇后。对于通常的 8×8 棋盘，答案是八个皇后（Madachy 1979; Steinhaus 1999, p. 29）。将 n 个皇后放置在 n×n 棋盘上，使任意两个皇后都不能互相攻击的不同方式的数量，对于前几个 n 值，分别是 1, 0, 0, 2, 10, 4, 40, 92, ... (OEIS A000170; Madachy 1979; Steinhaus 1999, p. 29)。这些解的旋转和反射不同的解的数量分别是 1, 0, 0, 1, 2, 1, 6, 12, 46, 92, ... (OEIS A002562; Dudeney 1970; p. 96)。上面说明了 n=8 的 12 个不同的解，其余 80 个解可以通过旋转和反射生成（Madachy 1979, Steinhaus 1999）。

QueensMin

占据或攻击 n×n 棋盘的所有方格所需的最小皇后数（即，n×n 皇后图的支配数）对于 n=1, 2, ... 由 1, 1, 1, 2, 3, 3, 4, 5, 5, 5, 5, 6, 7, 8, 9, 9, 9, 9, 10, ... (OEIS A075458) 给出，其中 Steinhaus 1999 (p. 29) 注释 gamma(Q_(8,8))=5。

Dudeney (1970, pp. 95-96) 给出了 N_p(k,n) 个 k 皇后攻击或占据 n×n 棋盘的每格，且每个皇后都受到至少另一个皇后攻击（“保护”）的不同排列方式的数量的结果，其中 n=8 的值由 Steinhaus (1999, p. 29) 给出。 n=5 情况下的 4860 个解可以从 638 个基本排列方式通过旋转和反射获得。

k 个皇后n×nN_p(k,n)
243
3537
361
475
584860

Dudeney (1970, pp. 95-96) 还给出了 N_u(k,n) 个 k 皇后攻击或占据 n×n 棋盘的每格，且任意两个皇后都不互相攻击（它们是“未受保护的”）的不同排列方式的数量的结果。

k 个皇后n×nN_u(k,n)
121
131
342
352
4617
471
5891

Vardi (1991) 将问题从正方形棋盘推广到具有环面拓扑的棋盘。对于 n 为奇数的 n 个皇后的解的数量为 1, 0, 10, 28, 0, 88, ... (OEIS A007705)。 Vardi (1991) 还考虑了环面“半皇后”问题，其中半皇后可以像车或象移动，但只能在正断开的对角线上移动。对于 n 为奇数的 n 个皇后的这个问题的解的数量为 1, 3, 15, 133, 2025, 37851, ... (OEIS A006717)，对于偶数 n 则为 0。

Velucchi 给出了问题“在 order n 棋盘上可能有多少种不同的 k 皇后排列方式？”的解，即 多项式中 a^kb^(n^2-k) 的系数的 1/8

p(a,b,n)={(a+b)^(n^2)+2(a+b)^n(a^2+b^2)^((n^2-n)/2); +3(a^2+b^2)^(n^2/2)+2(a^4+b^4)^(n^2/4); n even; (a+b)^(n^2)+2(a+b)(a^4+b^4)^((n^2-1)/4); +(a+b)(a^2+b^2)^((n^2-1)/2); +4(a+b)^n(a^2+b^2)^((n^2-n)/2) n odd.
(1)

Velucchi 还考虑了非支配皇后问题，该问题包括在 order n 棋盘上放置 n 个皇后，以留下最大数量 U(n) 的未被攻击的空单元格。前几个值是 0, 0, 0, 1, 3, 5, 7, 11, 18, 22, 30, 36, 47, 56, 72, 82, ... (OEIS A001366)。结果可以推广到 k 个皇后在 n×n 棋盘上的情况。

参见

主教问题, 国际象棋, 国王问题, 骑士问题, 骑士图, 车问题

使用 Wolfram|Alpha 探索

参考文献

Ahrens, W. "Das Achtköniginnenproblem." Ch. 9 in Mathematische Unterhaltungen und Spiele, dritte, verbesserte, anastatisch gedruckte aufl., Bd. 1. Leipzig, Germany: Teubner, pp. 211-284, 1921.Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 166-169, 1987.Campbell, P. J. "Gauss and the 8-Queens Problem: A Study in the Propagation of Historical Error." Historia Math. 4, 397-404, 1977.Chatham, D. "The N+k Queens Problem Page." http://people.moreheadstate.edu/fs/d.chatham/n+kqueens.html.Dudeney, H. E. "The Eight Queens." §300 in Amusements in Mathematics. New York: Dover, pp. 89 and 95-96, 1970.Erbas, C. and Tanik, M. M. "Generating Solutions to the N-Queens Problem Using 2-Circulants." Math. Mag. 68, 343-356, 1995.Erbas, C.; Tanik, M. M.; and Aliyzaicioglu, Z. "Linear Congruence Equations for the Solutions of the N-Queens Problem." Inform. Proc. Let. 41, 301-306, 1992.Gardner, M. "Patterns in Primes Are a Clue to the Strong Law of Small Numbers." Sci. Amer. 243, 18-28, Dec. 1980.Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1983.Ginsburg, J. "Gauss's Arithmetization of the Problem of n Queens." Scripta Math. 5, 63-66, 1939.Guy, R. K. "The n Queens Problem." §C18 in Unsolved Problems in Number Theory, 2nd ed. New York:Springer-Verlag, pp. 133-135, 1994.Kraitchik, M. "The Problem of the Queens" and "Domination of the Chessboard." §10.3 and 10.4 in Mathematical Recreations. New York: W. W. Norton, pp. 247-256, 1942.Madachy, J. S. Madachy's Mathematical Recreations. New York: Dover, pp. 34-36, 1979.Östergård, P. R. J. and Weakley, W. D. "Values of Domination Numbers of the Queen's Graph." Electronic J. Combinatorics 8, No. 1, R29, 1-19, 2001. http://www.combinatorics.org/Volume_8/Abstracts/v8i1r29.html.Pegg, E. Jr. "Math Games: Chessboard Tasks." Apr. 11, 2005. http://www.maa.org/editorial/mathgames/mathgames_04_11_05.html.Riven, I.; Vardi, I.; and Zimmermann, P. "The n-Queens Problem." Amer. Math. Monthly 101, 629-639, 1994.Riven, I. and Zabih, R. "An Algebraic Approach to Constraint Satisfaction Problems." In Proc. Eleventh Internat. Joint Conference on Artificial Intelligence, Vol. 1, August 20-25, 1989. Detroit, MI: IJCAII, pp. 284-289, 1989.Ruskey, F. "Information on the n Queens Problem." http://www.theory.csc.uvic.ca/~cos/inf/misc/Queen.html.Sloane, N. J. A. Sequences A000170/M1958, A001366, A002562/M0180, A006717/M3005, A007705/M4691, and A075458 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. and Plouffe, S. Figure M0180 in The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.Steinhaus, H. Mathematical Snapshots, 3rd ed. New York: Dover, pp. 29-30, 1999.Vardi, I. "The n-Queens Problems." Ch. 6 in Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 107-125, 1991.Velucchi, M. "For Me, This Is the Best Chess-Puzzle: Non-Dominating Queens Problem." http://anduin.eldar.org/~problemi/papers.html.Velucchi, M. "Different Dispositions on the ChessBoard." http://anduin.eldar.org/~problemi/papers.html.Wagon, S. "Graph Theory Problems from Hexagonal and Traditional Chess." College Math. J. 45, 278-287, 2014.Watkins, J. Across the Board: The Mathematics of Chessboard Problems. Princeton, NJ: Princeton University Press, 2004.

引用为

Weisstein, Eric W. "皇后问题。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/QueensProblem.html

学科分类