A group-based search for solutions of the n-queens problem

被引：9
|
作者：
Engelhardt, Matthias R.
机构：
[1] 90455 Nuernberg
来源：
DISCRETE MATHEMATICS | 2007年 / 307卷 / 21期
关键词：
n-Queens problem; finite group action; complete enumeration; backtracking algorithm;
D O I：
10.1016/j.disc.2007.01.007
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
The n-queens problem is a well-known problem in mathematics, yet a full search for n-queens solutions has been tackled until now using only simple algorithms (with the exception of the Rivin-Zabih algorithm). In this article, we discuss optimizations that mainly rely on group actions on the set of n-queens solutions. Most of our arguments deal with the case of toroidal queens; at the end, the application to the regular n-queens problem is discussed, and also the Rivin-Zabih algorithm. (C) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码：2535 / 2551
页数：17
相关论文
共 50 条
  • [1] FAST SEARCH ALGORITHMS FOR THE N-QUEENS PROBLEM
    SOSIC, R
    GU, J
    IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS, 1991, 21 (06): : 1572 - 1576
  • [2] Regular solutions of the n-queens problem on the torus
    Burger, AP
    Mynhardt, CM
    Cockayne, EJ
    UTILITAS MATHEMATICA, 2004, 65 : 219 - 230
  • [3] THE N-QUEENS PROBLEM
    RIVIN, I
    VARDI, I
    ZIMMERMANN, P
    AMERICAN MATHEMATICAL MONTHLY, 1994, 101 (07): : 629 - 639
  • [4] N-QUEENS PROBLEM
    BRUEN, A
    DIXON, R
    DISCRETE MATHEMATICS, 1975, 12 (04) : 393 - 395
  • [5] An Orbit-based Search Algorithm to Solve N-Queens Problem
    Zhang, Jun
    Zhang, Zili
    MECHANICAL ENGINEERING AND INTELLIGENT SYSTEMS, PTS 1 AND 2, 2012, 195-196 : 1049 - +
  • [6] 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
  • [7] The n-queens completion problem
    Stefan Glock
    David Munhá Correia
    Benny Sudakov
    Research in the Mathematical Sciences, 2022, 9
  • [8] The n-queens completion problem
    Glock, Stefan
    Munha Correia, David
    Sudakov, Benny
    RESEARCH IN THE MATHEMATICAL SCIENCES, 2022, 9 (03)
  • [9] TOROIDAL N-QUEENS PROBLEM
    GOLDSTEIN, RZ
    AMERICAN MATHEMATICAL MONTHLY, 1979, 86 (04): : 309 - 310
  • [10] 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
12345