主題
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 棋盤上的情況。

參見

主教問題, 國際象棋, 國王問題, 騎士問題, 騎士圖, 車問題

使用 探索

參考文獻

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. "皇后問題。" 來自 Web 資源。 https://mathworld.tw/QueensProblem.html

學科分類