A DYNAMIC-PROGRAMMING SOLUTION TO THE N-QUEENS PROBLEM

被引：11
|
作者：
RIVIN, I
ZABIH, R
机构：
[1] STANFORD UNIV,DEPT COMP SCI,STANFORD,CA 94305
[2] NEC CORP LTD,RES INST,PRINCETON,NJ 08540
来源：
INFORMATION PROCESSING LETTERS | 1992年 / 41卷 / 05期
关键词：
COMBINATORIAL PROBLEMS; DESIGN OF ALGORITHMS; DYNAMIC PROGRAMMING; N-QUEENS PROBLEM; SEARCH PROBLEMS;
D O I：
10.1016/0020-0190(92)90168-U
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
The n-queens problem is to determine in how many ways n queens may be placed on an n-by-n chessboard so that no two queens attack each other under the rules of chess. We describe a simple O(f(n)8n) solution to this problem that is based on dynamic programming, where f(n) is a low-order polynomial. This appears to be the first nontrivial upper bound for the problem.
引用
收藏
页码：253 / 256
页数：4
相关论文
共 50 条
  • [1] A SIMPLIFIED SOLUTION OF THE N-QUEENS PROBLEM
    REICHLING, M
    INFORMATION PROCESSING LETTERS, 1987, 25 (04) : 253 - 255
  • [2] THE N-QUEENS PROBLEM
    RIVIN, I
    VARDI, I
    ZIMMERMANN, P
    AMERICAN MATHEMATICAL MONTHLY, 1994, 101 (07): : 629 - 639
  • [3] N-QUEENS PROBLEM
    BRUEN, A
    DIXON, R
    DISCRETE MATHEMATICS, 1975, 12 (04) : 393 - 395
  • [4] The n-queens completion problem
    Stefan Glock
    David Munhá Correia
    Benny Sudakov
    Research in the Mathematical Sciences, 2022, 9
  • [5] The n-queens completion problem
    Glock, Stefan
    Munha Correia, David
    Sudakov, Benny
    RESEARCH IN THE MATHEMATICAL SCIENCES, 2022, 9 (03)
  • [6] TOROIDAL N-QUEENS PROBLEM
    GOLDSTEIN, RZ
    AMERICAN MATHEMATICAL MONTHLY, 1979, 86 (04): : 309 - 310
  • [7] A Solution to the N-Queens Problem Using Biogeography-Based Optimization
    Habiboghli, Ali
    Jalali, Tayebeh
    INTERNATIONAL JOURNAL OF INTERACTIVE MULTIMEDIA AND ARTIFICIAL INTELLIGENCE, 2017, 4 (04): : 22 - 26
  • [8] A Lower Bound for the n-queens Problem
    Simkin, Michael
    Luria, Zur
    PROCEEDINGS OF THE 2022 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, 2022, : 2185 - 2197
  • [9] The n-queens problem in higher dimensions
    Barr, Jeremiah
    Rao, Shrisha
    ELEMENTE DER MATHEMATIK, 2006, 61 (04) : 133 - 137
  • [10] New Constructions for the n-Queens Problem
    M. Bača
    S. C. López
    F. A. Muntaner-Batle
    A. Semaničová-Feňovčíková
    Results in Mathematics, 2020, 75
12345