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 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
  • [2] LINEAR CONGRUENCE EQUATIONS FOR THE SOLUTIONS OF THE N-QUEENS PROBLEM
    ERBAS, C
    TANIK, MM
    ALIYAZICIOGLU, Z
    INFORMATION PROCESSING LETTERS, 1992, 41 (06) : 301 - 306
  • [3] AN ANALYTICAL EVIDENCE FOR KALE HEURISTIC FOR THE N-QUEENS PROBLEM
    OH, SB
    INFORMATION PROCESSING LETTERS, 1993, 46 (01) : 51 - 54
  • [4] A Polynomial-Time DNA Computing Solution for the N-Queens Problem
    Maazallahi, Ramin
    Niknafs, Aliakbar
    Arabkhedri, Paria
    2ND WORLD CONFERENCE ON EDUCATIONAL TECHNOLOGY RESEARCH, 2013, 83 : 622 - 628
  • [5] The N-queens Problem on a symmetric Toeplitz matrix
    Szaniszlo, Zsuzsanna
    Tomova, Maggy
    Wyels, Cindy
    DISCRETE MATHEMATICS, 2009, 309 (04) : 969 - 974
  • [6] Neural networks for the N-Queens Problem: a review
    Mandziuk, J
    CONTROL AND CYBERNETICS, 2002, 31 (02): : 217 - 248
  • [7] Regular solutions of the n-queens problem on the torus
    Burger, AP
    Mynhardt, CM
    Cockayne, EJ
    UTILITAS MATHEMATICA, 2004, 65 : 219 - 230
  • [8] An improved genetic algorithm for the n-queens problem
    Hynek, J
    IC-AI'2000: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 1-III, 2000, : 517 - 522
  • [9] Hysteretic Hopfield network with dynamic tunneling for crossbar switch and N-queens problem
    Thangavel, P.
    Gladis, D.
    NEUROCOMPUTING, 2007, 70 (13-15) : 2544 - 2551
  • [10] Application of Hopfield Neural Network to the N-Queens Problem
    Lapushkin, Andrei A.
    BIOLOGICALLY INSPIRED COGNITIVE ARCHITECTURES (BICA) FOR YOUNG SCIENTISTS, 2016, 449 : 115 - 120
12345