“Queens Problem”的概念、定义、习题解题方法及翻译-数学辞典

单词

Queens Problem

释义

Queens Problem

What is the maximum number of queens which can be placed on an Chessboard such that no two attack oneanother? The answer is queens, which gives eight queens for the usual board (Madachy 1979). The numberof different ways the queens can be placed on an chessboard so that no two queens may attack each other forthe first few are 1, 0, 0, 2, 10, 4, 40, 92, ... (Sloane's A000170, Madachy 1979). The number of rotationally andreflectively distinct solutions are 1, 0, 0, 1, 2, 1, 6, 12, 46, 92, ... (Sloane's A002562; Dudeney 1970; p. 96). The 12distinct solutions for are illustrated above, and the remaining 80 are generated by Rotation andReflection (Madachy 1979).

The minimum number of queens needed to occupy or attack all squares of an board is 5. Dudeney (1970, pp. 95-96)gave the following results for the number of distinct arrangements of queens attacking or occupying everysquare of an board for which every queen is attacked (``protected'') by at least one other.

Queens
2	4	3
3	5	37
3	6	1
4	7	5

Dudeney (1970, pp. 95-96) also gave the following results for the number of distinct arrangements of queensattacking or occupying every square of an board for which no two queens attack one another (they are ``notprotected'').

Queens
1	2	1
1	3	1
3	4	2
3	5	2
4	6	17
4	7	1
5	8	91

Vardi (1991) generalizes the problem from a square chessboard to one with the topology of the Torus. The number ofsolutions for queens with A007705). Vardi (1991) also considers thetoroidal ``semiqueens'' problem, in which a semiqueen can move like a rook or bishop, but only on Positive brokendiagonals. The number of solutions to this problem for queens with Odd are 1, 3, 15, 133, 2025, 37851, ...(Sloane's A006717), and 0 for Even .

Chow and Velucchi give the solution to the question, ``How many different arrangements of queens are possible on anorder chessboard?'' as 1/8th of the Coefficient of in the Polynomial

Velucchi also considers the nondominating queens problem, which consists of placing

queens on an order

chessboardto leave a maximum number

of unattacked vacant cells. The first few values are 0, 0, 0, 1, 3, 5, 7, 11, 18, 22, 30,36, 47, 56, 72, 82, ... (Sloane's A001366). The results can be generalized to

queens on an

board.

See also Bishops Problem, Chess, Kings Problem, Knights Problem, Knight's Tour,Rooks Problem

References

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.

Chow, T. and Velucchi, M. ``Different Dispositions in the Chessboard.'' http://www.cli.di.unipi.it/~velucchi/diff.txt.

Dudeney, H. E. ``The Eight Queens.'' §300 in Amusements in Mathematics. New York: Dover, p. 89, 1970.

Erbas, C. and Tanik, M. M. ``Generating Solutions to the -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 -Queens Problem.'' Inform. Proc. Let. 41, 301-306, 1992.

Ginsburg, J. ``Gauss's Arithmetization of the Problem of Queens.'' Scripta Math. 5, 63-66, 1939.

Guy, R. K. ``The 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.

Pólya, G. ``Über die `doppelt-periodischen' Lösungen des -Damen-Problems.'' In Mathematische Unterhaltungen und Spiele (Ed. W. Ahrens). 1918.

Riven, I.; Vardi, I.; and Zimmerman, P. ``The -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 Queens Problem.'' http://sue.csc.uvic.ca/~cos/inf/misc/Queen.html.

Sloane, N. J. A. SequencesA001366,A000170/M1958,A006717/M3005,A007705/M4691,A002562/M0180in ``An On-Line Version of the Encyclopedia of Integer Sequences.''http://www.research.att.com/~njas/sequences/eisonline.html and extended entry in Sloane, N. J. A. and Plouffe, S.The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Vardi, I. ``The -Queens Problems.'' Ch. 6 in Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 107-125, 1991.

Velucchi, M. ``Non-Dominating Queens Problem.'' http://www.cli.di.unipi.it/~velucchi/queens.txt.

随便看

数学辞典收录了8975条数学词条，基本涵盖了常用数学知识及数学英语单词词组的翻译及用法，是数学学习的有利工具。