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 条
  • [21] The N-queens Problem on a symmetric Toeplitz matrix
    Szaniszlo, Zsuzsanna
    Tomova, Maggy
    Wyels, Cindy
    DISCRETE MATHEMATICS, 2009, 309 (04) : 969 - 974
  • [22] THE MODULAR N-QUEENS PROBLEM IN HIGHER DIMENSIONS
    NUDELMAN, SP
    DISCRETE MATHEMATICS, 1995, 146 (1-3) : 159 - 167
  • [23] LOCAL SEARCH WITH CONFLICT MINIMIZATION - A CASE-STUDY OF THE N-QUEENS PROBLEM
    SOSIC, R
    GU, J
    IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 1994, 6 (05) : 661 - 668
  • [24] Reducing the time complexity of the n-queens problem
    El-Qawasmeh, E
    Al-Noubani, K
    INTERNATIONAL JOURNAL ON ARTIFICIAL INTELLIGENCE TOOLS, 2005, 14 (03) : 545 - 557
  • [25] 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
  • [26] 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
  • [27] Results for the n-queens problem on the Mobius board
    Bell, Jordan
    Stevens, Brett
    AUSTRALASIAN JOURNAL OF COMBINATORICS, 2008, 42 : 21 - 34
  • [28] Research and Realization of N-Queens Problem Based on the Logic Language Prolog
    Gu, Baolei
    COMPUTATIONAL INTELLIGENCE AND INTELLIGENT SYSTEMS, 2012, 316 : 50 - 56
  • [29] New decision rules for exact search in N-Queens
    San Segundo, Pablo
    JOURNAL OF GLOBAL OPTIMIZATION, 2011, 51 (03) : 497 - 514
  • [30] A modified Hopfield model for solving the N-Queens problem
    da Silva, IN
    de Souza, AN
    Bordon, ME
    IJCNN 2000: PROCEEDINGS OF THE IEEE-INNS-ENNS INTERNATIONAL JOINT CONFERENCE ON NEURAL NETWORKS, VOL VI, 2000, : 509 - 514
12345