% This file was created with JabRef 2.4.2.
% Encoding: UTF8
@ARTICLE{Abramson1989,
author = {B. Abramson and M.M. Yung},
title = {Divide and Conquer under Global Constraints: {A} Solution
to the $n$-Queens Problem},
journal = {Journal of Parallel and Distributed Computing},
year = {1989},
volume = {6},
pages = {649-662},
abstract = {Configuring $n$ mutually nonattacking Queens on an $n\times{}n$
chessboard is a classical problem that was first posed over a century
ago. Over the past few decades, this problem has become important
to computer scientists by serving as the standard example of a globally
constrained problem which is solvable using backtracking search methods.
A related problem, placing the $n$-Queens on a toroidal board,
has been discussed in detail by Poyla and Chandra. Their work focused
on characterizing the solvable cases and finding solutions which
arrange the Queens in a regular pattern. This paper describes a
new divide-and-conquer algorithm that solves both problems and investigates
the relationship between them. The connection between the solutions
of the two problems illustrates an important, but frequently overlooked,
method of algorithm design: detailed combinatorial analysis of an
overconstrained variation can reveal solutions to the corresponding
original problem. The solution is an example of solving a globally
constrained problem using the divide-and-conquer technique, rather
than the usual backtracking algorithm. The former is much faster
in both sequential and parallel environments.},
doi = {10.1016/0743-7315(89)90011-7}
}
@INPROCEEDINGS{Abramson1986,
author = {B. Abramson and M.M. Yung},
title = {Construction Through Decomposition: {A} Divide-and-Conquer
Algorithm for the $n$-Queens Problem},
booktitle = {Proceedings of 1986 ACM Fall Joint Computer Conference},
year = {1986},
pages = {620-628}
}
@BOOK{Ahrens1901,
title = {{M}athematische {U}nterhaltungen und {S}piele},
publisher = {B.G. Teubner},
year = {1901},
author = {W. Ahrens},
url = {http://www.archive.org/details/mathunterhaltung00ahrerich},
refersto = {\cite{Nauck1850}},
annote = {Several editions:
1910 (also including \cite{Polya1918});
1921: Dritte, verbesserte, anastatisch gedruckte {A}uflage.
Chapter IX: Das {A}chtk\"oniginnenproblem
See also Chapter X: Die 5 K\"oniginnen auf dem Schachbrett.}
}
@BOOK{Ahrens1902,
annote = {G.1 {M}athematische {S}piele {A}chtdamenproblem},
title = {{E}ncyklop\"adie der {M}athematischen {W}issenschaften, {E}rster {B}and in
Zwei {T}eilen. {Z}weiter {T}eil},
publisher = {B. G. {T}eubner},
year = {1902},
author = {W. Ahrens}
}
@INPROCEEDINGS{Alavi1994,
author = {Y. Alavi and D.R. Lick and J. Liu},
title = {Strongly Diagonal Latin Squares and Permutation Cubes},
booktitle = {Proceedings of the Twenty-ﬁfth Southeastern International Conference on
Combinatorics, Graph Theory and Computing},
year = {1994},
pages = {65–70}
}
@TECHREPORT{Allison1988,
author = {L. Allison and C.N. Yee and M. McGaughey.},
title = {Three-Dimensional Queens Problems},
institution = {Dept. Computer Science, Monash University, Victoria, Australia},
year = {1989},
number = {89/130},
url = {http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Recn/Queens3D/},
abstract = {The two-dimensional $N$-queens problem is generalised to three dimensions and to
$N^2$-queens. There are non-toroidal and toroidal variants. A computer search has been
carried out for (non-toroidal) solutions up to $N=14$. We conjecture that toroidal
solutions exist iff the smallest factor of $N$ is greater than 7.}
}
@ARTICLE{Alvis20001,
author = {D. Alvis and M. Kinyon},
title = {Birkhoff{'}s Theorem for Panstochastic Matrices},
journal = {The American Mathematical Monthly},
year = {2001},
volume = {108(1)},
pages = {28-37},
doi = {10.2307/2695673}
}
@ARTICLE{Ambrus2006,
author = {G. Ambrus and J. Bar\'at},
title = {A Contribution to Queens Graphs: {A} Substitution Method},
journal = {Discrete Mathematics},
year = {2006},
volume = {306},
pages = {1105-1114},
doi = {10.1016/j.disc.2006.03.002},
abstract = {A graph $G$ is a queens graph if the vertices of $G$ can be mapped to queens
on the chessboard such that two vertices are adjacent if and only if the corresponding
queens attack each other, i.e. they are in horizontal, vertical or diagonal position.
We prove a conjecture of Beineke, Broere and Henning that the Cartesian product of an
odd cycle and a path is a queens graph. We show that the same does not hold for two odd
cycles. The representation of the Cartesian product of an odd cycle and an even cycle
remains an open problem.
We also prove constructively that any finite subgraph of the rectangular grid or the
hexagonal grid is a queens graph.
Using a small computer search we solve another conjecture of the authors mentioned above,
saying that $K_{3,4}$ minus an edge is a minimal non-queens graph.}
}
@BOOK{Andrews1960,
title = {Magic Squares and Cubes},
publisher = {Dover Publications Inc., NewYork},
year = {1960},
author = {W.S. Andrews},
edition = {2nd},
annote = {With chapters by other authors.}
}
@ARTICLE{Atkin1983,
author = {A.O.L. Atkin and L. Hay and R.G. Larson},
title = {Enumeration and Construction of Pandiagonal Latin Squares
of Primeorder},
journal = {Computers and Mathematics with Applications},
year = {1983},
volume = {9},
pages = {267-292},
doi = {10.1016/0898-1221(83)90130-X},
abstract = {A complete enumeration and algebraic description is given of all pandiagonal
Latin squares of order $\leq 13$. For $n = 5$, 7 and 11 there are (up to equivalence)
exactly the $n-3$ cyclic squares. For $n = 13$ there are 12,386 inequivalent squares;
of these 10 are cyclic (in all directions) and 1560 are semi-cyclic (cyclic in a single
direction). Systematic methods are given for constructing semi-cyclic pandiagonal
Latin squares of any prime order $> 11$.}
}
@BOOK{Ball1892,
title = {Mathematical Recreations and Essays},
publisher = {Macmillan and Co., London},
year = {1892},
author = {W.W.R. Ball},
annote = {Subsection ``The Eight Queens Problem''.
Many editions (e.g., 1905 (4th), 1922 (10th), 2004 (reprint of the 1937 version)),
later editions with editor H.S.M. Coxeter (13th, 1987, University of Toronto Press).},
url = {http://www.gutenberg.org/etext/26839}
}
@ARTICLE{Barr2006a,
author = {J. Barr and S. Rao},
title = {The $n$-Queens Problem in Higher Dimensions},
journal = {Elemente der Mathematik},
year = {2006},
volume = {61},
pages = {133-137},
url = {http://www.ems-ph.org/journals/show_pdf.php?issn=0013-6018&vol=61&iss=4&rank=1}
}
@ARTICLE{Barwell1980,
author = {B. Barwell},
title = {Solution to Problem 811},
journal = {Journal of Recreational Mathematics},
year = {1980},
volume = {13},
pages = {61}
}
@INCOLLECTION{Beasley1989,
author = {J.D. Beasley},
title = {The Mathematics of Games},
booktitle = {Recreations in Mathematics, volume 5},
publisher = {The Clarendon Press - Oxford University Press},
year = {1989}
}
@ARTICLE{Behmann1910,
author = {H. Behmann},
title = {Das gesamte {S}chachbrett unter {B}eachtung der {R}egeln des {A}chtk\"oniginnenproblems
zu Besetzen},
journal = {Mathematisch-Naturwissenschaftliche Bl\"atter. Organ des Arnst\"adter
Verbandes mathematischer und naturwissenschaftlicher Vereine an Deutschen
Hochschulen},
year = {1910},
volume = {8},
pages = {87-89}
}
@ARTICLE{Beineke1999,
author = {L.W. Beineke and I. Broere and M.A. Henning},
title = {Queens Graphs},
journal = {Discrete Mathematics},
year = {1999},
volume = {206},
pages = {63-75},
doi = {10.1016/S0012-365X(98)00392-6},
abstract = {The queens graph of a $(0,1)$-matrix $A$ is the graph whose vertices correspond
to the 1's in $A$ and in which two vertices are adjacent if and only if some diagonal or
line of $A$ contains the corresponding 1's. A basic question is the determination of
which graphs are queens graphs. We establish that a complete block graph is a queens graph
if and only if it does not contain $K_{1,5}$ as an induced subgraph. A similar result is shown
to hold for trees and cacti. Every grid graph is shown to be a queens graph, as are
the graphs $K_n\times{}P_m$ and $C_{2n}\times{}P_m$ for all integers $n,m\geq 2$. We show
that a complete multipartite graph is a queens graph if and only if it is a complete graph
or an induced subgraph of $K_{4,4}$, $K_{1,3,3}$, $K_{2,2,2}$ or $K_{1,1,2,2}$.
It is also shown that $K_{3,4}−e$ is not a queens graph.}
}
@ARTICLE{Bell2005,
author = {J. Bell},
title = {An Introduction to {SDR}{'}s and Latin Squares},
journal = {Morehead Electronic Journal of Applicable Mathematics},
year = {2005},
volume = {4},
number = {MATH-2005-03},
abstract = {In this paper we study systems of distinct representatives ({SDR}{'}s)
and Latin squares, considering {SDR}{'}s especially in their application
to constructing Latin squares. We give proofs of several important
elementary results for {SDR}{'}s and Latin squares, in particular
Hall{'}s marriage theorem and lower bounds for the number of Latin
squares of each order, and state several other results, such as necessary
and sufficient conditions for having a common {SDR} for two families.
We consider some of the applications of Latin squares both in pure
mathematics, for instance as the multiplication table for quasigroups,
and in applications, such as analyzing crops for differences in fertility
and susceptibility to insect attack. We also present a brief history
of the study of Latin squares and {SDR}'s.},
annote = {Chapter 4 is called ``Applications to $n$-queens''.},
url = {http://www.moreheadstate.edu/mejam/}
}
@ARTICLE{Bell2008,
author = {J. Bell and B Stevens},
title = {Results for the $n$-Queens Problem on the {M}\"obius Board},
journal = {Australasian Journal of Combinatorics},
pages = {21-34},
volume = {42},
year = {2008},
url = {https://ajc.maths.uq.edu.au/pdf/42/ajc_v42_p021.pdf},
abstract = {In this paper we consider the extension of the $n$-queens problem to the
M\"obius strip; that is, the problem of placing a maximum number of
nonattacking queens on the $m\times n$ chessboard for which the left and right
edges are twisted connected. We prove the existence of solutions for the
$m\times n$ M\"obius board for classes of $m$ and $n$ with density 25/48 in the set
of all $m\times n$ M\ ̈obius boards, and show the impossibility of solutions for
a set of $m$ and $n$ with density 1/16. We also have computed the total
number of solutions for the $m\times m$ M\"obius board for $m$ from 1 to 16.}
}
@ARTICLE{Bell2009,
author = {J. Bell and B. Stevens},
title = {A Survey of Known Results and Research Areas for $n$-Queens},
journal = {Discrete Mathematics},
year = {2009},
abstract = {In this paper we survey known results for the $n$-Queens problem
of placing $n$ nonattacking Queens on an $n\times{}n$ chessboard
and consider extensions of the problem, e.g. other board topologies
and dimensions. For all solution constructions, we either give the
construction, an outline of it, or a reference. In our analysis of
the modular board, we give a simple result for finding the intersections
of diagonals. We then investigate a number of open research areas
for the problem, stating several existing and new conjectures. Along
with the known results for $n$-Queens that we discuss, we also
give a history of the problem. In particular, we note that the first
proof that n nonattacking Queens can always be placed on an n×n
board for $n > 3$ is by E. Pauls, rather than by W. Ahrens who is
typically cited. We have attempted in this paper to discuss all the
mathematical literature in all languages on the $n$-Queens problem.
However, we look only briefly at computational approaches.},
doi = {10.1016/j.disc.2007.12.043},
pages={1-31},
volume={309},
keywords = {$n$-Queens problem; Modular $n$-Queens problem; Queens graph;
Chessboard graph; Chessboard problems}
}
@ARTICLE{Bell2007a,
author = {J. Bell and B. Stevens},
title = {Constructing Orthogonal Pandiagonal Latin Squares and Panmagic
Squares from Modular $n$-Queens Solutions},
journal = {Journal of Combinatorial Designs},
year = {2007},
volume = {15(3)},
pages = {221-234},
abstract = {In this article, we show how to construct pairs of orthogonal pandiagonal
Latin squares and panmagic squares from certain types of modular
$n$-Queens solutions. We prove that when these modular $n$-Queens
solutions are symmetric, the panmagic squares thus constructed will
be associative, where for an $n\times{}n$ associative magic square
$A = (a_{ij})$, for all $i$ and $j$ it holds that $a_{ij} + a_{n-i-1,n-j-1}
= c$ for a fixed $c$. We further show how to construct orthogonal
Latin squares whose modular difference diagonals are Latin from any
modular $n$-Queens solution. As well, we analyze constructing orthogonal
pandiagonal Latin squares from particular classes of non-linear modular
$n$-Queens solutions. These pandiagonal Latin squares are not row
cyclic, giving a partial solution to a problem of Hedayat. 2007},
doi = {10.1002/jcd.20143}
}
@ARTICLE{Bennett1967,
author = {B.T. Bennett and R.B. Potts},
title = {Arrays and Brooks},
journal = {Journal of the Australian Mathematical Society},
year = {1967},
volume = {7},
pages = {23-31},
doi = {10.1017/S144678870000505X},
annote = {Combinatorial problems concerning rooks, Queens, bishops and knights
on a chess board.}
}
@ARTICLE{Bennett1910,
author = {G.T. Bennett},
title = {The Eight Queens Problem (or Super Imposable Solutions
for $8\times{}8$ Boards)},
journal = {The Messenger of Mathematics},
year = {1910},
volume = {39},
pages = {19},
annote = {In 1910 G. Bennett concluded that there are only 12 distinctly different
solutions to the Queens problem, that is, solutions that could
not be obtained one from another by rotations for 90, 180 and 270,
and mirror-images.}
}
@INCOLLECTION{Berge1970,
author = {C. Berge},
title = {Graphes et Hypergraphes},
booktitle = {Monographies Universitaires de Math\'ematiques, 37},
publisher = {Dunod, Paris},
year = {1970}
}
@ARTICLE{Bernhardsson1991,
author = {B. Bernhardsson},
title = {Explicit Solutions to the $n$-Queens Problems for all $n$},
journal = {ACM SIGART Bulletin},
year = {1991},
volume = {2},
pages = {7},
doi = {10.1145/122319.122322},
abstract = {The $n$-queens problem is often used as a benchmark problem for AI research and
in combinatorial optimization. An example is the recent article \cite{Sosic1990} in this magazine
that presented a polynomial time algorithm for finding a solution. Several CPU-hours
were spent finding solutions for some $n$ up to 500,000.},
refersto = {\cite{Sosic1990}, \cite{Hoffman1969}}
}
@ARTICLE{Bernhold1942,
author = {H. Bernhold},
title = {Die {L}{\"o}sung des 8-{D}amen-{P}roblems},
journal = {Deutsche Schachzeitung},
year = {1942},
pages = {38-40},
volume = {97}
}
@ARTICLE{Bezzel1848,
author = {F.W.M. Bezzel},
title = {Proposal of Eight Queens Problem},
journal = {Berliner Schachzeitung},
year = {1848},
volume = {3},
pages = {363},
annote = {Reference 3: Zwei Schachfragen. In: Schachzeitung. In monatlichen
Heften ausgegeben von der Berliner Schachgesellschaft. Dritter Jahrgang,
Berlin\/ London, S. 363. Wieviel Steine mit der Wirksamkeit der Dame
k\"onnen auf das im \"ubrigen leere Brett ... Unbekannte Schachfreund.}
}
@ARTICLE{Bitner1975,
author = {J.R. Bitner and E.M. Reingold},
title = {Backtrack Programming Techniques},
journal = {Communications of the {ACM}},
year = {1975},
volume = {18},
pages = {651-656},
abstract = {The purpose of this paper is twofold. First, a brief exposition of
the general backtrack technique and its history is given. Second,
it is shown how the use of macros can considerably shorten the computation
time in many cases. In particular, this technique has allowed the
solution of two previously open combinatorial problems, the computation
of new terms in a well-known series, and the substantial reduction
in computation time for the solution to another combinatorial problem.
This article deals with the basics of backtracking.},
doi = {10.1145/361219.361224}
}
@ARTICLE{Blumenthal1928,
author = {L.M. Blumenthal},
title = {Discussions: {A}n Extension of the {G}auss Problem of Eight Queens},
journal = {The American Mathematical Monthly},
year = {1928},
volume = {35(6)},
pages = {307-309},
doi = {10.2307/2298678}
}
@ARTICLE{Bode2000,
author = {J.-P. Bode and H. Harborth},
title = {Independent Chess pieces on {E}uclidean Boards},
journal = {Journal of Combinatorial Mathematics and Combinatorial Computing},
year = {2000},
volume = {33},
pages = {209-223},
annote = {Papers in honour of Ernest J. Cockayne.}
}
@INPROCEEDINGS{Bozinovski2004,
author = {A. Bozinovski and S. Bozinovski},
title = {$n$-{Q}ueens Pattern Generation: {A}n Insight into Space Complexity
of a Backtracking Algorithm},
booktitle = {{ACM} International Conference Proceeding Series; Proceedings of
the 2004 International Symposium on Information and Communication
Technologies},
year = {2004},
pages = {281-286},
abstract = {It is proposed a method for tracking partial solutions while executing
a backtracking algorithm. That enables observation of space requirements
of a backtracking algorithm. To illustrate the method, the well known
benchmark $n$-Queens problem is considered. Results of the experiments
are shown and discussed.}
}
@BOOK{Bratko1986,
title = {Prolog Programming for {A}rtificial {I}ntelligence},
publisher = {Addison-Wesley},
year = {1986},
author = {I. Bratko},
annote = {First edition: 1986; second: 1990; third: 2001.
A Prolog program for the solution of our problem is presented.}
}
@ARTICLE{Bruen1975,
author = {A. Bruen and R. Dixon},
title = {The $n$-Queens Problem},
journal = {Discrete Mathematics},
year = {1975},
volume = {12},
pages = {393-395},
doi = {10.1016/0012-365X(75)90079-5},
abstract = {We present some new solutions to the problem of arranging n queens on
an $n \times{} n$ chessboard with no two taking each other. Recent
related work of other authors is also discussed.}
}
@ARTICLE{Burger1997,
author = {A.P. Burger and E.J. Cockayne and C.M. Mynhardt},
title = {Domination and Irredundance in the Queens{}'{} Graph},
journal = {Discrete Mathematics},
year = {1997},
volume = {163},
pages = {47-66},
doi = {10.1016/0012-365X(95)00327-S},
abstract = {The vertices of the queens' graph $Q_n$ are the squares of an $n \times{} n$
chessboard and two squares are adjacent if a queen placed on one covers the other.
It is shown that the domination number of $Q_n$ is at most
$31n/54 + O(1)$, that $Q_n$ possesses minimal dominating sets of cardinality
$5n/2 - O(1)$ and that the cardinality of any irredundant set of vertices of
$Q_n$ ($n \geq 9$) is at most $\lfloor 6n+6-8\sqrt{n+\sqrt{n}+1} \rfloor$.}
}
@ARTICLE{Burger2002,
author = {A.P. Burger and C.M. Mynhardt},
title = {An Upper Bound for the Minimum Number of Queens Covering
the $n\times{}n$ Chessboard},
journal = {Discrete Applied Mathematics},
year = {2002},
volume = {121},
pages = {51-60},
doi = {10.1016/S0166-218X(01)00244-X},
abstract = {We show that the minimum number of queens required to cover the
$n\times{}n$ chessboard is at most $\frac{8}{15}n+O(1)$.}
}
@ARTICLE{Burger2003,
author = {A.P. Burger and C.M. Mynhardt},
title = {An Improved Upper Bound for Queens Domination Numbers},
journal = {Discrete Mathematics},
year = {2003},
volume = {266},
pages = {119-131},
doi = {10.1016/S0012-365X(02)00802-6},
abstract = {We consider the domination number of the queens graph $Q_n$ and show that if,
for some fixed $k$, there is a dominating set of $Q_{4k+1}$ of a certain type with
cardinality $2k+1$, then for any $n$ large enough,
$\gamma(Q_n)\leq [(3k+5)/(6k+3)]+O(1)$. The same construction shows that for any
$m\geq 1$ and $n=2(6m-1)(2k+1)-1$,
$\gamma(Q_n^t)\leq [(2k+3)/(4k+2)]+O(1)$
where $Q_n^t$ is the toroidal $n\times{}n$ queens graph.}
}
@ARTICLE{Burger2000,
author = {A.P. Burger and C.M. Mynhardt},
title = {Properties of Dominating Sets of the Queens Graph ${Q}_{4k+3}$},
journal = {Utilitas Mathematica},
year = {2000},
volume = {57},
pages = {237-253}
}
@ARTICLE{Burger2000a,
author = {A.P. Burger and C.M. Mynhardt},
title = {Small Irredundance Numbers for Queens Graphs},
journal = {Journal of Combinatorial Mathematics and Combinatorial Computing},
year = {2000},
volume = {33},
pages = {33-43}
}
@ARTICLE{Burger1999,
author = {A.P. Burger and C.M. Mynhardt},
title = {Queens on Hexagonal Boards},
journal = {Journal of Combinatorial Mathematics and Combinatorial Computing},
year = {1999},
volume = {31},
pages = {97-111}
}
@ARTICLE{Burger2004,
author = {A.P. Burger and C.M. Mynhardt and E.J. Cockayne},
title = {Regular Solutions of the $n$-Queens Problem on the Torus},
journal = {Utilitas Mathematica},
year = {2004},
volume = {65},
pages = {219-230},
abstract = {The $n$-queens problem on the torus is the problem of placing $n$
queens on an $n\times{}n$ chessboard drawn on the torus so that no two queens
attack each other. This is known to be possible if and only if
$n \equiv \pm 1\ (\mathrm{mod\ } 6)$. A solution to this problem is said to be regular
if it places queens on all squares with co-ordinates $(x + a, kx + b)$
for some fixed integers $k \neq 0$, $a$ and $b$. We determine the number of
non-isometric regular solutions for each $n \equiv \pm 1\ (\mathrm{mod\ } 6)$.
}
}
@ARTICLE{Burger2001,
author = {A.P. Burger and C.M. Mynhardt and E.J. Cockayne},
title = {Queens Graphs for Chessboards on the Torus},
journal = {Australasian Journal of Combinatorics},
year = {2001},
volume = {24},
pages = {231-246},
url = {https://ajc.maths.uq.edu.au/pdf/24/ajc-v24-p231.pdf},
abstract = {We consider the independence, domination and independent domination
numbers of graphs obtained from the moves of queens on chessboards
drawn on the torus, and determine exact values for each of these parameters
in infinitely many cases.}
}
@ARTICLE{Burger1994,
author = {A.P. Burger and C.M. Mynhardt and E.J. Cockayne},
title = {Domination Numbers for the Queens' Graph},
journal = {Bulletin of the Institute of Combinatorics and its Applications},
year = {1994},
volume = {10},
pages = {73-82}
}
@ARTICLE{Burger2000b,
author = {A.P. Burger and C.M. Mynhardt},
title = {Symmetry and Domination in Queens' Graphs},
journal = {Bulletin of the Institute of Combinatorics and its Applications},
year = {2000},
volume = {29},
pages = {11-24}
}
@ARTICLE{Bussey1922,
author = {W.H. Bussey},
title = {A Note on the Problem of the Eight Queens},
journal = {The American Mathematical Monthly},
year = {1922},
volume = {29(7)},
pages = {252-253},
doi = {10.2307/2299223}
}
@INPROCEEDINGS{Cadoli2006,
author = {M. Cadoli and M. Schaerf},
title = {Partial Solutions with Unique Completion},
booktitle = {Reasoning, Action and Interaction in
AI Theories and Systems},
publisher = {Springer},
year = {2006},
volume = {4155},
pages = {101-115},
series = {Lecture Notes in Computer Science},
doi = {10.1007/11829263},
abstract = {In this paper we investigate the computational complexity of
combinatorial problems with givens, i.e., partial solutions, and where a
unique solution is required. Examples for this article are taken from the
games of Sudoku, $N$-queens and related games. We will show the computational
complexity of many decision and search problems related to Sudoku, a number
of similar games and their generalization. Furthermore, we propose a logical
description of several such problems that can lead to a formulation in the
language of Quantified Boolean Formulae (QBF) and, hence, their mechanization
via a QBF solver. Some experiments on finding the minimum number of givens
necessary/sufficient to guarantee uniqueness of solution are shown.}
}
@ARTICLE{Cairns2002,
author = {G. Cairns},
title = {Pillow Chess},
journal = {Mathematics Magazine},
year = {2002},
volume = {75},
pages = {173-186},
url = {http://www.jstor.org/stable/3219240}
}
@ARTICLE{Cairns2001,
author = {G. Cairns},
title = {Queens on Non-Square Tori},
journal = {The Electronic Journal of Combinatorics},
year = {2001},
volume = {8(1)},
number = {N6},
pages = {1-3},
url = {http://www.combinatorics.org/Volume_8/PDF/v8i1n6.pdf}
}
@ARTICLE{Campbell1977,
author = {P.J. Campbell},
title = {Gauss and the Eight Queens Problem, {A} Study in Miniature
of the Propagation of Historical Error},
journal = {Historia Mathematica},
year = {1977},
volume = {4},
pages = {397-404},
doi = {10.1016/0315-0860(77)90076-3},
abstract = {An 1874 article by J. W. L. Glaisher asserted that the eight
queens problem of recreational mathematics originated in 1850 with Franz
Nauck proposing it to Gauss, who then gave the complete solution. In fact
the problem was first proposed two years earlier by Max Bezzel, proposed
again by Nauck in a newspaper Gauss happened to read, and only partially
solved by Gauss in a casual attempt. Glaisher had access to an accurate
account of the history in German but perhaps could not read the language
well; the error subsequently spread through the recreational mathematics literature.}
}
@ARTICLE{Carter2005,
author = {T.A. Carter and W.D. Weakley},
title = {The $n$-Queens Problem with Diagonal Constraints},
journal = {Journal of Combinatorial Mathematics and Combinatorial Computing},
year = {2005},
volume = {53},
pages = {165-178}
}
@INPROCEEDINGS{Catalan1864,
author = {E.C. Catalan},
title = {Unknown},
booktitle = {Nouvelles Annales de Math\'ematiques 216me, t. XIII},
year = {1864},
pages = {187},
annote = {Jedenfalls infolge Druckfehlers --- statt dessen Berliner Schachzeitung
1840 anfiihrt, wird dieselbe Stelle gemeint haben (\cite{Ahrens1901}).}
}
@ARTICLE{Chaiken2015,
author ={S. Chaiken and C.R.H. Hanusa and T. Zaslavsky},
title = {A $q$-Queens Problem. {II}. {T}he square board},
journal = {Journal of Algebraic Combinatorics},
year = {2015},
volume={41},
pages={619-642},
abstract = {We apply to the $n\times n$ chessboard the counting theory from Part I for nonattacking placements of chess pieces with unbounded straight-line moves, such as the queen. Part I showed that the number of ways to place $q$ identical nonattacking pieces is given by a quasipolynomial function of $n$ of degree $2q$, whose coefficients are (essentially) polynomials in $q$ that depend cyclically on $n$. Here, we study the periods of the quasipolynomial and its coefficients, which are bounded by functions, not well understood, of the piece’s move directions, and we develop exact formulas for the very highest coefficients. The coefficients of the three highest powers of $n$ do not vary with $n$. On the other hand, we present simple pieces for which the fourth coefficient varies periodically. We develop detailed properties of counting quasipolynomials that will be applied in sequels to partial queens, whose moves are subsets of those of the queen, and the nightrider, whose moves are extended knight’s moves. We conclude with the first, though strange, formula for the classical $n$-Queens Problem and with several conjectures and open problems.},
doi = {10.1007/s10801-014-0547-0}
}
@ARTICLE{Chandra1974,
author = {A.K. Chandra},
title = {Independent Permutations, as Related to a Problem of {M}oser
and a Theorem of {P}\'olya},
journal = {Journal of Combinatorial Theory, Series A},
year = {1974},
volume = {16},
pages = {111-120},
doi = {10.1016/0097-3165(74)90076-4},
abstract = {We introduce the notion of a set of independent permutations on the domain
$\{0, 1,\ldots n-1\}$, and obtain bounds on the size of the largest such set. The results are
applied to a problem proposed by Moser in which he asked for the largest number of nodes in a
$d$-cube of side $n$ such that no $n$ of these nodes are collinear. Independent permutations
are also related to the problem of placing $n$ non-capturing superqueens (chess queens with
wrap-around capability) on an $n \times n$ board. As a special case of this treatment we obtain
P\'olya's theorem that this problem can be solved if and only if $n$ is not a multiple of 2 or 3.}
}
@ARTICLE{Chatham2006,
author = {R.D. Chatham and G.H. Fricke and R.D. Skaggs},
title = {The Queens Separation Problem},
journal = {Utilitas Mathematica},
year = {2006},
volume = {69},
pages = {129-141},
abstract = {We define a legal placement of Queens to be any placement in which
any two attacking Queens can be separated by a Pawn. The Queens separation number
is defined to be equal to the minimum number of Pawns which can separate some legal
placement of $m$ Queens on an order $n$ chess board. We prove that $n + 1$
Queens can be separated by 1 Pawn and conjecture that $n + k$ Queens can be
separated by $k$ Pawns for large enough $n$. We also provide some results on
the separation number of other chess pieces.},
url = {http://www.npluskqueens.info/uploads/2/1/3/5/21355572/queenssep.pdf}
}
@ARTICLE{Chatham2009first,
author = {R.D. Chatham and M. Doyle and G.H. Fricke and J. Reitmann and R.D.
Skaggs and M. Wolff},
title = {Independence and Domination Separation on Chessboard Graphs},
journal = {Journal of Combinatorial Mathematics and Combinatorial Computing},
year = {2009},
volume = {68},
pages= {3-17},
abstract = {A legal placement of Queens is any placement of Queens on an
order $N$ chessboard in which any two attacking Queens can be separated
by a Pawn. The Queens independence separation number is the minimum
number of Pawns which can be placed on an $n \times{} n$ board to
result in a separated board on which a maximum of $m$ independent
Queens can be placed. We prove that $N + k$ Queens can be separated
by $k$ Pawns for large enough $N$ and provide some results on the
number of fundamental solutions to this problem. We also introduce
separation relative to other domination-related parameters for Queens,
Rooks, and Bishops.},
url = {http://www.npluskqueens.info/uploads/2/1/3/5/21355572/queenssep2.pdf}
}
@ARTICLE{Chatham2009,
author = {R.D. Chatham and M. Doyle and J.J. Miller and A.M. Rogers and R.D.
Skaggs and J.A. Ward},
title = {Algorithm Performance for Chessboard Separation Problems},
journal = {Journal of Combinatorial Mathematics and Combinatorial Computing},
year = {2009},
volume = {70},
abstract = {Chessboard separation problems are modifications to classic
chessboard problems, such as the $N$ Queens Problem, in which obstacles
are placed on the chessboard. This paper focuses on a variation
known as the $N + k$ Queens Problem, in which $k$ Pawns and $N + k$
mutually non-attacking Queens are to be placed on an $N$-by-$N$
chessboard. Results are presented from performance studies examining the
efficiency of sequential and parallel programs that count the number
of solutions to the $N + k$ Queens Problem using traditional
backtracking and dancing links. The use of Stochastic Local Search for
determining existence of solutions is also presented. In addition,
preliminary results are given for a similar problem, the $N +k$ Amazons.},
url = {http://www.npluskqueens.info/uploads/2/1/3/5/21355572/dlxmccc.pdf}
}
@ARTICLE{Chatham2009b,
author = {R.D. Chatham},
title = {Reflections on the ${N} + k$ Queens Problem},
journal = {College Mathematics Journal},
year = {2009},
volume = {40},
pages = {204-210},
abstract = {Given a regular chessboard, can you place eight queens on it,
so that no two queens attack each other? More generally, given a square
chessboard with $N$ rows and $N$ columns, can you place $N$ queens on it, so
that no two queens attack each other?
This puzzle, known as the $N$ queens problem, is old, and famous, and has
an extensive history. Here we present a recently formulated elaboration,
which we call the $N + k$ queens problem. We describe some of what is known about
the $N + k$ queens problem, prove a few new results, and propose some open questions.},
url = {http://www.npluskqueens.info/uploads/2/1/3/5/21355572/cmj204-210.pdf}
}
@ARTICLE{Chatham2012,
author = {R.D. Chatham and M. Doyle and R.J. Jeffers and W.A. Kosters and R.D. Skaggs and J.A. Ward},
title = {Centrosymmetric Solutions to Chessboard Separation Problems},
journal = {Bulletin of the Institute of Combinatorics and its Applications},
year = {2012},
volume = {65},
abstract = {Given a regular chessboard, can you place eight queens on it,
so that no two queens attack each other? More generally, given a square
chessboard with $N$ rows and $N$ columns, can you place $N$ queens on it, so
that no two queens attack each other?
This puzzle, known as the $N$ queens problem, is old, and famous, and has
an extensive history. Here we present a recently formulated elaboration,
which we call the $N + k$ queens problem. We describe some of what is known about
the $N + k$ queens problem, prove a few new results, and propose some open questions.},
url = {http://www.npluskqueens.info/uploads/2/1/3/5/21355572/centrosymm2.pdf}
}
@MISC{Chatham,
author = {R.D. Chatham},
title = {The ${N}+k$ Queens Problem Page},
year = {2009},
url = {http://www.npluskqueens.info/uploads/2/1/3/5/21355572/n+kqueens.html},
annote = {Website.}
}
@INPROCEEDINGS{Chen2007,
author = {J.-C. Chen},
title = {An Efficient Non-Probabilistic Search Algorithm for the
$n$-Queens Problem},
booktitle = {Proceedings of the Third Conference on IASTED International Conference:
Advances in Computer Science and Technology},
year = {2007},
abstract = {We present a new heuristic search for the $n$-Queens problem, which
is neither backtracking nor random search. This algorithm finds systematically
a solution in linear time. Its speed is faster than the fastest algorithm
known so far. On an ordinary personal computer, it can find a solution
for 3000000 Queens in less than 5 seconds.},
url = {http://portal.acm.org/citation.cfm?id=1322534}
}
@ARTICLE{Chen1991,
author = {M. Chen},
title = {The Maximum Number of Mutually Uncapturable Strong Queens},
journal = {Journal of Qinghai Normal University (Natural Science)},
year = {1991},
volume = {1},
pages = {9-12}
}
@ARTICLE{Chen1992,
author = {M. Chen and R. Sun and J. Zhu},
title = {Partial $n$-Solutions to the Modular $n$-Queen Problem},
journal = {Chinese Science Bulletin},
year = {1992},
volume = {37(17)},
pages = {1422-1425}
}
@INPROCEEDINGS{Chen1992a,
author = {M. Chen and R. Sun and J. Zhu},
title = {Partial $n$-Solution to the Modular $n$-Queens Problem. II},
booktitle = {Combinatorics and Graph Theory, Proceedings of the Spring School and International Conference on Combinatorics (SSICC '92)},
year = {1992},
pages = {1-4},
publisher = {World Scientific}
}
@MISC{Chvatal2005,
author = {V. Chv\'atal},
title = {Colouring the Queen Graphs},
year = {2005},
url = {http://users.encs.concordia.ca/~chvatal/queengraphs.html},
annote = {Website.}
}
@ARTICLE{Clapp1986,
author = {R.M. Clapp and T.N. Mudge and R.A. Volz},
title = {Solutions to the $n$-Queens Problem Using Tasking in {A}da},
journal = {ACM SIGPLAN Notices},
year = {1986},
volume = {21},
pages = {99-110},
doi = {10.1145/15042.15046},
refersto = {\cite{Wirth1976}}
}
@ARTICLE{Clark1985,
author = {D.S. Clark},
title = {A Combinatorial Theorem on Circulant Matrices},
journal = {The American Mathematical Monthly},
year = {1985},
volume = {92(10)},
pages = {725-729},
doi = {10.2307/2323225}
}
@INPROCEEDINGS{Clark1989,
author = {D.S. Clark and O. Shisha},
title = {Invulnerable Queens on an Infinite Chessboard},
booktitle = {Proceedings of the Third International
Conference on Combinatorial Mathematics},
year = {1989},
pages = {133-139}
}
@ARTICLE{Clark1988,
author = {D.S. Clark and O. Shisha},
title = {Proof without Words: {I}nductive Construction of an infinite Chessboard
with Maximal Placement of Nonattacking Queens},
journal = {Mathematics Magazine},
year = {1988},
volume = {61},
pages = {98},
url = {http://www.jstor.org/stable/2690038},
annote = {A one page paper without words \ldots},
refersto = {\cite{Clark1989}, \cite{Kraitchik1942}}
}
@ARTICLE{Cockayne1990,
author = {E.J. Cockayne},
title = {Chessboard Domination Problems},
journal = {Discrete Mathematics},
year = {1990},
volume = {86},
pages = {13-20},
doi = {10.1016/0012-365X(90)90344-H},
abstract = {A graph may be formed from an $n \times{} n$ chessboard by taking the squares
as the vertices and two vertices are adjacent if a chess piece situated on one square
covers the other. In this paper we survey some recent results concerning domination
parameters for certain graphs constructed in this way.}
}
@ARTICLE{Cockayne1986,
author = {E.J. Cockayne and S.T. Hedetniemi},
title = {On the Diagonal Queens Domination Problem},
journal = {Journal of Combinatorial Theory, Series A},
year = {1986},
volume = {42},
pages = {137-139},
doi = {10.1016/0097-3165(86)90012-9},
abstract = {It is shown that the problem of covering an $n \times n$ chessboard with a
minimum number of queens on a major diagonal is related to the number-theoretic function
$r_3(n)$, the smallest number of integers in a subset of $\{1,\ldots,n\}$
which must contain three terms in arithmetic progression.}
}
@ARTICLE{Cockayne2001,
author = {E.J. Cockayne and C.M. Mynhardt},
title = {Properties of Queens Graphs and the Irredundance Number of ${Q}_7$},
journal = {Australasian Journal of Combinatorics},
year = {2001},
volume = {23},
pages = {285-299},
url = {https://ajc.maths.uq.edu.au/pdf/23/ocr-ajc-v23-p285.pdf},
abstract = {We prove results concerning neighbours of vertex subsets
and irredundance in the queens graph $Q_n$. We also establish that the
lower irredundance number of $Q_7$ is equal to four.}
}
@ARTICLE{Cockayne1987,
author = {E.J. Cockayne and P.H. Spencer},
title = {On the Independent Queens Covering Problem},
journal = {Graphs and Combinatorics},
year = {1987},
volume = {4},
pages = {101-110},
annote = {The minimum number of Queens which can be placed on an $n\times{}n$
chessboard so that all other squares are dominated by at least one
Queen but no Queen covers another, is shown to be less than $0.705n + 2.305$.},
doi = {10.1007/BF01864158}
}
@BOOK{Colbourn1999,
title = {Triple Systems},
series = {Oxford Mathematical Monographs},
publisher = {The Clarendon Press --- Oxford University Press},
year = {1999},
author = {C.J. Colbourn and A. Rosa}
}
@INPROCEEDINGS{Cournia2006,
author = {N. Cournia},
title = {Chessboard Domination on Programmable Graphics Hardware},
booktitle = {Proceedings of the 44th Annual Southeast Regional Conference},
year = {2006},
pages = {62-67},
doi = {10.1145/1185448.1185463},
abstract = {In this paper we present an algorithm to compute the minimum dominating
number of a chessboard graph given any chess piece. We use the CPU to compute possible
minimally dominating sets, which we then send to programmable graphics hardware to determine
the set's domination. We find that the GPU accelerated algorithm performs better than a
comparable CPU based algorithm for board sizes greater than 9. To our knowledge, this
paper presents the first algorithm to determine the minimum domination number of a
chessboard graph using the GPU.}
}
@INPROCEEDINGS{Crawford1992,
author = {K.D. Crawford},
title = {Solving the $n$-Queens Problem Using {G}enetic {A}lgorithms},
booktitle = {Proceedings of the 1992 ACM/SIGAPP Symposium on Applied Computing:
Technological Challenges of the 1990's},
year = {1992},
pages = {1039-1047},
doi = {10.1145/130069.130128}
}
@ARTICLE{Cull1994,
author = {P. Cull and R. Pandey},
title = {Isomorphism and the $n$-Queens Problem},
journal = {ACM SIGCSE Bulletin},
year = {1994},
volume = {26},
pages = {29-36},
abstract = {The $n$-Queens problem is commonly used to teach the programming
technique of backtrack search. The $n$-Queens problem may also
be used to illustrate the important concept of isomorphism. Here
we show how the $n$-Queens problem can be used as a vehicle to
teach the concepts of isomorphism, transformation groups or generators,
and equivalence classes. We indicate how these ideas can be used
in a programming exercise. We include a bibliography of 29 papers.},
doi = {10.1145/187387.187400}
}
@ARTICLE{Cvetkovi'c1969,
author = {D. Cvetkovi\'c},
title = {Some Remarks on the Problem of $n$-Queens},
journal = {Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz.},
year = {1969},
volume = {274-301(290)},
pages = {100-102}
}
@MISC{Dealy2004,
author = {S. Dealy},
title = {Common Search Strategies and Heuristics With Respect to the {N}-Queens Problem},
year = {2004},
abstract = {The $N$-Queens problem is examined and programmatically implemented for Depth First
Search, Depth First Search with improvements, Branch and Bound, and Beam Search.
Several heuristics are presented and implemented with each of the searches. Results were
analyzed for number of nodes generated, number of nodes traversed, and relative execution time.
While heuristics were found which gave Branch and Bound and Beam Search a significant
edge over DFS, there exist polynomial time algorithms using complete board assignment and
heuristic repair methods which are purported to do better.
},
note = {CS504 Term Project},
url ={http://www.cs.unm.edu/~sdealy/nqueens_proj.pdf}
}
@ARTICLE{Dean1998,
author = {D.S. Dean and G. Parisi},
title = {Statistical Mechanics of a Two-Dimensional System with Long-Range
Interactions},
journal = {Journal of Physics A: Mathematics and General},
year = {1998},
volume = {31},
pages = {3949-3960},
doi = {10.1088/0305-4470/31/17/006},
abstract = {We analyse the statistical physics of a two-dimensional lattice-based
system with long-range interactions. The particles interact in a way analogous
to the queens on a chess board. The long-range nature of the interaction gives
the mathematics of the problem a simple geometric structure which simplifies both
the analytic and numerical study of the system. We present some analytic calculations
for the statics of the problem and we also perform Monte Carlo simulations which
exhibit a dynamical transition between a high-temperature liquid regime and a
low-temperature glassy regime exhibiting ageing in the two time-correlation functions.}
}
@ARTICLE{Demiroers1992,
author = {O. Demir\"ors and N. Rafraf and M.M. Tanik},
title = {Obtaining $n$-Queens Solutions from Magic Squares and Constructing
Magic Squares from $n$-Queens Solutions},
journal = {Journal of Recreational Mathematics},
year = {1992},
volume = {24},
pages = {272-280}
}
@TECHREPORT{Demiroers1991,
author = {O. Demir\"ors and M.M. Tanik},
title = {Peaceful Queens and Magic Squares},
institution = {Department of Computer Science and Engineering, Southern Methodist University},
year = {1991},
number = {91-CSE-7}
}
@ARTICLE{Dietrich2005,
author = {H. Dietrich and H. Harborth},
title = {Independence on Triangular Triangle Boards},
journal = {Abhandlungen der Braunschweigischen Wissenschaftlichen Gesellschaft},
year = {2005},
volume = {54},
pages = {73-87},
abstract = {Triangular parts of the Euclidean triangle tessellation of the
plane are considered as gameboards $T_n$. The independence number $\beta_n$ is
the maximum number of non-attacking copies of a piece on $T_n$. For nine of
the chess-like pieces $\beta_n$ is determined completely.}
}
@ARTICLE{Doyle2008,
author = {M. Doyle and B. Rawe and A. Rogers},
title = {{JDLX}: {V}isualization of Dancing Links},
journal = {Journal of Computing Sciences in Colleges},
year = {2008},
volume = {24},
pages = {9-15},
url = {http://dl.acm.org/citation.cfm?id=1409768},
abstract = {Data structures courses have settled on a familiar canon of structures and
algorithms, and this is reflected in the standard textbooks. It is often useful for
instructors to enliven such courses by presenting data structures that are of more recent
interest, ones that may simultaneously challenge students' understanding of algorithms and
their skills in programming. Exact cover problems, exemplified by the newly popular Sudoku
game as well as the classic 8-queens problem, may be efficiently solved by the DLX algorithm
popularized by Knuth in 2000, and this can provide a good capstone experience in a data
structures course. The DLX algorithm operates by recursion on circular multiply linked lists.
Because the pointer mechanics of the DLX algorithm is quite complicated, visualization
techniques are called for. As the choreography of ``dancing links" in DLX is highly visual
anyway, this is very natural. In this paper we review best practices in algorithmic
visualization for learners, and then describe a Java-based visualization of DLX applied
to $N$-Queens. We also present some preliminary results that indicate that it is effective
in enhancing student learning.},
refersto = {\cite{Chatham2009first}, \cite{Knuth2000}}
}
@INPROCEEDINGS{Draa2005,
author = {A. Draa and H. Talbi and M. Batouche},
title = {A Quantum-inspired {G}enetic {A}lgorithm for Solving the ${N}$-Queens Problem},
booktitle = {Proceedings of the 7th International Symposium on Programming and Systems (ISPS’2005)},
year = {2005},
pages = {145-152}
}
@ARTICLE{Draa2010,
author = {A. Draa and S. Meshoul and H. Talbi and M. Batouche},
title = {A Quantum-Inspired Differential Evolution Algorithm for Solving the N-Queens Problem},
journal = {The International Arab Journal of Information Technology},
year = {2010},
volume = {7},
pages = {21--27},
url = {http://www.ccis2k.org/iajit/PDF/vol.7,no.1/4.pdf},
abstract = {In this paper, a quantum-inspired differential evolution algorithm for solving the N-queens problem is
presented. The N-queens problem aims at placing N queens on an NxN chessboard, in such a way that no queen could
capture any of the others. The proposed algorithm is a novel hybridization between differential evolution algorithms
and quantum computing principles. Accordingly, differential evolution algorithms have been enhanced by the adoption
of some quantum concepts such as quantum bits and states superposition. The use of the quantum interference has allowed
this hybrid approach to have a remarkable efficiency and good results.
},
refersto = {\cite{Draa2005}, \cite{Watkins2004}, \cite{Erbas1992}}
}
@BOOK{Dudeney1917,
title = {Amusements in Mathematics},
publisher = {Thomas Nelson \& Sons, Limited},
year = {1917},
author = {H.E. Dudeney},
annote = {Later editions from Dover Publications, Inc.
Chapter Chessboard Problems},
url = {http://www.gutenberg.org/etext/16713}
}
@MISC{Durango,
author = {{Durango Bill}},
title = {The ${N}$-Queens Problem},
annote = {Website.},
url = {http://www.durangobill.com/N_Queens.html}
}
@INPROCEEDINGS{Eiben1995,
author = {A.E. Eiben and P.-E. Rau\'e and Zs. Ruttkay},
title = {{GA}-easy and {GA}-hard Constraint Satisfaction Problems},
booktitle = {Proceedings of the ECAI-94 Workshop on Constraint Processing},
year = {1995},
volume = {923},
series = {Lecture Notes in Computer Science},
publisher = {Springer-Verlag},
doi = {10.1007/3-540-59479-5_30},
pages = {267-283},
abstract = {In this paper we discuss the possibilities of applying genetic
algorithms (GA) for solving constraint satisfaction problems (CSP). We point
out how the greediness of deterministic classical CSP solving techniques can
be counterbalanced by the random mechanisms of GAs. We tested our ideas by
running experiments on four different CSPs: $N$-queens, graph 3-colouring,
the traffic lights and the Zebra problem. Three of the problems have proven
to be GA-easy, and even for the GA-hard one the performance of the GA could
be boosted by techniques familiar in classical methods. Thus GAs are promising
tools for solving CSPs. In the discussion, we address the issues of non-solvable
CSPs and the generation of all the solutions.}
}
@INPROCEEDINGS{Eiben1994,
author = {A.E. Eiben and P.-E. Rau\'e and Zs. Ruttkay},
title = {Solving Constraint Satisfaction Problems Using {G}enetic {A}lgorithms},
booktitle = {Proceedings of the 1st IEEE World Conference on Computational Intelligence},
year = {1994},
pages = {542-547},
volume = {2},
publisher = {IEEE Service Center},
doi = {10.1109/ICEC.1994.350002},
abstract = {This article discusses the applicability of genetic algorithms (GAs)
to solve constraint satisfaction problems (CSPs). We discuss the requirements and
possibilities of defining so-called heuristic GAs (HGAs), which can be expected
to be effective and efficient methods to solve CSPs since they adopt heuristics
used in classical CSP solving search techniques. We present and analyse experimental
results gained by testing different heuristic GAs on the $N$-queens problem and
on the graph 3-colouring problem}
}
@ARTICLE{Eickenscheidt1980,
author = {B. Eickenscheidt},
title = {Das $n$-{D}amen-{P}roblem auf dem {Z}ylinderbrett},
journal = {feenschach},
year = {1980},
volume = {50},
pages = {382-385},
annote = {See also joint work with B. Schwarzkopf, feenschach 1970, p. 811}
}
@INPROCEEDINGS{El-Qawasmeh2004,
author = {E. El-Qawasmeh and K. Al-Noubani},
title = {A Polynomial Time Algorithm for the ${N}$-Queens Problems},
booktitle = {Proceedings of the IASTED International Conference on Neural Networks and Computational Intelligence (NCI 2004)},
year = {2004},
pages = {191-195}
}
@ARTICLE{El-Qawasmeh2005,
author = {E. El-Qawasmeh and K. Al-Noubani},
title = {Reducing the Time Complexity of the ${N}$-Queens Problem},
journal = {International Journal on Artificial Intelligence Tools},
year = {2005},
pages = {545-557},
volume = {14},
doi = {10.1142/S0218213005002247},
abstract = {This paper presents a fast algorithm for solving the $n$-queens problem.
The basic idea of this algorithm is to use pre-computed solutions in 75\% of the cases,
while the remaining cases are solved by calling the Sosic's algorithm. The novelty of
this algorithm is in the observation that these pre-computable cases exhibit a modular
nature. In addition, the pre-computed solutions run 100 times faster than Sosic's
algorithm in most cases.}
}
@ARTICLE{Engelhardt2007,
author = {M.R. Engelhardt},
title = {A Group-based Search for Solutions of the $n$-Queens Problem},
journal = {Discrete Mathematics},
year = {2007},
volume = {307},
pages = {2535-2551},
abstract = {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.},
doi = {10.1016/j.disc.2007.01.007},
refersto = {\cite{Rivin1994}, \cite{Rivin1992}, \cite{Schlude2003}}
}
@ARTICLE{Engelhardt2010,
author = {M. Engelhardt},
title = {Der {S}tammbaum der {L}{\"o}sungen des {D}amenproblems},
journal = {Spektrum der Wissenschaft},
year = {2010},
month = {August},
pages = {68-71},
url = {http://www.spektrum.de/artikel/1037434&_z=798888}
}
@MISC{Nqueensde,
author = {M. Engelhardt},
title = {The n Queens Problem},
url = {http://www.nqueens.de/},
annote = {Website.}
}
@TECHREPORT{Erbas1991,
author = {C. Erbas and N. Rafraf and M.M. Tanik},
title = {Magic Squares Constructing by the Uniform Step Method Provide Solutions
to the $n$-Queens Problem},
institution = {Department of Computer Science and Engineering, Southern Methodist University},
year = {1991},
number = {91-CSE-25}
}
@INPROCEEDINGS{Erbas1992,
author = {C. Erbas and S. Sarkeshik and M.M. Tanik},
title = {Different Perspectives of the $n$-Queens Problem},
booktitle = {CSC '92: Proceedings of the 1992 ACM Annual Conference on Communications},
year = {1992},
pages = {99-108},
abstract = {The $N$-Queens problem is a commonly used example in computer science.
There are numerous approaches proposed to solve the problem. We introduce
several definitions of the problem, and review some of the algorithms.
We classify the algorithms for the $N$-Queens problem into 3 categories.
The first category comprises the algorithms generating all the solutions
for a given $N$. The algorithms in the second category are desinged
to generate only the fundamental solutions~\cite{Topor1982}. The algorithms in the
last category generate only one or several solutions but not necessarily
all of them.},
doi = {10.1145/131214.131227}
}
@TECHREPORT{Erbas1991a,
author = {C. Erbas and S. Sarkeshik and M.M. Tanik},
title = {Algorithmic and Constructive Approaches to the $n$-Queens Problem},
institution = {Department of Computer Science and Engineering, Southern Methodist
University},
year = {1991},
number = {91-CSE-31}
}
@ARTICLE{Erbas1995a,
author = {C. Erbas and M.M. Tanik},
title = {Generating Solutions to the $n$-Queens Problem Using $2$-Circulants},
journal = {Mathematics Magazine},
year = {1995},
volume = {68},
pages = {343-356},
url = {http://www.jstor.org/stable/2690923}
}
@ARTICLE{Erbas1994,
author = {C. Erbas and M.M. Tanik},
title = {Parallel Memory Allocation and Data Alignment in {SIMD} Machines},
journal = {Parallel Algorithms and Applications},
year = {1994},
volume = {4},
pages = {139-151},
doi = {10.1080/10637199408915460},
abstract = {In this paper, we introduce a memory storage scheme allowing
conflict-free parallel access to rows, columns, square blocks, distributed
blocks, and positive and negative diagonals of two dimensional arrays. Unlike
the existing schemes, the proposed scheme can be used for an arbitrary number
of memory modules and an arbitrary size of matrices. We develop a systematic
procedure for the memory allocation based on a placement matrix constructed
using circulant matrices. We, also, analyze the data alignment requirements
of the proposed scheme, and demonstrate that the data vectors read from memory
modules can be aligned for the processors using a set of shift, flip, and
shuffle operations, which can be implemented by a data manipulation network. },
annote = {Preliminary version appeared under the title: Storage schemes for
parallel memory systems and the $n$-Queens problem.}
}
@INPROCEEDINGS{Erbas1992a,
author = {C. Erbas and M.M. Tanik},
title = {Storage Schemes for Parallel Memory Systems and the $n$-Queens
Problem},
booktitle = {Proceedings of the 15th Anniversary of the ASME ETCE Confererence,
Computer Applications Symposium},
year = {1992},
volume = {43},
pages = {115-120}
}
@TECHREPORT{Erbas1991b,
author = {C. Erbas and M.M. Tanik},
title = {$n$-Queens Problem and its Algorithms},
institution = {Department of Computer Science and Engineering, Southern Methodist
University},
year = {1991},
number = {91-CSE-8}
}
@TECHREPORT{Erbas1991c,
author = {C. Erbas and M.M. Tanik},
title = {$n$-Queens Problem and its Connection to the Polygons},
institution = {Department of Computer Science and Engineering, Southern Methodist University},
year = {1991},
number = {91-CSE-21}
}
@ARTICLE{Erbas1992b,
author = {C. Erbas and M.M. Tanik and Z. Aliyazicioglu},
title = {Linear Congruence Equations for the Solutions of the $n$-Queens
Problem},
journal = {Information Processing Letters},
year = {1992},
volume = {41},
pages = {301-306},
abstract = {We demonstrate a method using linear congruence equations to generate
solutions to the $N$-Queens problem. There are only a few papers
in the literature generating solutions for every $N$. Our method generates
solutions for every $N$, and the number of solutions produced by our
method is larger than the number of solutions given in these papers.},
doi = {10.1016/0020-0190(92)90156-P}
}
@TECHREPORT{Erbas1992c,
author = {C. Erbas and M.M. Tanik and Z. Aliyazicioglu},
title = {A Note on {F}alkowski\' s $n$-Queens Solutions},
institution = {Department of Computer Science and Engineering, Southern Methodist University},
year = {1992},
number = {92-CSE-14}
}
@INPROCEEDINGS{Erbas1993,
author = {C. Erbas and M.M. Tanik and V.S.S. Nair},
title = {A Circulant Matrix Based Approach to Storage Schemes
for Parallel Memory Systems},
booktitle = {Proceedings of the Fifth IEEE Symposium on Parallel and Distributed
Processing},
year = {1993},
pages = {92-99},
organization = {IEEE},
abstract = {We introduce a memory storage scheme allowing conflict-free parallel
access to rows, columns, square blocks, distributed blocks, and positive and
negative diagonals of two dimensional arrays. Unlike the existing schemes, the
proposed scheme can be used for an arbitrary number of memory modules and an
arbitrary size of the arrays. We develop a systematic procedure for the memory
allocation based on a placement matrix constructed using circulant matrices},
doi = {10.1109/SPDP.1993.395546}
}
@ARTICLE{Erdem2003,
title = {Tight Logic Programs},
journal = {Theory and Practice of Logic Programming},
volume = {3},
pages = {499-518},
year = {2003},
author = {E. Erdem and V. Lifschitz},
doi = {10.1017/S1471068403001765},
abstract = {This note is about the relationship between two theories of negation
as failure --- one based on program completion, the other based on stable models,
or answer sets. François Fages showed that if a logic program satisfies a certain
syntactic condition, which is now called ‘tightness,’ then its stable models can
be characterized as the models of its completion. We extend the definition of
tightness and Fages' theorem to programs with nested expressions in the bodies of
rules, and study tight logic programs containing the definition of the transitive
closure of a predicate.}
}
@ARTICLE{Falkowski1986,
author = {B.-J. Falkowski and L. Schmitz},
title = {A Note on the Queen's Problem},
journal = {Information Processing Letters},
year = {1986},
volume = {23},
pages = {39-46},
doi = {10.1016/0020-0190(86)90128-6},
refersto = {\cite{Ginsburg1939}, \cite{Golomb1965}, \cite{Netto1901}}
}
@ARTICLE{Fillmore1974,
author = {J.P. Fillmore and S.G. Williamson},
title = {On Backtracking: {A} Combinatorial Description of the Algorithm},
journal = {SIAM Journal on Computing},
year = {1974},
volume = {3},
pages = {41-55},
doi = {10.1137/0203004},
abstract = {A basic algorithm for solving many discrete problems is the so-called
``backtracking" algorithm. The basic problem is that of generating the elements of a subset
$S_0 $ of a finite set in an efficient manner. If a group $G$ acts on $S_0 $, then
one might wish to obtain only nonisomorphic elements of $S_0 $. In this paper the
basic backtracking algorithm is described in terms of chains of partitions on the
set $S$. The corresponding isomorph rejection problem is described in terms of
$G$-invariant chains of partitions on $S$. Examples and flow charts are given.}
}
@INBOOK{Finch2003,
chapter = {Mathematical Constants},
title = {Encyclopedia of Mathematics and its Applications},
publisher = {Cambridge University Press},
year = {2003},
author = {S.R. Finch},
volume = {94}
}
@TECHREPORT{Foley1987,
author = {J. Foley},
title = {Manchester Dataflow Machine: {P}reliminary Benchmark Test
Evaluation},
institution = {University of Manchester, Computer Science Department},
year = {1987},
number = {UMCS-87-11-2},
abstract = {The Manchester Dataflow Hardware is supported by a Software compiler
for the SISAL language and a number of programs have been written
to act as Benchmark tests for the hardware. The Benchmark set used
contains a wide range of programs including numerical algorithms,
sorting, graph colouring and $n$ Queens algorithms plus others. All
programs are compiled using a range of optimisations, including function
inlining and vectorisation. The resulting statistics, obtained both
by simulation and hardware are presented.},
url = {http://intranet.cs.man.ac.uk/Intranet_subweb/library/cstechrep/Abstracts/UMCS-87-11-2.html}
}
@ARTICLE{Foulds1984,
author = {L.R. Foulds and D.G. Johnston},
title = {An Application of Graph Theory and Integer Programming:
Chessboard Nonattacking Puzzles},
journal = {Mathematics Magazine},
year = {1984},
volume = {57(3)},
pages = {95-104},
url = {http://www.jstor.org/stable/2689591}
}
@ARTICLE{Franel1894,
author = {J. Franel},
title = {$n$-Queens solution},
journal = {L{'}Interm\'ediaire des Math\'ematiciens},
year = {1894},
volume = {11},
pages = {140-141},
annote = {Article no. 123.}
}
@MASTERSTHESIS{Gomez1997,
author = {R. G{\'o}mez},
title = {On the $d$-Dimensional Modular $n$-Queen Problem},
school = {University of Maryland at College Park},
year = {1997}
}
@MISC{Gomez2004,
author = {R. G\'omez(-Aiza) and J.J. Montellano(-Ballesteros) and R. Strausz},
title = {On the Modular $n$-Queen Problem in Higher Dimensions},
year = {2004},
abstract = {The modular $n$-queen problem in higher dimensions was introduced
by Nudelman \cite{Nudelman1995}. He showed that for a complete solution
to exist in the $d$-dimensional modular $n$-chessboard, it is necessary that
$\gcd(n, (2d-1)!) = 1$, and that it is sufficient that
$\gcd(n, (2d-1)!) = 1$. He conjectured that the last condition is
also necessary and showed that this is indeed the case for the class of linear
solutions. In this notes, we observe that the conjecture is true for the larger
class of polynomial solutions, which are solutions we present as a natural
generalization of the bidimensional solutions developed by Kl{\o}ve \cite{Klove1977}.
We also generalize constructions of bidimensional solutions developed
also by Kl{\o}ve \cite{Klove1981}.},
refersto = {\cite{Gomez1997}, \cite{Klove1977}, \cite{Klove1981}, \cite{Monsky1989},
\cite{Nudelman1995}},
url = {http://www.liacs.nl/home/kosters/nqueens/papers/gomez2004.pdf}
}
@INPROCEEDINGS{Gao1990,
author = {Q.S. Gao and S.J. Hou},
title = {Junior {R}esearcher: {A} Discovery System that can solve the
Queens Problems on a Constant Computational Complexity},
booktitle = {Information Technology, 1990. Next Decade in Information Technology,
Proceedings of the 5th Jerusalem Conference on (Cat. No.90TH0326-9)},
year = {1990},
pages = {345-347},
abstract = {An approach that uses the discovery system Junior Researcher to solve
the $n$-Queens problems ($n \geq 4$) is proposed. The functions,
structure and features of Junior Researcher are described. A constant-complexity
algorithm for solving the problem is then given.},
doi = {10.1109/JCIT.1990.128303}
}
@ARTICLE{Gardner1999,
author = {M. Gardner},
title = {Chess Queens and Maximum Unattacked Cells},
journal = {Math Horizons},
year = {1999},
volume = {7},
month = {November},
pages = {12-16},
abstract = {There is now an enormous literature on the old classic task of
placing eight queens on a chessboard so that no queen attacks another.
There are twelve solutions, not counting trivial rotations and reflections.
The task naturally generalizes to enumerating the number of solutions for
$n$ non-attacking queens on an $n\times{}n$ board.}
}
@BOOK{Gardner1968,
title = {The Unexpected Hanging and Other Mathematical Diversions},
publisher = {Simon \& Schuster},
year = {1968},
author = {M. Gardner},
annote = {Several editions, as Further Mathematical Diversions.
Chapter 16: The Eight Queens and Other Chessboard Diversions.}
}
@BOOK{Gardner1983,
title = {Wheels, Life, and Other Mathematical Amusements},
publisher = {Freeman},
year = {1983},
author = {M. Gardner},
annote = {Problem 8.19 is about superqueens, unique solution on the $n=10$ board;
in Chapter 17 we read about multicolor nonattacking queens, and more.}
}
@BOOK{Gardner1991,
title = {Fractal Music, Hypercards and More Mathematical Recreations from Scientific
American Magazin},
publisher = {Freeman},
year = {1991},
author = {M. Gardner},
annote = {Chapter 15: Mathematical Chess Puzzles;
$n$-queens problem (reflected, modular)}
}
@ARTICLE{Gardner1980,
author = {M. Gardner},
title = {Patterns in Primes are a Clue to the Strong Law of Small
Numbers},
journal = {Scientific American},
year = {1980},
volume = {243},
pages = {18-28}
}
@ARTICLE{Gardner1972,
author = {Martin Gardner},
title = {Mathematical Games},
journal = {Scientific American},
year = {1972},
volume = {227},
pages = {176-182}
}
@BOOK{Garey1983,
title = {Computers and Intractability: {A} Guide to the Theory of {NP}-Completeness},
publisher = {W. H. Freeman and Co., San Fransisco, CA},
year = {1979},
author = {M.R. Garey and D.S. Johnson}
}
@ARTICLE{Garner1981,
author = {C.W.L. Garner and A.M. Herzberg},
title = {On {M}c{C}arty's Queen Squares},
journal = {The American Mathematical Monthly},
year = {1981},
volume = {88(8)},
pages = {612-613},
doi = {10.2307/2320511}
}
@BOOK{Gauss1850,
title = {Werke {B}and XII},
publisher = {George Olms Verlag, Hildesheim},
year = {1850},
author = {C.F. Gauss},
annote = {1973, Reprint of the 1929 original. Correspondence with H.C. Schumacher.},
url={http://gdz.sub.uni-goettingen.de/}
}
@ARTICLE{Gent2017,
author = {I.P. Gent and C. Jefferson and P. Nightingale},
title = {Complexity of $n$-Queens Completion},
journal = {Journal of Artificial Intelligence Research},
year = {2017},
pages = {815-848},
volume = {59},
doi = {10.1613/jair.5512},
abstract = {The $n$-Queens problem is to place $n$ chess queens on an $n$ by $n$ chessboard so that no two queens are on the same row, column or diagonal. The $n$-Queens Completion problem is a variant, dating to 1850, in which some queens are already placed and the solver is asked to place the rest, if possible. We show that $n$-Queens Completion is both NP-Complete and \#P-Complete. A corollary is that any non-attacking arrangement of queens can be included as a part of a solution to a larger $n$-Queens problem. We introduce generators of random instances for $n$-Queens Completion and the closely related Blocked $n$-Queens and Excluded Diagonals Problem. We describe three solvers for these problems, and empirically analyse the hardness of randomly generated instances. For Blocked $n$-Queens and the Excluded Diagonals Problem, we show the existence of a phase transition associated with hard instances as has been seen in other NP-Complete problems, but a natural generator for $n$-Queens Completion did not generate consistently hard instances. The significance of this work is that the $n$-Queens problem has been very widely used as a benchmark in Artificial Intelligence, but conclusions on it are often disputable because of the simple complexity of the decision problem. Our results give alternative benchmarks which are hard theoretically and empirically, but for which solving techniques designed for $n$-Queens need minimal or no change.}
}
@ARTICLE{Gibbons1996,
author = {P.B. Gibbons and J.A. Webb},
title = {Some New Results for the Queens Domination Problem},
journal = {Australasian Journal of Combinatorics},
year = {1997},
volume = {15},
pages = {145-160},
url = {https://ajc.maths.uq.edu.au/pdf/15/ocr-ajc-v15-p145.pdf},
abstract = {Computing techniques are described which have
resulted in the establishment of new results for the queens domination
problem. In particular it is shown that the minimum cardinalities
of independent sets of dominating queens for chessboards of size
14, 15, and 16 are 8, 9, and 9 respectively, and that the minimum
cardinalities of sets of dominating queens for chessboards of size 29,
41, 45, and 57 are 15, 21,23 and 29 respectively. As a by-product
the numbers of non-isomorphic ways of covering a chessboard of size
$n$ with $k$ independent queens for $1 \leq n \leq 15$ and
$1 \leq k \leq 8$, as well as the case $n = 16$, $k = 8$, are computed.}
}
@BOOK{Gik1983,
title = {Shakhmaty i Matematika (BibliotechkaKvant)},
publisher = {Nauka, Moscow},
year = {1983},
author = {E.Y. Gik},
volume = {24}
}
@BOOK{Gik1976,
title = {Matematika na shakhmatnoi doske (Nauchno-populiarnaiaseriia)},
publisher = {Nauka, Moscow},
year = {1976},
author = {E.Y. Gik}
}
@ARTICLE{Ginsburg1939,
author = {Ginsburg, J.},
title = {Gauss's Arithmetization of the Problem of $n$-Queens},
journal = {Scripta Mathematica},
year = {1939},
volume = {5},
pages = {63-66}
}
@ARTICLE{Glaisher1874,
author = {J.W.L. Glaisher},
title = {On the Problem of the Eight Queens},
journal = {Edinburgh Philosophical Magazine},
year = {1874},
volume = {4(48)},
pages = {457-467},
annote = {In 1874 J. W. Glaisher proposed expanding the Eight Queens Problem
to the $n$-Queens problem, that is, solving the Queens' puzzle
for the general $n\times{}n$ chessboard. For example, the well-known
$n$-Queens problem can be tackled by noting that the eight geometric
symmetries of the problem translate into an invariance group of the
set of clauses; this reduces the search space, as was noted already
by Glaisher.}
}
@ARTICLE{Goldsby1987,
author = {M.E. Goldsby},
title = {Solving the ``${N} <= 8$-Queens" Problem with {CSP} and {M}odula-2},
journal = {SIGPLAN Notices},
year = {1987},
volume = {22},
pages = {43-52},
doi = {10.1145/24686.24689}
}
@INPROCEEDINGS{Golomb1970,
author = {S.W. Golomb},
title = {Sphere Packing, Coding Metrics and Chess Puzzles},
booktitle = {Chapel Hill Conference on Combinatorial Mathematics and its Applications},
year = {1970},
pages = {176-189}
}
@ARTICLE{Golomb1965,
author = {S.W. Golomb and L.D. Baumert},
title = {Backtrack Programming},
journal = {Journal of the ACM},
year = {1965},
volume = {12},
pages = {516-524},
doi = {10.1145/321296.321300},
abstract = {A widely used method of efficient search is examined in detail.
This examiniation provides the opprtunity to formulate its scope and methods
in their full generality. In addition to a general exposition of
the basic process, some important refinements are indicated.
Examples are given which illustrate the salient features of this searching process.},
refersto = {\cite{Ginsburg1939}, \cite{Netto1901}}
}
@ARTICLE{Golomb1984,
author = {S.W. Golomb and H. Taylor},
title = {Constructions and Properties of {C}ostas Arrays},
journal = {Proceedings of the IEEE},
volume= {72},
year = {1984},
pages = {1143-1163},
abstract = {A Costas array is an $n\times{}n$ array of dots and blanks with
exactly one dot in each row and column, and with distinct vector differences
between all pairs of dots. As a frequency-hop pattern for radar or sonar, a Costas
array has an optimum ambiguity function, since any translation of the array parallel
to the coordinate axes produces at most one out-of-phase coincidence. We conjecture
that $n\times{}n$ Costas arrays exist for every positive integer $n$. Using various
constructions due to L. Welch, A. Lempel, and the authors, Costas arrays are shown
to exist when $n = p - 1$, $n = q - 2$, $n = q - 3$, and sometimes when $n = q - 4$
and $n = q - 5$, where $p$ is a prime number, and $q$ is any power of a prime number.
All known Costas array constructions are listed for 271 values of $n$ up to 360.
The first eight gaps in this table occur at $n = 32$, 33, 43, 48, 49, 53, 54, 63.
(The examples for $n = 19$ and $n = 31$ were obtained by augmenting Welch's
construction.) Let $C(n)$ denote the total number of $n\times{}n$ Costas arrays.
Costas calculated $C(n)$ for $n \leq 12$. Recently, John Robbins found
$C(13) = 12828$. We exhibit all the arrays for $n \leq 8$. From Welch's construction,
$C(n) \geq 2n$ for infinitely many $n$. Some Costas arrays can be sheared into
``honeycomb arrays.'' All known honeycomb arrays are exhibited, corresponding
to $n = 1$, 3, 7, 9, 15, 21, 27, 45. Ten unsolved problems are listed.},
doi = {10.1109/PROC.1984.12994}
}
@BOOK{Golombeck1977,
title = {Golombeck's Encyclopedia of Chess},
publisher = {Crown Publishers, New York},
year = {1977},
author = {H. Golombeck}
}
@ARTICLE{Gosset1914,
author = {T. Gosset},
title = {The Eight Queens Problem},
journal = {Messenger of Mathematics},
year = {1914},
volume = {44},
pages = {48},
annote = {T. Gosset later proved Bennett to be right, in 1914.}
}
@ARTICLE{Gray1993,
author = {J.S. Gray},
title = {Is Eight Enough? {T}he Eight Queens Problem Re-examined},
journal = {ACM SIGCSE Bulletin},
year = {1993},
volume = {25},
pages = {39-44,51},
abstract = {A detailed analysis of a classic backtracking problem, The Eight
Queen Problem is presented. The paper addresses additional facets
of the Eight Queen Problem that might be overlooked when casually
generating a program solution. The author suggests that the extra
time taken to fully analyze the problem will result in a better understanding
of the problem which in turn will manifest itself in a better program
solution.},
doi = {10.1145/165408.165423},
refersto = {\cite{Sosic1990}, \cite{Wirth1976}}
}
@ARTICLE{Grigoryan2018,
author = {E. Grigoryan},
title = {Investigation of the Regularities in the Formation of Solutions $n$-Queens Problem},
journal = {Modeling of Artificial Intelligence},
year = {2018},
volume = {5},
pages = {3-21},
doi = {10.13187/mai.2018.1.3},
abstract = {
The $n$-Queens problem is considered. A description of the regularities in a sequential list of
all solutions, both complete and short, is given.
}
}
@ARTICLE{Grinstead1990,
author = {C.M. Grinstead and B. Hahne and D. {Van Stone}},
title = {On the Queen Domination Problem},
journal = {Discrete Mathematics},
year = {1990},
volume = {86},
pages = {21-26},
doi = {10.1016/0012-365X(90)90345-I},
abstract = {
A configuration of queens on an $m \times{} m$ chessboard is said to dominate the board
if every square either contains a queen or is attacked by a queen. The configuration
is said to be non-attacking if no queen attacks another queen. Let $f(m)$ and $g(m)$
equal the minimum number of queens and the minimum number of non-attacking queens,
respectively, needed to dominate an $m \times{} m$ chessboard. We prove that:
1. $f(m)\leq\frac{14}{23}m+O(1)$, and
2. $g(m)\leq\frac{2}{3}m+O(1)$.
These are the best upper bounds known at the present time for these functions.
},
refersto = {\cite{Cockayne1990}}
}
@TECHREPORT{Gruenberger1965,
author = {F.J. Gruenberger},
title = {Optimizing the Eight Queens Overlay Problem},
institution = {RAND Corporation, Santa Monica, CA, US},
year = {1965},
url = {http://www.rand.org/pubs/papers/P3102},
abstract = {A study of the old problem of how to place eight queens on a chess
board so that no queen attacks any of the others. This paper studies the overlay
problem: How can the 12 basic solutions to the above be shown on one chess board
with a minimum of crowding? The scheme suggested reduces the multi-stage decision
process to a series of single-stage decisions, each with a simple criterion of success.
},
refersto = {\cite{Ball1892}}
}
@ARTICLE{Gu1991,
author = {J. Gu},
title = {On a General Framework for Large-scale Constraint-Based Optimization},
journal = {ACM SIGART Bulletin},
year = {1991},
volume = {2},
pages = {8},
doi = {10.1145/122319.122323},
abstract = {The explicit solution for the $n$-queens problem, mentioned in a letter
from Bo Bernhardsson \cite{Bernhardsson1991}, is basically Pauls's solution analyzed by Ahrens
(See reference \cite{Ahrens1901} of our previous article in SIGART October issue 1990).
The result was in public domain long before 1918 (not 1969). We also mentioned
its weakness, namely: The class of solutions provided by analytical methods is
very restricted, as Ahrens pointed out in \cite{Ahrens1901}. They can only provide one solution
for the $n$-queens problem and can not provide any solution (much better
explicit solutions for the $n$-queens problem exist). This is not the case
for search methods which can find, in principle, any solution. This distinction
is crucial for practical applications of the $n$-queens problem.},
refersto = {\cite{Ahrens1901}, \cite{Bernhardsson1991}, \cite{Sosic1990}}
}
@ARTICLE{Gunther1874,
author = {S. G{\"u}nther},
title = {Zur Mathematisches {T}heorie des {S}chachbretts},
journal = {Archiv der Mathematik und Physik},
year = {1874},
volume = {56},
pages = {281-292},
url = {http://archive.org/stream/archivdermathem21unkngoog}
}
@INPROCEEDINGS{Gut2009,
author = {M.A. Guti{\'e}rrez-Naranjo and M.A. Mart{\'{\i}}nez-del-Amor and I. P{\'e}rez-Hurtado and M.J. P{\'e}rez-Jim{\'e}nez},
title = {Solving the {N}-Queens Puzzle with {P} Systems},
booktitle = {Seventh Brainstorming Week on Membrane Computing},
year = {2009},
pages = {199-210},
volume = {I},
url = {http://www.gcn.us.es/7BWMC/volume/21_queens.pdf},
abstract = {The $N$-queens puzzle consists on placing $N$ queens on
an $N\times{}N$ grid in such way that no two queens are on the same row,
column or diagonal line. In this paper we
present a family of {P} systems with active membranes (one {P} system
for each value of $N$)
that provides all the possible solutions to the puzzle.}
}
@INPROCEEDINGS{Gut2011,
author = {M.A. Guti{\'e}rrez-Naranjo and M.J. P{\'e}rez-Jim{\'e}nez},
title = {Depth-First Search with {P} Systems},
booktitle = {Membrane Computing},
series = {Lecture Notes in Computer Science},
publisher = {Springer-Verlag, Berlin},
pages = {257-264},
volume = {6501},
doi = {10.1007/978-3-642-18123-8_20},
year = {2011},
abstract = {The usual way to find a solution for an {NP} complete problem in Membrane
Computing is by brute force algorithms. These solutions work from a theoretical point
of view but they are implementable only for small instances of the problem. In this
paper we provide a family of P systems which brings techniques from Artificial Intelligence
into Membrane Computing and apply them to solve the $N$-queens problem.
},
refersto = {\cite{Gut2009}}
}
@BOOK{Guy1981,
title = {Unsolved Problems in Number Theory},
publisher = {Springer-Verlag},
year = {1981},
author = {R.K. Guy},
annote = {Third edition: 2004. Chapter C18: The $n$-Queens Problem}
}
@ARTICLE{Han1998,
author = {J. Han and L. Liu and T. Lu},
title = {Evaluation of Declarative $n$-Queens Recursion: {D}eductive
Database Approach},
journal = {Information Sciences},
year = {1998},
volume = {105},
pages = {69-100},
doi = {10.1016/S0020-0255(97)10019-6},
abstract = {Can we evaluate a logic program declaratively? That is, can a logic program be
evaluated correctly and efficiently, independent of query modes and rule/predicate ordering,
finding a complete set of answers, and terminating properly? the answer could be ``yes'',
at least for a good subclass of logic programs, based on our investigation and experimentation
using a deductive database approach. In this paper, an $n$-queens problem, a classical
logic program, is used as a running example to demonstrate the methodology. Our analysis
shows that binding analysis and constraint exploration are two essential issues in the
realization of declarative logic programming. The limitations of our methodology are
also discussed in the paper.},
refersto = {\cite{Stone1987}}
}
@ARTICLE{Hansche1973,
author = {B. Hansche and W. Vucenic},
title = {On the $n$-Queens Problem},
journal = {Notices of the American Mathematical Society},
year = {1973},
volume = {20},
pages = {568}
}
@INPROCEEDINGS{Harborth2003,
author = {H. Harborth and V. Kultan and K. Nyaradyova and Z. Spendelova},
title = {Independence on Triangular Hexagon Boards},
booktitle = {Proceedings of the Thirty-Fourth Southeastern International Conference
on Combinatorics, Graph Theory and Computing},
year = {2003},
pages = {215-222}
}
@ARTICLE{Hayes1992,
author = {P. Hayes},
title = {A Problem of Chess Queens},
journal = {Journal of Recreational Mathematics},
year = {1992},
volume = {24},
pages = {264-271}
}
@ARTICLE{Hedayat1977,
author = {A. Hedayat},
title = {A Complete Solution to the Existence and Nonexistence of
{K}nut {V}ik Designs and Orthogonal {K}nut {V}ik Designs.},
journal = {Journal of Combinatorial Theory, Series A},
year = {1977},
volume = {22},
pages = {331-337},
doi = {10.1016/0097-3165(77)90007-3},
abstract = {Hedayat and Federer (Ann. of Statist. 3 (1975), 445–-447) proved that Knut Vik
designs do not exist for all even orders. They gave a simple algorithm for the construction
of such designs for all other orders, except when the order of the design is divisible by 3.
The existence of Knut Vik designs of orders divisible by 3 was left unsolved by these authors.
It is shown here that Knut Vik designs do not also exist for all orders divisible by 3. An easy
algorithm based on a result of Euler is provided for the construction of orthogonal Knut Vik
designs for all orders not divisible by 2 or 3. Therefore, we can say that Knut Vik designs
and orthogonal Knut Vik designs of order $n$ exist if and only if $n$ is not divisible by 2 or 3.
The results are based on the concepts of a super diagonal and parallel super diagonals in an
$n \times{} n$ array, which have been introduced and studied for the first time here.
Other relevant results are also given.}
}
@ARTICLE{Heden2002,
author = {O. Heden},
title = {Maximal Partial Spreads and the Modular $n$-Queen Problem
{III}},
journal = {Discrete Mathematics},
year = {2002},
volume = {243},
pages = {135-150},
doi = {10.1016/S0012-365X(00)00464-7},
abstract = {Maximal partial spreads in $PG(3,q)$, $q=p^k$, $p$ odd prime and $q\geq 7$,
are constructed for any integer $n$ in the interval $(q^2+1)/2+6\leq n\leq (5q^2+4q-1)/8$
in the case $q+1\equiv 0,\pm 2,\pm 4,\pm 6,\pm 10, 12\ (\mathrm{mod\ } 24)$.
In all these cases, maximal
partial spreads of the size $(q^2+1)/2+n$ have also been constructed for some small values
of the integer $n$. These values depend on $q$ and are mainly $n=3$ and $n=4$. Combining
these results with previous results of the author and with that of others we can conclude
that there exist maximal partial spreads in $PG(3,q)$, $q=p^k$ where $p$ is an odd prime and
$q\geq 7$, of size $n$ for any integer $n$ in the interval
$(q^2+1)/2+6\leq n \leq q^2-q+2$.}
}
@ARTICLE{Heden1995,
author = {O. Heden},
title = {Maximal Partial Spreads and the Modular $n$-Queen Problem.
{II}},
journal = {Discrete Mathematics},
year = {1995},
volume = {142},
pages = {97-106},
doi = {10.1016/0012-365X(94)00008-7},
abstract = {We prove that if $q + 1 \equiv 8 \mathrm{\ or\ } 16\ (\mathrm{mod\ } 24)$
then, for any integer $n$ in the interval $(q^2 + 1)/2 + 3 \leq n \leq (5q^2 + 4q + 7)/8$,
there is a maximal partial spread of size $n$ in $PG(3, q)$.}
}
@ARTICLE{Heden1993,
author = {O. Heden},
title = {Maximal Partial Spreads and the Modular $n$-Queen Problem},
journal = {Discrete Mathematics},
year = {1993},
volume = {120},
pages = {75-91},
abstract = {We prove that for any integer n in the interval
$(5q^2+4q-1)/8\leq n\leq q^2+q-2$ there is a
maximal partial spread of size $n$ in $PG (3, q)$ where $q$ is odd
and $q \geq 7$. We also prove that there are maximal partial spreads
of size $(q^2+3)/2$ when $\gcd(q+1,24)=2$ or $4$ and of size $(q^2+5)/2$
when $\gcd(q+1,24)=4$.},
doi = {10.1016/0012-365X(93)90566-C}
}
@ARTICLE{Heden1992,
author = {O. Heden},
title = {On the Modular $n$-Queen Problem},
journal = {Discrete Mathematics},
year = {1992},
volume = {102},
pages = {155-161},
doi = {10.1016/0012-365X(92)90050-P},
abstract = {Let $M(n)$ denote the maximum number of queens on a modular chessboard
such that no two attack each other. We prove that if 4 or 6 divides $n$ then $M(n) \leq n-2$
and if $\gcd(n, 24) = 8$ then $M(n)\geq n - 2$. We also show that $M(24) = 22$.}
}
@BOOK{Hedetniemi1998,
title = {Domination in Graphs: {A}dvanced Topics},
publisher = {Marcel Dekker, New York},
year = {1998},
author = {S.M. Hedetniemi and S.T. Hedetniemi and R. Reynolds},
annote = {Chapter 6: Combinatorial Problems on Chessboards: {II}}
}
@BOOK{Hentenryck2005,
title = {Constrained-Based Local Search},
publisher = {The MIT Press},
year = {2005},
author = {P. {Van Hentenryck} and L. Michel},
annote = {Chapter 5.1: The Queens Problem}
}
@ARTICLE{Hern'andez2005,
author = {J. Hern\'andez and L. Robert},
title = {Figures of Constant Width on a Chessboard},
journal = {The American Mathematical Monthly},
year = {2005},
volume = {112(1)},
pages = {42-50},
url = {http://www.jstor.org/stable/2690038}
}
@ARTICLE{Herzberg1981,
author = {A.M. Herzberg and C.W.L. Garner},
title = {Latin Queen Squares},
journal = {Utilitas Mathematica},
year = {1981},
volume = {20},
pages = {143-154}
}
@ARTICLE{Hitotomatu1979,
author = {H. Hitotomatu and K. Noshita},
title = {A Technique for Implementing Backtrack Algorithms and its Application},
journal = {Information Processing Letters},
year = {1979},
volume = {8},
pages = {174-175},
doi = {10.1016/0020-0190(79)90016-4}
}
@ARTICLE{Hoffman1969,
author = {E.J. Hoffman and J.C. Loessi and R.C. Moore},
title = {Constructions for the Solution of the $m$-Queens Problem},
journal = {Mathematics Magazine},
year = {1969},
volume = {42},
pages = {66-72},
annote = {$m$ instead of $n$ \ldots},
url = {http://www.jstor.org/stable/2689192}
}
@ARTICLE{Hollander1973,
author = {D.H. Hollander},
title = {An Unexpected Two-Dimensional Space-Group Containing Seven
of the Twelve Basic Solutions to the Eight Queens Problem},
journal = {Journal of Recreational Mathematics},
year = {1973},
volume = {6(4)},
pages = {287-291}
}
@INPROCEEDINGS{Homaifar1992,
author = {A. Homaifar and J. Turner and S. Ali},
title = {The $n$-Queens Problem and {G}enetic {A}lgorithms},
booktitle = {Proceedings IEEE Southeast Conference, Volume 1},
year = {1992},
pages = {262-267},
abstract = {The authors determined how well the operators of genetic algorithms
handled very difficult combinatorial and constraint satisfaction
problems. The $n$-Queens problem is a complex combinatorial problem.
Genetic algorithms are efficient and robust search algorithms that
can solve the $n$-Queens problem. To derive a problem, the genetic
algorithm treats the problem as an ordering or sequencing problem
and blindly traverses the search space to satisfy the large number
of constraints posed by the inherent complexity of the problem. Results
are presented for $N < 200$.},
doi = {10.1109/SECON.1992.202348}
}
@ARTICLE{Hsiang2004,
author = {J. Hsiang and D.F. Hsu and Y.-P. Shieh},
title = {On the Hardness of Counting Problems of Complete Mappings},
journal = {Discrete Mathematics},
year = {2004},
volume = {277},
pages = {87-100},
doi = {10.1016/S0012-365X(03)00176-6},
abstract = {A complete mapping of an algebraic structure $(G,+)$ is a bijection $f(x)$
of $G$ over $G$ such that $f(x)=x+h(x)$ for some bijection $h(x)$. A question often raised is,
given an algebraic structure $G$, how many complete mappings of $G$ there are. In this paper
we investigate a somewhat different problem. That is, how difficult it is to count the number
of complete mappings of $G$. We show that for a closed structure, the counting problem is
\#P-complete. For a closed structure with a left-identity and left-cancellation law, the
counting problem is also \#P-complete. For an abelian group, on the other hand, the
counting problem is beyond the \#P-class. Furthermore, the famous counting problems
of $n$-queen and toroidal $n$-queen problems are both beyond the \#P-class.}
}
@INPROCEEDINGS{Hsiang2002,
author = {J. Hsiang and Y. Shieh and Y. Chen},
title = {The Cyclic Complete Mappings Counting Problems},
booktitle = {PaPS: Problems and Problem Sets for ATP Workshop in conjunction with CADE-18 and FLoC 2002},
year = {2002},
url = {http://www.arping.idv.tw/cm/index.htm}
}
@INPROCEEDINGS{Hu2003,
author = {X. Hu and R.C. Eberhart and Y. Shi},
title = {Swarm Intelligence for Permutation Optimization: {A} Case Study
of $n$-Queens Problem},
booktitle = {Proceedings IEEE Swarm Intelligence Symposium (SIS'03)},
year = {2003},
pages = {243-246},
doi = {10.1109/SIS.2003.1202275},
abstract = {This paper introduces a modified particle swarm optimizer which deals
with permutation problems. Particles are defined as permutations of a group of unique values.
Velocity updates are redefined based on the similarity of two particles. Particles change
their permutations with a random rate defined by their velocities. A mutation factor
is introduced to prevent the current pBest from becoming stuck at local minima. Preliminary
study on the $n$-queens problem shows that the modified PSO is promising in solving
constraint satisfaction problems.}
}
@ARTICLE{Huff1973,
author = {G.B. Huff},
title = {On Pairings of the First $2n$ Natural Numbers},
journal = {Acta Arithmetica},
year = {1973},
volume = {23},
pages = {117-126},
url = {http://matwbn.icm.edu.pl/ksiazki/aa/aa23/aa2322.pdf}
}
@ARTICLE{Hukushima2002,
author = {K. Hukushima},
title = {Extended Ensemble {M}onte {C}arlo Approach to Hardly Relaxing
Problems},
journal = {Computer Physics Communications},
year = {2002},
volume = {147},
pages = {77-82},
doi = {doi:10.1016/S0010-4655(02)00207-2},
abstract = {A set of methods based on an idea of extended ensemble has been
proposed for simulating hardly relaxing systems such as spin glasses. The
multicanonical method, simulated tempering and exchange Monte Carlo are typical
examples of this family. We briefly review extended ensemble Monte Carlo methods,
particularly focusing on the exchange Monte Carlo method. Using the method, we
study the number of solutions of the $N$ queens problem which is a kind of
constraint-satisfaction problem. This problem is a typical example of hardly
relaxing problems because there exist numerous solutions and energy barriers
between them. Our numerical result supports the conjecture that the number of
solutions is proportional to $N^N$ in the large $N$ limit. We also discuss the
thermodynamic properties of the $N$ queens problem at finite temperatures
introduced artificially.}
}
@ARTICLE{Hwang1983,
author = {F.K. Hwang and K.W. Lih},
title = {Latin Squares and Superqueens},
journal = {Journal of Combinatorial Theory, Series A},
year = {1983},
volume = {34},
pages = {110-114},
doi = {10.1016/0097-3165(83)90048-1},
abstract = {Let $L$ be a Latin square of order $n$ with entries from
$\{0, 1,\ldots, n-1\}$. In addition, $L$ is said to have the $(n, k)$ property if,
in each right or left wrap around diagonal, the number of cells with entries smaller than
$k$ is exactly $k$. It is established that a necessary and sufficient condition for the
existence of Latin squares having the $(n, k)$ property is that of
$(2|n \Rightarrow 2| k)$ and $(3|n \Rightarrow 3| k)$. Also, these Latin squares are
related to a problem of placing nonattacking queens on a toroidal chessboard.}
}
@ARTICLE{Iyer1966,
author = {M.R. Iyer and V.V. Menon},
title = {On Coloring the $n\times{}n$ Chessboard},
journal = {The American Mathematical Monthly},
year = {1966},
volume = {73(7)},
pages = {721-725},
doi = {10.2307/2313979}
}
@ARTICLE{Jha2018,
author = {R. Jha and D. Das and A. Dash and S. Jayaraman and B.K. Behera and P.K. Panigrahi},
title = {A Novel Quantum $N$-Queens Solver Algorithm and its Simulation and Application to Satellite Communication Using {IBM} Quantum Experience
},
journal = {arXiv},
year = {2018},
volume = {arXiv:1806.10221},
abstract = {Quantum computers can potentially solve problems that are computationally intractable on a classical computer in polynomial time using quantum-mechanical effects such as superposition and entanglement. The $N$-Queens Problem is a notable example that falls under the class of NP-complete problems. It involves the arrangement of $N$ chess queens on an $N\times N$ chessboard such that no queen attacks any other queen, i.e. no two queens are placed along the same row, column or diagonal. The best time complexity that a classical computer has achieved so far in generating all solutions of the $N$-Queens Problem is of the order $O(N!)$. In this paper, we propose a new algorithm to generate all solutions to the $N$-Queens Problem for a given $N$ in polynomial time of order $O(N^3)$ and polynomial memory of order $O(N^2)$ on a quantum computer. We simulate the 4-queens problem and demonstrate its application to satellite communication using IBM Quantum Experience platform.
},
url = {https://arxiv.org/abs/1806.10221}}
}
@INPROCEEDINGS{Jing1999,
author = {J. Han and J. Liu and Q. Cai},
title = {From {A}life Agents to a Kingdom of $n$-Queens},
booktitle = {Intelligent Agent Technology: {S}ystems,
Methodologies, and Tools},
year = {1999},
pages = {110-120},
abstract = {This paper presents a new approach to solving $n$-Queen problems,
which involves a model of distributed autonomous agents with artificial
life (ALife) and a method of representing $n$-Queen constraints
in an agent environment. The distributed agents locally interact
with their living environment, i.e., a chessboard, and execute their
reactive behaviors by applying their behavioral rules for randomized
motion, least-conflict position searching, and cooperating with other
agents etc. The agent-based $n$-Queen problem solving system evolves
through selection and contest according to the rule of Survival of
the Fittest, in which some agents will die or be eaten if their moving
strategies are less efficient than others. The experimental results
have shown that this system is capable of solving large-scale $n$-Queen
problems. This paper also provides a model of ALife agents for solving
general {CSP}s.},
url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.6158}
}
@ARTICLE{Kuchmann1997,
author = {F.C. K\"uchmann},
title = {Solving the Eight Queens Problem},
journal = {MacTech Magazine: {F}or {M}acintosh Programmers \& Developers},
year = {1997},
volume = {13},
pages = {20-27}
}
@ARTICLE{Kale1990,
author = {L.V. Kal\'e},
title = {An Almost Perfect Heuristic for the ${N}$ Nonattacking Queens
Problem},
journal = {Information Processing Letters},
year = {1990},
volume = {34},
pages = {173-178},
doi = {10.1016/0020-0190(90)90156-R},
abstract = {We present a heuristic technique for finding solutions to the $N$ nonattacking
queens problem that is almost perfect in the sense that it finds a first solution without
any backtracks in most cases. In addition to previously known variable-ordering heuristics
and their extensions, it uses a value-ordering heuristic, which contributes dramatically to
its success. Using these heuristics, solutions have been found for all values of
$N$ between 4 and 1000.}
}
@ARTICLE{Katzman2005,
author = {M. Katzman},
title = {Counting Monomials},
journal = {Journal of Algebraic Combinatorics},
year = {2005},
volume = {22},
pages = {331-341},
doi = {10.1007/s10801-005-4531-6},
abstract = {This paper presents two enumeration techniques based on Hilbert functions.
The paper illustrates these techniques by solving two chessboard problems.}
}
@ARTICLE{Kazarin1975,
author = {L.S. Kazarin and G.N. Kopylov and E.A. Timofeev},
title = {The Chromatic Number of a Special Class of Graphs},
journal = {Vestnik Jaroslav Univ. Vyp.},
year = {1975},
volume = {9},
pages = {37-46}
}
@ARTICLE{Kearse2002,
author = {M.D. Kearse and P.B. Gibbons},
title = {A New Lower Bound on Upper Irredundance in the Queens'
Graph},
journal = {Discrete Mathematics},
year = {2002},
volume = {256},
pages = {225-242},
doi = {10.1016/S0012-365X(01)00467-8},
abstract = {The queens’ graph $Q_n$ has the squares of the $n\times{}n$ chessboard as its
vertices, with two squares adjacent if they are in the same row, column, or diagonal.
An irredundant set of queens has the property that each queen in the set attacks at
least one square which is attacked by no other queen. $IR(Q_n)$ is the cardinality of the largest
irredundant set of vertices in $Q_n$. Currently the best lower bound for
$IR(Q_n)$ is $IR(Q_n)\geq 2.5n-O(1)$, while the best upper bound is
$IR(Q_n)\leq \lfloor 6n + 6 -8\sqrt{n +\sqrt{n} + 1}\rfloor$
for $n\geq 6$. Here the lower bound is improved to
$IR(Q_n)\geq 6n-O(n^{2/3})$. In particular, it is shown for even
$k\geq 6$ that $IR(Q_{k^3})\geq 6k^3-29k^2-O(k)$.}
}
@ARTICLE{Keating1993,
author = {J.G. Keating},
title = {{H}opfield Networks, Neural Data Structures and the Nine
Flies Problem: {N}eural Network Programming Projects for
Undergraduates},
journal = {ACM SIGCSE Bulletin},
year = {1993},
volume = {25},
pages = {33-37,40,60},
doi = {10.1145/164205.164224},
abstract = {This paper describes two neural network programming projects suitable for
undergraduate students who have already completed introductory courses in Programming
and Data Structures. It briefly outlines the structure and operation of Hopfield Networks
from a data structure stand-point and demonstrates how these type of neural networks may be
used to solve interesting problems like Perelman's Nine Flies Problem. Although the Hopfield
model is well defined mathematically, students do not have to be very familiar with the
mathematics of the model in order to use it to solve problems. Students are actively encouraged
to design modifications to their implementations in order to obtain faster or more accurate
solutions. Additionally, students are also expected to compare the neural network's performance
with traditional approaches, in order that they may appreciate the subtleties of both approaches.
Sample results are provided from projects which have been completed during the last three-year
period.},
refersto = {\cite{Mandziuk1992}}
}
@ARTICLE{Khan2003,
author = {S.U. Khan},
title = {Modular $n$-Queen},
journal = {Geombinatorics},
year = {2003},
volume = {12(4)},
pages = {217-221}
}
@ARTICLE{Kim1979,
author = {S. Kim},
title = {Problem 811},
journal = {Journal of Recreational Mathematics},
year = {1979},
volume = {12(1)},
pages = {fply53}
}
@ARTICLE{Kise2004,
author = {K. Kise and T. Katagiri and H. Honda and T. Yuba},
title = {Solving the $n$-Queens Problem with a {PG} Cluster},
journal = {IEICE Transactions on Information and Systems, Pt.1 (Japanese Edition)},
year = {2004},
abstract = {The $n$-Queens problem is to place N Queens of which no Queen
can attack each other on an $n\times{}n$ chess board. This paper
presents a sequential program which attains from 11\% to 18\% of
improvement in the speed as compared with a present program. And
by parallelizing using {MPI} and calculating using PC clusters, the
number of solutions for the 24-Queens problem is calculated for
the first time in the world. Main knowledge of this experience is
as follows. 1) From 11\% to 18\% speed-up in a sequential program
is attained by the optimization of memory reference and control structure,
2) A master-worker scheme is efffective in the parallelization, 3)
The hyper-threading technology of Pentium4 processor attains 30\%
speed-up, 4) In the solution of a real problem, it is necessary to
consider the efficiently as the whole system.}
}
@TECHREPORT{Kise2004a,
author = {K. Kise and T. Katagiri and H. Honda and T. Yuba},
title = {Solving the 24-Queens Problem Using {MPI} on a {PC} Cluster},
institution = {Graduate School of Information Systems, The University of Electro-Communication},
year = {2004},
number = {UEC-IS-2004-6}
}
@ARTICLE{Klarner1979,
author = {D.A. Klarner},
title = {Queen Squares},
journal = {Journal of Recreational Mathematics},
year = {1979},
volume = {12(3)},
pages = {177-178}
}
@ARTICLE{Klarner1967,
author = {D.A. Klarner},
title = {The Problem of Reflecting Queens},
journal = {American Mathematical Monthly},
year = {1967},
volume = {74(8)},
pages = {953-955},
doi = {10.2307/2315273}
}
@ARTICLE{Klove1981,
author = {T. Kl{\o}ve},
title = {The Modular $n$-Queen Problem {II}},
journal = {Discrete Mathematics},
year = {1981},
volume = {36},
pages = {33-48},
doi = {10.1016/0012-365X(81)90171-0},
abstract = {We study classes of solutions to the modular $n$-queen problem. The main part of
the paper is concerned with symmetric solutions (solutions invariant under 90\degree{} rotation).
In the last section we study maximal partial solutions for those values of $n$
for which no solutions exist.}
}
@ARTICLE{Klove1977,
author = {T. Kl{\o}ve},
title = {The Modular $n$-Queen Problem},
journal = {Discrete Mathematics},
year = {1977},
volume = {19},
pages = {289-291},
doi = {10.1016/0012-365X(77)90110-8},
abstract = {We show that the modular $n$-queen problem has a solution if and only if
$\gcd(n, 6) = 1$. We give a class of solutions for all these $n$.}
}
@INPROCEEDINGS{Knuth2000,
author = {D.E. Knuth},
title = {Dancing Links},
booktitle = {Millennial Perspectives in Computer Science},
year = {2000},
pages = {187-214},
publisher = {Palgrave},
url = {http://www-cs-faculty.stanford.edu/~knuth/papers/dancing-color.ps.gz}
}
@BOOK{Koshy2001,
title = {Elementary Number Theory with {A}pplications},
publisher = {Harcourt Academic Press, San Diego},
year = {2001},
author = {T. Koshy}
}
@MISC{Kotesovec1996,
author = {V. Kot\v{e}\v{s}ovec},
title = {Mezi \v{s}achovnic{\'{\i}} a po\v{c}{\'{\i}}ta\v{c}em},
year = {1996},
annote = {Self-published book (in Czech).},
url = {http://web.iol.cz/vaclav.kotesovec/}
}
@ARTICLE{Kovalenko1996,
author = {I.N. Kovalenko},
title = {Upper Bound on the Number of Complete Maps},
journal = {Cybernetics and System Analysis},
year = {1996},
volume = {32},
pages = {65-68},
doi = {10.1007/BF02366583},
annote = {Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 81-–85,
January–February, 1996.}
}
@BOOK{Kraitchik1942,
title = {Mathematical Recreations},
publisher = {W.W. Norton, New York},
year = {1942},
author = {M. Kraitchik},
annote = {Later editions from Dover Publications, Inc.
Chapter 10.3: The Problem of the Queens;
Chapter 10.4: Domination of the Chessboard}
}
@BOOK{Kreuzer2005,
title = {Computational Commutative Algebra. 2},
publisher = {Springer-Verlag, Berlin},
year = {2005},
author = {M. Kreuzer and L. Robbiano}
}
@INPROCEEDINGS{Kunde1997,
author = {M. Kunde and K. G\"urtzig},
title = {Efficient Sorting and Routing on Reconfigurable Meshes Using
Restricted Bus Length},
booktitle = {Proceedings of the 11th International Parallel Processing Symposium
(IPPS1997)},
year = {1997},
pages = {713-720},
organization = {IEEE Computer Society},
doi = {10.1109/IPPS.1997.580985},
abstract = {Sorting and balanced routing problems for synchronous mesh-like
processor networks with reconfigurable buses are considered. Induced by the
argument that broadcasting along buses of arbitrary length within unit time
seems rather non-realistic, we consider basic problems on reconfigurable meshes
that can be solved efficiently even with restricted bus length.It is shown that
on $r$-dimensional reconfigurable meshes of side length n with bus length
bounded to a constant $l$ the $h-h$ sorting and routing problem can be solved
within $hn+o(hrn)$ steps in any case and in $hn/2+o(hrn)$ steps with high
probability, provided that $hl \geq 4r$. This result is due to a data
concentration method that is explained in the paper and it will hold even for
certain very light loadings, i.e. with significantly less than one elements per
processor on average. Extensions to two-dimensional reconfigurable meshes
with diagonal links are considered.}
}
@ARTICLE{Landau1896,
author = {E. Landau},
title = {{\"U}ber das {A}chtdamenproblem und seine {V}erallgemeinerung},
journal = {Naturwiss. Wochenschrift},
year = {1896},
volume = {11},
pages = {367-371}
}
@ARTICLE{Laparewicz1912,
author = {A. Laparewicz},
title = {Kr\'olowe na Szachnownicy, Wektor},
journal = {Mathematische-Physikalische Zeitschrift},
year = {1912},
volume = {1(6)},
pages = {326-336}
}
@ARTICLE{Larson1977,
author = {L.C. Larson},
title = {A Theorem About Primes Proved on a Chessboard},
journal = {Mathematics Magazine},
year = {1977},
volume = {50},
pages = {69-74},
url = {http://www.jstor.org/stable/2689726}
}
@INPROCEEDINGS{Laskar2003,
author = {R. Laskar and A. McRae and C. Wallis},
title = {Domination in Triangulated Chessboard Graphs},
booktitle = {Proceedings of the Thirty-Fourth Southeastern International Conference
on Combinatorics, Graph Theory and Computing},
year = {2003},
pages = {107-123}
}
@ARTICLE{Laskar1999,
author = {R. Laskar and C. Wallis},
title = {Chessboard Graphs, Related Designs, and Domination Parameters},
journal = {Journal of Statistical Planning and Inference},
year = {1999},
volume = {76},
pages = {285-294},
doi = {10.1016/S0378-3758(98)00132-3},
abstract = {The graph-theoretic study of combinatorial chessboard problems
can be extended to the study of line graphs of graphs of combinatorial designs.
In particular, the determination of optimal placements of rooks on a chessboard
corresponds to the determination of domination parameters of graphs of block
designs. The determination of one such parameter, the independence number,
is shown to follow directly from classical results in design theory. Additionally,
the domination number of graphs of finite projective planes is discussed.}
}
@ARTICLE{Le1990,
author = {M.H. Le and W. Li and E.T. Wang},
title = {A Generalization of the $n$-Queen Problem},
journal = {Journal of Systems Science and Mathematical Sciences},
year = {1990},
volume = {3(2)},
pages = {183-192}
}
@ARTICLE{Le1989,
author = {M.H. Le and W. Li and E.T. Wang},
title = {A Generalization of the $n$-Queen Problem},
journal = {Journal of Systems Science and Mathematical Sciences},
year = {1989},
volume = {9(2)},
pages = {158-168}
}
@INPROCEEDINGS{Le2005,
author = {T.-N. Le and C.-K. Pham},
title = {A New ${N}$-Parallel Updating Method of the {H}opfield-Type
Neural Network for $n$-Queens Problem},
booktitle = {Proceedings IEEE International Joint Conference on
Neural Networks (IJCNN'05)},
year = {2005},
pages = {788-791},
abstract = {In the previous $N$-parallel updating methods of the Hopfield-type
neural network for $n$-Queens problem, $n\times{}n$ neurons have
been grouped into $N$ groups. Each group composed of $N$ neurons
which are located in a same horizontal line (column) or in a same
diagonal line. However, these method did not give convergence results
of 100\% in all size of $N$. Also, they required a large convergence
time steps. In our work, we propose a new $N$-parallel updating method
of the Hopfield-type neural network for $n$-Queens problem, in
which, a new grouping method for $N$ neurons composed in the same
group has been adopted. As a result, simulation results of the proposed
method show a best performance than the previous generally.},
url = {http://ieeexplore.ieee.org/servlet/opac?punumber=10421}
}
@ARTICLE{Letavec2002,
author = {C. Letavec and J. Ruggiero},
title = {The $n$-Queens Problem},
journal = {INFORMS Transactions on Education},
year = {2002},
volume = {2},
url = {http://archive.ite.journal.informs.org/Vol2No3/LetavecRuggiero/LetavecRuggiero.pdf}
}
@INPROCEEDINGS{Li2004,
author = {P. Li and Z. Guangxi and L. Xiao},
title = {The Low-Density Parity-Check Codes Based on the $n$-Queen Problem},
booktitle = {NRBC: Proceedings of the 2004 ACM Workshop on Next-Generation Residential
Broadband Challenges},
year = {2004},
pages = {37-41},
publisher = {ACM Press},
doi = {10.1145/1026763.1026771},
abstract = {This paper presents a new family of low-density parity-check (LDPC) code,
the sparse parity-check matrix of which is constructed by self-defining non-diagonal identity
sub-matrix that is a solution of the ``$n$n-queen problem". So this sub-matrix is called the
$Q$-matrix and these LDPC codes are called the $Q$-matrixes LDPC codes. The $Q$-matrixes LDPC
codes are good or very good codes with iterative decoding and their Tanner graphs are free of
4-lines cycle. Furthermore, they can be created in cycle form. Their encoding can be achieved
in linear time. Especially, their code length and code rate can be flexible and quickly adjusted
according to the practical situation, and the performance of high rate is also very good.
The other unique excellence is that the large sparse parity-check matrixes of long $Q$-matrixes
LDPC codes require very small storage space. The result of this paper is very significant not
only for designing low complexity encoder, improving performance and reducing the complexity
of the sum-product iterative decoding algorithm, but also for building practice system of
encodable and decodable LDPC code.}
}
@ARTICLE{Lionnet1869,
author = {F.J.E. Lionnet},
title = {Question 963},
journal = {Nouvelles Annales de Math\'ematiques},
year = {1869},
volume = {28},
pages = {560}
}
@BOOK{Lucas1973,
title = {R\'ecr\'eations Math\'ematiques},
publisher = {Librairie Scientifique et Technique Albert Blanchard, Paris},
year = {1973},
author = {E. Lucas},
edition = {2nd (nouveau tirage)}
}
@ARTICLE{Lucas1894,
author = {E. Lucas},
title = {Question 123},
journal = {L{'}Interm\'ediaire des Math\'ematiciens},
year = {1894},
volume = {11},
pages = {67}
}
@ARTICLE{Luria2017,
author = {Z. Luria},
title = {New Bounds on the Number of $n$-Queens Configurations},
journal = {arXiv},
year = {2017},
volume = {arXiv:1705.05225},
abstract = {
In how many ways can $n$ queens be placed on an $n\times n$ chessboard
so that no two queens attack each other? This is the famous $n$-queens problem.
Let $Q(n)$ denote the number of such configurations, and let $T (n)$ be the number of
configurations on a toroidal chessboard. We show that for every $n$ of the form $4^k + 1$,
$T (n)$ and $Q(n)$ are both at least $n^{\Omega(n)}$. This result confirms a conjecture of Rivin,
Vardi and Zimmerman for these values of $n$. We also present new upper bounds
on $T (n)$ and $Q(n)$ using the entropy method, and conjecture that in the case of $T (n)$
the bound is asymptotically tight. Along the way, we prove an upper bound on the
number of perfect matchings in regular hypergraphs, which may be of independent
interest.
},
url = {https://arxiv.org/abs/1705.05225}
}
@BOOK{Madachy1966,
author = {J.S. Madachy},
title = {Mathematics on Vacation},
publisher = {Thomas Nelson and Sons Ltd.},
year = {1966},
annote = {Pages 34--36. Later editions (1979), as Madachy's Mathematical Recreations,
from Dover Publications, Inc.}
}
@ARTICLE{Mandziuk1995,
author = {J. Mandziuk},
title = {Solving the $n$-Queens Problem with a Binary {H}opfield-Type
Network. Synchronous and Asynchronous Model},
journal = {Biological Cybernetics},
year = {1995},
volume = {72},
pages = {439-446},
doi = {10.1007/BF00201419},
abstract = {The application of a discrete Hopfield-type neural network to
solving the NP-Hard optimization problem --- the $N$-Queens Problem (NQP) ---
is presented. The applied network is binary, and at every moment each
neuron potential is equal to either 0 or 1. The network can be implemented
in the asynchronous mode as well as in the synchronous one with n parallel
running processors. In both cases the convergence rate is up to 100\%, and the
experimental estimate of the average computational complexity is polynomial.
Based on the computer simulation results and the theoretical analysis, the proper
network parameters are established. The behaviour of the network is explained.}
}
@ARTICLE{Mandziuk1992,
author = {J. Mandziuk and B. Macukow},
title = {A Neural Network Designed to Solve the $n$-Queens Problem},
journal = {Biological Cybernetics},
year = {1992},
volume = {66},
pages = {375-379},
doi = {10.1007/BF00203674},
abstract = {In this paper we discuss the Hopfield neural network
designed to solve the $N$-Queens Problem (NQP). Our network exhibits good
performance in escaping from local minima of energy surface of the problem.
Only in approximately 1\% of trials it settles in a false stable state
(local minimum of energy). Extenive simulations indicate that the network
is efficient and less sensitive to changes of its initial energy (potentials
of neurons). Two strategies employed to achieve the solution and results of
computer simulation are presented. Some theoretical remarks about convergence
of the network are added.}
}
@INPROCEEDINGS{Manzano2002,
author = {H.A. {Del Manzano} and C. Echevar(r)ia and L. Steinberg},
title = {Quantum Algorithm for $n$-Queens Problem},
booktitle = {Computing Research Conference (CRC2002), Mayag\"uez, Puerto Rico},
year = {2002},
url = {http://www.ece.uprm.edu/crc/crc2002/papers/DelManzano_Hector.pdf}
}
@MISC{MathWorld,
author = {MathWorld},
title = {Queens Problem},
year = {2009},
url = {http://mathworld.wolfram.com/QueensProblem.html},
annote = {Website.}
}
@ARTICLE{McCarty1978,
author = {C.P. McCarty},
title = {Queen Squares},
journal = {The American Mathematical Monthly},
year = {1978},
volume = {85(7)},
pages = {578-580},
doi = {10.2307/2320871}
}
@ARTICLE{McKay2006,
author = {B.D. McKay and J.C. McLeod and I.M. Wanless},
title = {The Number of Transversals in a Latin Square},
journal = {Designs, Codes and Cryptography},
year = {2006},
volume = {40},
pages = {269-284},
doi = {10.1007/s10623-006-0012-8},
abstract = {A Latin Square of order $n$ is an $n\times{}n$ array of $n$ symbols, in which
each symbol occurs exactly once in each row and column. A transversal is a set of $n$ entries,
one selected from each row and each column of a Latin Square of order $n$ such that no two
entries contain the same symbol. Define $T(n)$ to be the maximum number of transversals over
all Latin squares of order $n$. We show that $b^n \leq T(n) \leq c^n\sqrt{n}\,n!$ for
$n \geq 5$, where $b \approx 1.719$ and $c \approx 0.614$. A corollary of this result is an
upper bound on the number of placements of n non-attacking queens on an $n\times{}n$ toroidal
chess board. Some divisibility properties of the number of transversals in Latin squares based
on finite groups are established. We also provide data from a computer enumeration of transversals
in all Latin Squares of order at most 9, all groups of order at most 23 and all possible
turn-squares of order 14.}
}
@ARTICLE{Menon1965,
author = {V.V. Menon},
title = {Problem {E}1782: Coloring a Chessboard},
journal = {The American Mathematical Monthly},
year = {1965},
volume = {72(4)},
pages = {421},
doi = {10.2307/2313512}
}
@ARTICLE{MenonGoldberg1966,
author = {V.V. Menon and M. Goldberg},
title = {Problem {E}1782: Coloring a Chessboard},
journal = {The American Mathematical Monthly},
year = {1966},
volume = {73(6)},
pages = {670-671},
doi = {10.2307/2314824},
refersto = {\cite{Menon1965}}
}
@ARTICLE{Minton1992,
author = {S. Minton and M.D. Johnston and A.B. Philips and P. Laird},
title = {Minimizing Conflicts: {A} Heuristic Repair Method for Constraint
Satisfaction and Scheduling Problems},
journal = {Artificial Intelligence},
year = {1992},
volume = {58},
pages = {161-205},
doi = {10.1016/0004-3702(92)90007-K},
refersto = {\cite{Abramson1989}, \cite{Bitner1975}, \cite{Kale1990}, \cite{Morris1992},
\cite{Sosic1990}, \cite{Stone1987}},
abstract = {The paper describes a simple heuristic approach to solving large-scale
constraint satisfaction and scheduling problems. In this approach one starts with an
inconsistent assignment for a set of variables and searches through the space of possible
repairs. The search can be guided by a value-ordering heuristic, the min-conflicts heuristic,
that attempts to minimize the number of constraint violations after each step.
The heuristic can be used with a variety of different search strategies.
We demonstrate empirically that on the $n$-queens problem, a technique based on this
approach performs orders of magnitude better than traditional backtracking techniques.
We also describe a scheduling application where the approach has been used successfully.
A theoretical analysis is presented both to explain why this method works well on certain
types of problems and to predict when it is likely to be most effective.}
}
@TECHREPORT{Miyamoto2006,
author = {K. Miyamoto and H. Nakajima},
title = {Solving the $n$-Queens Problem on the Torus Using a
Continuous-Dynamical-System
Model of a Complex-Valued Neural Network of Phasor Type},
institution = {Institute of Electronics, Information and Communication Engineers)},
year = {2006},
number = {106},
abstract = {A method of solving the $n$-Queens problem on the Torus based on
a complex-valued neural network of phasor type, which has its state
variables on the unit circle in the complex plane, is considered.
First, the positions of Queens on the chessboard are represented
by the states of $N$ neurons, and a rule of updating the states are
defined as a continuous dynamical system that minimizes an energy
function of the states of neurons. To confirm the validity of this
method, the stability of the solutions and the geometrical structure
of the solution space are analyzed. The result of the analysis is
investigated by numerical experiments, and it is found that the problem
is solved well when $N$ is 5 and 7.}
}
@ARTICLE{Monsky1978,
author = {P. Monsky},
title = {Problem {E}2698: Superimposable Solutions},
journal = {The American Mathematical Monthly},
year = {1978},
volume = {85(2)},
pages = {116-117},
doi = {10.2307/2321794}
}
@ARTICLE{Monsky1979,
author = {P. Monsky and R.Z. Goldstein},
title = {Problem {E}2698: Toroidal $n$-Queens problem},
journal = {The American Mathematical Monthly},
year = {1979},
volume = {86(4)},
pages = {309-310},
url = {http://www.jstor.org/stable/2320763},
refersto = {\cite{Monsky1978}}
}
@ARTICLE{Monsky1986,
author = {P. Monsky},
title = {Problem {E}3162: Superqueens},
journal = {The American Mathematical Monthly},
year = {1986},
volume = {93(7)},
pages = {566},
doi = {10.2307/2323039}
}
@ARTICLE{Monsky1989,
author = {P. Monsky},
title = {Problem {E}3162: Superqueens},
journal = {The American Mathematical Monthly},
year = {1989},
volume = {96(3)},
pages = {258-259},
doi = {10.2307/2325220},
refersto = {\cite{Monsky1986}}
}
@INPROCEEDINGS{Morris1992,
author = {P. Morris},
title = {On the Density of Solutions in Equilibrium Points for the
Queens Problem},
booktitle = {Proceedings AAAI Conference on Artificial Intelligence AAAI-92},
year = {1992},
url = {www.aaai.org/Papers/AAAI/1992/AAAI92-066.pdf},
refersto = {\cite{Sosic1991}}
}
@ARTICLE{Nadel1990,
author = {B.A. Nadel},
title = {Representation Selection for Constraint Satisfaction: {A} Case
Study Using $n$-Queens},
journal = {IEEE Expert},
year = {1990},
volume = {5},
pages = {16-23},
abstract = {Representation selection for a constraint satisfaction problem ({CSP})
is addressed. The {CSP} problem class is introduced and the classic
$n$-Queens problem is used to show that many different {CSP} representations
may exist for a given real-world problem. The complexities of solving
these alternative representations are compared empirically and theoretically.
The good agreement found is due to two key features of the analytic
results, their generality and their precision (or instance specificity),
which are also discussed. The $n$-Queens problem is used only to
provide a convenient case study; the approach to {CSP} representation
selection applies to arbitrary problems that can be formulated in
terms of {CSP} and, when the corresponding mathematical results are
available, should also be readily applicable when selecting representations
in domains other than {CSP}},
doi = {10.1109/64.54670}
}
@INPROCEEDINGS{Nakaguchi1999,
author = {Nakaguchi, T. and Jin'no, K. and Tanaka, M.},
title = {Theoretical Analysis of Hysteresis Neural Network solving
$n$-Queens Problems},
booktitle = {Proceedings IEEE International Symposium on Circuits and Systems (ISCAS'99)},
year = {1999},
pages = {555-558},
doi = {10.1109/ISCAS.1999.777632},
abstract = {We propose a hysteresis neural network system solving NP-hard
optimization problems, the $N$-Queens Problem. The continuous system with binary
outputs searches a solution of the problem without energy function. The output
vector corresponds to a complete solution when the output vector becomes stable.
That is, this system does never become stable without satisfying the constraints
of the problem. Through it is very hard to remove limit cycles completely from this
system, we can propose a new method to reduce the possibility of limit cycle by
controlling time constants.}
}
@ARTICLE{Nauck1850,
author = {F. Nauck},
title = {Briefwechsel mit {A}llen f\"ur {A}lle},
journal = {Leipziger Illustrierte Zeitung},
year = {1850},
volume = {377},
pages = {182},
annote = {Franz Nauck outlined the first complete solution of the 8x8 chessboard,
consisting of 92 solutions, in the Leipzig Illustrierte Zeitung in
1850.}
}
@ARTICLE{Naur1972,
author = {P. Naur},
title = {An experiment on Program Development},
journal = {BIT},
year = {1972},
volume = {12},
pages = {347-365},
doi = {10.1007/BF01932307},
abstract = {As a contribution to programming methodology, the paper contains
a detailed, step-by-step account of the considerations leading to a program
for solving the 8-queens problem. The experience is related to the method of
stepwise refinement and to general problem solving techniques.},
refersto = {\cite{Wirth1971}}
}
@BOOK{Netto1901,
title = {Lehrbuch der {C}ombinatorik},
publisher = {B.G. Teubner, Leipzig},
year = {1901},
author = {E. Netto},
annote = {Chapter 3, Section 39. Several editions.}
}
@ARTICLE{Nivasch2005,
author = {G. Nivasch and E. Lev},
title = {Non-Attacking Queens on a Triangle},
journal = {Mathematics Magazine},
year = {2005},
volume = {78},
pages = {399-403},
url = {http://www.jstor.org/stable/30044202}
}
@INPROCEEDINGS{Noguchi2006,
author = {W. Noguchi and C.-K. Pham},
title = {A Proposal to Solve $n$-Queens Problems Using Maximum Neuron Model
with A Modified Hill-Climbing Term},
booktitle = {Proceedings International Joint Conference on Neural Networks (IJCNN'06)},
year = {2006},
pages = {2679-2682},
doi = {10.1109/IJCNN.2006.247149},
abstract = {An effective solving method with a modified hill-climbing term which is applied
to a maximum neuron model for the $N$-Queens problems is proposed. In which, a first model
using a gradient ascent learning for determining A and B coefficients, a second model using
fixed A and B coefficients which are determined by an upper bound of an input value to a
neuron, and a third model using modified initial values which applied to the second model,
have been adopted. As a result, calculation times are reduced when compared with the
previous methods.}
}
@MASTERSTHESIS{Noon2002,
author = {H. Noon},
title = {Surreal Numbers and the $n$-Queens Game},
school = {Bennington College, Bennington, Vermont, US},
year = {2002},
url = {http://www.liacs.nl/home/kosters/nqueens/papers/noon2002.pdf}
}
@ARTICLE{Noon2006,
author = {H. Noon and G. {Van Brummelen}},
title = {The Non-Attacking Queens Game},
journal = {College Mathematics Journal},
year = {2006},
volume = {37},
pages = {223-227},
url = {http://www.jstor.org/stable/27646335},
abstract = {Gauss found a solution to the problem (first posed by Max Bezzel in 1848) of
placing $n$ queens on an $n\times{}n$ chessboard so that no queen is attacked by another.
The $n$alfaro-queens game considered here is this: Two players alternately place queens on
a board so that no two attack one another, and the winner is the player who places a
queen so that all squares are attacked.},
refersto = {\cite{Bezzel1848}, \cite{Campbell1977}, \cite{Ginsburg1939},
\cite{Schrage1989}}
}
@ARTICLE{Nudelman1995,
author = {S.P. Nudelman},
title = {The Modular $n$-Queens Problem in Higher Dimensions},
journal = {Discrete Mathematics},
year = {1995},
volume = {146},
pages = {159-167},
doi = {10.1016/0012-365X(94)00161-5},
abstract = {Let $M(n, d)$ denote the maximum number of queens on a $d$-dimensional modular
chessboard such that no two attack each other. We show that if $\gcd(n, (2d - 1)!) = 1$
then $M (n, d) = n$. We also prove that if $\gcd(n, (2d - 1)!) > 1$ then there are no
complete linear solutions, and if $\gcd(n, (2d - 1)!) > 1$ then $M (n, d) < n$. Moreover,
if $n \leq 2^d - 1$ we show $M (n, d) = 1$.}
}
@ARTICLE{Oestergard2001,
author = {P.R.J. Oesterg{\aa}rd and W.D. Weakley},
title = {Values of Domination Numbers of the Queen's Graph},
journal = {The Electronic Journal of Combinatorics},
year = {2001},
volume = {8(1)},
number = {R29},
pages = {1-19},
url = {http://www.combinatorics.org/ojs/index.php/eljc/article/view/v8i1r29/pdf}
}
@ARTICLE{Oh1993,
author = {S.B. Oh},
title = {An Analytical Evidence for {K}al\'e's Heuristic for the ${N}$ Queens Problem},
journal = {Information Processing Letters},
year = {1993},
volume = {46},
pages = {51-54},
doi = {10.1016/0020-0190(93)90196-G},
refersto = {\cite{Kale1990}}
}
@BOOK{Okunev1935,
title = {Kombinatornye Zadachi na Shakhmatnoi Doske},
publisher = {ONTI, Moscow, Leningrad},
year = {1935},
author = {L.Y. Okunev}
}
@ARTICLE{Olson1993,
author = {A.T. Olson},
title = {The Eight Queens Problem},
journal = {Journal of Computers in Mathematics and Science Teaching},
year = {1993},
volume = {12},
pages = {93}
}
@ARTICLE{Panayotopoulos1986,
author = {A. Panayotopoulos},
title = {Generating Stable Permutations},
journal = {Discrete Mathematics},
year = {1986},
volume = {62},
pages = {219-221},
doi = {10.1016/0012-365X(86)90121-4}
}
@ARTICLE{Parmentier1883,
author = {T. Parmentier},
title = {Probl\`eme des $n$-reines},
journal = {Comptes Rendus de l{'}{A}ssociation Fran\c{c}aise pour l{'}Avancement
des Sciences},
year = {1883},
pages = {197-213},
organization = {Association Fran\c{c}aise pour l{'}{A}vancement des Sciences,
Congr\`es de Rouen}
}
@ARTICLE{Pauls1874,
author = {Pauls},
title = {Das {M}aximalproblem der {D}amen auf dem {S}chachbrete},
journal = {Deutsche Schachzeitung, Organ f\"ur das Gesammte Schachleben},
year = {1874},
volume = {29},
pages = {129-134, 257-267}
}
@MISC{Pearson,
author = {C.S. Pearson and M.S. Pearson},
title = {Analysis of the n-Queens Puzzle in 2 and 3 Dimensions},
year = {2009},
url = {http://queens.cspea.co.uk/},
annote = {Website.}
}
@MISC{Pegg2005,
author = {{Pegg Jr.}, E.},
title = {Math Games: {C}hessboard Tasks},
year = {2005},
url = {http://www.maa.org/editorial/mathgames/mathgames_04_11_05.html},
annote = {Website.}
}
@BOOK{Petkovic1997,
title = {Mathematics and Chess (110 Entertaining Problems and Solutions)},
publisher = {Dover Publications Inc.},
year = {1997},
author = {M. Petkovi\'c}
}
@BOOK{Pickover2002,
title = {The Zen of Magic Squares, Circles, and Stars (An Exhibition of Surprising
Structures Across Dimensions)},
publisher = {Princeton University Press, Princeton, NJ},
year = {2002},
author = {C.A. Pickover}
}
@ARTICLE{Planck1900,
author = {C. Planck},
title = {The $n$-Queens Problem},
journal = {British Chess Magazine},
year = {1900},
volume = {20(4)},
pages = {94-97}
}
@BOOK{Polster1998,
title = {A Geometrical Picture Book},
publisher = {Springer},
year = {1998},
author = {B. Polster}
}
@ARTICLE{Poulet1922,
author = {P. Poulet},
title = {Suites de Nombres},
journal = {L{'}Intermediaire des {m}ath\'ematiciens},
year = {1922},
volume = {21},
pages = {92-93}
}
@INBOOK{Polya1918,
chapter = {{\"U}ber die ``doppelt-periodischen'' {L}\"osungen des ${N}$-{D}amen-{P}roblems},
title = {Mathematische {U}nterhaltungen und {S}piele},
publisher = {B.G. Teubner},
year = {1918},
author = {G. P{\'o}lya},
annote = {In the 1918 edition of \cite{Ahrens1901}.
Also G. P\'olya, Collected Works, Vol. IV, 237--247.}
}
@ARTICLE{Preusser2016,
title = {Putting Queens in Carry Chains, No. 27},
author = {T.B. Preu{\ss}er and M.R. Engelhardt},
journal = {Journal of Signal Processing Systems},
year = {2016},
doi = {10.1007/s11265-016-1176-8},
abstract = {The $N$-Queens Puzzle is a fascinating combinatorial
problem. Up to now, the number of distinct valid
placements of $N$ non-attacking queens on a generalized $N\times N$
chessboard cannot be computed by a formula. The computation
of these numbers is instead based on an exhaustive
search whose complexity grows dramatically with the problem
size $N$. Solutions counts are currently known for all
$N$ up to 26. The parallelization of the search for solutions
is embarrassingly simple. It is achieved by pre-placing the
queens within a certain board region. These pre-placements
partition the search space. The chosen extent of the preplacement
allows for a wide range of the partitioning granularity.
This ease of partitioning makes the $N$-Queens Puzzle
a great show-off case for tremendously parallel computation
approaches and a flexible benchmark for parallel compute
resources. This article presents the Q27 Project, an opensource
effort targeting the computation of the solution count
of the 27-Queens Puzzle. It is the first undertaking pushing
the frontier of the $N$-Queens Puzzle that exploits the
complete symmetry group $D_4$ of the square. This reduces
the overall computational complexity already to an eighth in
comparison to a naive exploration of the whole search space.
This article details the coronal pre-placement that enables
the partitioning of the overall search under this approach.
With respect to the physical implementation of the computation,
it describes the hardware structure that explores
the resulting subproblems efficiently by exploiting bit-level
operations and their mapping to FPGA devices as well as
the infrastructure that organizes the contributing devices
in a distributed computation. The performance of several
FPGA platforms is evaluated using the Q27 computation
as a benchmark, and some intriguing observations obtained
from the available partial solutions are presented. Finally,
an estimate on the remaining run time and on the expected
magnitude of the final result is dared.
}
}
@ARTICLE{Qiu1986,
author = {W.S. Qiu},
title = {The $n$-Queens Problem},
journal = {Journal of Mathematics (Wuhan)},
year = {1986},
volume = {6(2)},
pages = {117-130}
}
@ARTICLE{Qiu2002,
author = {Z. Qiu},
title = {Bit-Vector Encoding of $n$-Queen Problem},
journal = {ACM SIGPLAN Notices},
year = {2002},
volume = {37},
pages = {68-70},
abstract = {8-queen problem and its generalization, n-queen problem are
well-known examples in the textbooks on elementary programming, data structures,
and algorithms. Different methods are proposed to solve these problems, for example,
in \cite{Wirth1976}. In this paper, we present a purely bit-vector encoding of the
$n$-queen problem. It is very natural, simple to understand, and efficient.
It involves only bit-wise operations.},
doi = {10.1145/568600.568613},
refersto = {\cite{Wirth1976}}
}
@ARTICLE{Raghavan1987,
author = {V. Raghavan and S.M. Venkatesan},
title = {On Bounds for a Board Covering Problem},
journal = {Information Processing Letters},
year = {1987},
pages = {281-284},
volume = {25},
doi = {10.1016/0020-0190(87)90201-8}
}
@INPROCEEDINGS{Rees1981,
author = {G.H.J. {Van Rees}},
title = {On Latin Queen Squares},
booktitle = {Proceedings of the Tenth Manitoba Conference on Numerical Mathematics
and Computing},
year = {1981},
volume = {II},
pages = {267–273}
}
@ARTICLE{Reichling1987,
author = {M. Reichling},
title = {A Simplified Solution of the ${N}$ Queens' Problem},
journal = {Information Processing Letters},
year = {1987},
volume = {25},
pages = {253-255},
refersto = {\cite{Falkowski1986}},
doi = {10.1016/0020-0190(87)90171-2}
}
@INPROCEEDINGS{Rivin1989,
author = {I. Rivin and R. Zabih},
title = {An Algebraic Approach to Constraint Satisfaction Problems},
booktitle = {Proceedings Eleventh International Joint Conference on Artificial Intelligence (IJCAI)},
year = {1989},
pages = {284-289},
url = {http://dli.iiit.ac.in/ijcai/IJCAI-89-VOL1/PDF/045.pdf},
abstract = {A constraint satisfaction problem, or CSP, can be reformulated as an integer
linear programming problem. The reformulated problem can be solved via polynomial multiplication.
If the CSP has $n$ variables whose domain size is $m$, and if the equivalent programming
problem involves $M$ equations, then the number of solutions can be determined in time
$0(nm2^{M-n})$. This surprising link between search problems and algebraic techniques allows us
to show improved bounds for several constraint satisfaction problems, including new simply
exponential bounds for determining the number of solutions to the $n$-queens problem. We also
address the problem of minimizing $M$ for a particular CSP.},
refersto = {\cite{Garey1983}, \cite{Rivin1994}}
}
@ARTICLE{Rivin1994,
author = {I. Rivin and I. Vardi and P. Zimmerman},
title = {The $n$-Queens Problem},
journal = {The American Mathematical Monthly},
year = {1994},
volume = {101(7)},
pages = {629-639},
doi = {10.2307/2974691}
}
@ARTICLE{Rivin1992,
author = {I. Rivin and R. Zabih},
title = {A Dynamic Programming Solution to the $n$-Queens Problem},
journal = {Information Processing Letters},
year = {1992},
volume = {41},
pages = {253-256},
doi = {10.1016/0020-0190(92)90168-U},
abstract = {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)8^n)$ 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.},
annote = {This article refers to a preprint of \cite{Rivin1994} published in
1990.}
}
@ARTICLE{Rohl1983,
author = {J.S. Rohl},
title = {A Faster Lexicographical ${N}$ Queens Algorithm},
journal = {Information Processing Letters},
year = {1983},
volume = {17},
pages = {231-233},
doi = {10.1016/0020-0190(83)90104-7}
}
@ARTICLE{Rolfe1995,
author = {T.J. Rolfe},
title = {Queens on a Chessboard: {M}aking the Best of a Bad Situation},
journal = {SCCS: Proceedings of the 28th Annual Small College Computing Symposium},
year = {1995},
volume = {28},
pages = {201-210},
abstract = {Placing Queens on a chessboard is a classic use of backtracking
to speed up a worse than exponential-time algorithm. After the discussion
of the basic problem and its solution, two algorithm optimizations
are presented (both optimizations together increase the processing
speed by an order of magnitude for sufficiently large boards), along
with a symmetry constraint on acceptable board configurations.
The fully optimized algorithm is then used to show three separate
approaches to using parallel processing to further speed the solution:
(1) using fork() on a UNIX multiprocessor, (2) using a shared-memory
multiprocessor (Silicon Graphics 4D/380), and (3) programming in
a message-passing distributed-memory environment (PVM on RS/6000
computers).},
url = {http://penguin.ewu.edu/~trolfe/SCCS-95/SCCS-95.html}
}
@ARTICLE{Rolfe2006,
author = {T.J. Rolfe},
title = {Las {V}egas does $n$-Queens},
journal = {ACM SIGCSE Bulletin},
year = {2006},
pages = {37-38},
volume = {38},
abstract = {This paper presents two Las Vegas algorithms to generate single solutions
to the $n$-queens problem. One algorithm generates and improves on random permutation
vectors until it achieves one that is a successful solution, while the other
algorithm randomly positions queens within each row in
positions not under attack from above.},
doi = {10.1145/1138403.1138429}
}
@MISC{Ruskey,
author = {F. Ruskey},
title = {Information on the $n$-Queens Problem},
annote = {Website.},
url = {http://www.theory.csc.uvic.ca/~cos/inf/misc/Queen.html}
}
@ARTICLE{Sagols2002,
author = {F. Sagols and C.J. Colbourn},
title = {{NS1D0} Sequences and {A}nti-{P}asch {S}teiner {T}riple {S}ystems},
journal = {Ars Combinatoria},
year = {2002},
volume = {62},
pages = {17-31}
}
@INBOOK{Sainte-Lagu:e1926,
chapter = {Les R\'eseaux (ou Graphes)},
title = {M\'emorial des Sciences Math\'ematiques},
publisher = {Gauthier-Villars, Paris},
year = {1926},
author = {A. Sainte-Lague},
volume = {18}
}
@ARTICLE{SanSegundo2011,
author = {P. {San Segundo}},
title = {New Decision Rules for Exact Search in {N}-Queens},
journal = {Journal of Global Optimization},
year = {2011},
volume = {TBA},
pages = {1-18},
doi = {10.1007/s10898-011-9653-x},
abstract = {This paper presents a set of new decision rules for exact search in N-Queens. Apart from new tiebreaking strategies for value and variable ordering, we introduce the notion of ‘free diagonal’ for decision taking at each step of the search. With the proposed new decision heuristic the number of subproblems needed to enumerate the first $K$ solutions (typically $K$ = 1, 10 and 100) is greatly reduced w.r.t. other algorithms and constitutes empirical evidence that the average solution density (or its inverse, the number of subproblems per solution) remains constant independent of N. Specifically finding a valid configuration was backtrack free in 994 cases out of 1,000, an almost perfect decision ratio. This research is part of a bigger project which aims at deriving new decision rules for CSP domains by evaluating, at each step, a constraint value graph $G_c$. N-Queens has adapted well to this strategy: domain independent rules are inferred directly from $G_c$ whereas domain dependent knowledge is represented by an induced hypergraph over $G_c$ and computed by similar domain independent techniques. Prior work on the Number Place problem also yielded similar encouraging results.}
}
@ARTICLE{Scheid1960,
author = {F. Scheid},
title = {Some Packing Problems},
journal = {The American Mathematical Monthly},
year = {1960},
volume = {67(3)},
pages = {231-235},
doi = {10.2307/2309682}
}
@TECHREPORT{Schlude2003,
author = {K. Schlude and E. Specker},
title = {Zum {P}roblem der {D}amen auf dem {T}orus},
institution = {Departement Informatik, Eidgenossische Technische Hochschule (ETH) Z\"urich},
year = {2003},
number = {412}
}
@ARTICLE{Schrage1989,
author = {G. Schrage},
title = {The Eight Queens Problem as a Strategy Game},
journal = {International Journal of Mathematical Education in Science and Technology},
year = {1989},
volume = {17},
pages = {143-148},
abstract = {A strategy game is presented that is strongly connected to the
classical `eight queens problem' for checkerboards. Two different versions
of the game are analysed with computer assistance. The algorithm for this
analysis is developed in terms of a general game model. Thus it can be
used, at least in principal, for any two-person strategy game. },
doi = {10.1080/0020739860170203}
}
@BOOK{Schroeder1991,
title = {Fractals, Chaos, Power Laws: {M}inutes from an Infinite Paradise},
publisher = {W.H. Freeman and Company, New York},
year = {1991},
author = {M. Schroeder}
}
@BOOK{Schwartz1986,
title = {An Introduction to {SETL}},
publisher = {Springer-Verlag},
year = {1986},
author = {J.T. Schwartz and R.B.K. Dewar and E. Dubinsky and E. Schonberg},
annote = {Chapter 7: Programming with Sets.
The $n$-Queens problem is solved using the programming language
{SETL}.}
}
@ARTICLE{Sebastian1969,
author = {J.D. Sebastian},
title = {Some Computer Solutions to the Reflecting Queens Problem},
journal = {The American Mathematical Monthly},
year = {1969},
volume = {76(4)},
pages = {399-400},
doi = {10.2307/2316435}
}
@ARTICLE{Selfridge1963,
author = {J.L. Selfridge},
title = {Abstract 63T-80: Pairings of the First $2n$ Integers so that Sums and Differences are All Distinct},
journal = {Notices of the American Mathematical Society},
year = {1963},
volume = {19},
pages = {195}
}
@ARTICLE{Sforza1925,
author = {G. Sforza},
title = {Una Regola pel Gioco della $n$ Regine Quando $n$ \'e Primo},
journal = {Periodicodi Matematiche. Organo della Mathesis, Societ\'a Italiana
di Scienze Mathematichee Fisiche},
year = {1925},
volume = {5(4)},
pages = {107-109}
}
@ARTICLE{Shagrir1992,
author = {O. Shagrir},
title = {A Neural Net with Self-inhibiting Units for the $n$-Queens Problem},
journal = {International Journal of Neural Systems},
year = {1992},
volume = {3},
pages = {249-252},
abstract = {Suggested here is a neural net algorithm for the $n$-Queens problem.
The net is basically a Hopfield net but with one major difference:
every unit is allowed to inhibit itself. This distinctive characteristic
enables the net to escape efficiently from all local minima. The
net’s dynamics then can be described as a travel in paths of low-level
energy spaces until it finds a solution (global minimum). The paper
explains why standard Hopfield nets have failed to solve the Queens
problem and proofs that the self-inhibiting net (NQ2 algorithm in
the text) never stabilizes in local minima and relaxes when it falls
into a global minimum are provided. The experimental results supported
by theoretical explanation indicate that the net never continually
oscillates but relaxes into a solution in polynomial time. In addition,
it appears that the net solves the Queens problem regardless of
the dimension n or the initialized values. The net uses only few
parameters to fix the weights; all globally determined as a function
of $n$.},
doi = {10.1142/S0129065792000206}
}
@ARTICLE{Shapiro1978,
author = {H.D. Shapiro},
title = {Generalized Latin Squares on the Torus},
journal = {Discrete Mathematics},
year = {1978},
volume = {24},
pages = {63-77},
doi = {10.1016/0012-365X(78)90173-5},
abstrat = {The notion of a Latin square is generalized. The natural object on which to
define this extension is the torus. A theorem is proved which shows that the existence of
a Latin square implies the existence of a linear Latin square, a Latin square with special
form. The theorems in the paper are used to provide alternate proofs of results due to
P\'olya and Chandra (in relation to a problem of Moser).
The inability to extend the results to orthogonal Latin squares is noted.},
refersto = {\cite{Chandra1974}, \cite{Polya1918}}
}
@ARTICLE{Shapiro1978a,
author = {H.D. Shapiro},
title = {Theoretical Limitations on the Efficient Use of Parallel Memories},
journal = {IEEE Transactions on Computers},
year = {1978},
volume = {C-27},
pages = {421-428},
doi = {10.1109/TC.1978.1675122},
abstract = {The effective utilization of single-instruction-multiple-data stream machines
depends heavily on being able to arrange the data elements of arrays in parallel memory
modules so that memory conflicts are avoided when the data are fetched. Several classes of
storage algorithms are presented. Necessary and sufficient conditions are derived which can
be used to determine if all conflict can be avoided. For the matrix subparts most often
demanded in numerical analysis computations, whenever the class of storage algorithms
called periodic skewing schemes provides conflict-free access, the subclass called linear
skewing schemes also provides such access.}
}
@ARTICLE{Shen1962,
author = {M.-K. Shen and T.-P. Shen},
title = {Research Problem 39},
journal = {Bulletin of the American Mathematical Society},
year = {1962},
volume = {68},
pages = {557},
doi = {10.1090/S0002-9904-1962-10842-8}
}
@INPROCEEDINGS{Silva2000,
author = {I.N. da Silva and A.N. de Souza and M.E. Bordon},
title = {A Modified {H}opfield Model for Solving the ${N}$-Queens Problem},
booktitle = {Neural Networks, Proceedings of the {IEEE-INNS-ENNS} International
Joint Conference on},
year = {2000},
pages = {$509 - 514$},
abstract = {A neural network model for solving the $N$-Queens problem is presented
in this paper. More specifically, a modified Hopfield network is
developed and its internal parameters are computed using the valid-subspace
technique. These parameters guarantee the convergence of the network
to the equilibrium points. The network is shown to be completely
stable and globally convergent to the solutions of the $N$-Queens
problem. Simulation results are presented to validate the proposed
approach.},
doi = {10.1109/IJCNN.2000.859446}
}
@ARTICLE{Slater1963,
author = {M. Slater},
title = {Research Problem 1},
journal = {Bulletin of the American Mathematical Society},
year = {1963},
volume = {69},
pages = {333},
doi = {10.1090/S0002-9904-1963-10907-6},
refersto = {\cite{Shen1962}}
}
@MISC{Sloane000170,
author = {N.J.A. Sloane},
title = {Sequence {A}000170: {N}umber of Ways of Placing $n$ Nonattacking Queens
on $n\times{}n$ Board},
howpublished = {The On-Line Encyclopedia of Integer Sequences (OEIS)},
url = {https://oeis.org/search?q=A000170},
abstract = {1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596, 2279184,
14772512, 95815104, 666090624, 4968057848, 39029188884, 314666222712, 2691008701644,
24233937684440, 227514171973736, 2207893435808352, \ldots}
}
@MISC{Sloane001366,
author = {N.J.A. Sloane},
title = {Sequence {A}001366: {M}aximal Number of Unattacked Squares with $n$-Queens
on $n\times{}n$ Board (Answers for $n \geq 17$ only Probable)},
howpublished = {The On-Line Encyclopedia of Integer Sequences (OEIS)},
url = {https://oeis.org/search?q=A001366},
abstract = {0, 0, 0, 1, 3, 5, 7, 11, 18, 22, 30, 36, 47, 56, 72, 82, 97, 111, 132,
145, 170, 186, 216, 240, 260, 290, 324, 360, 381, 420, \ldots}
}
@MISC{Sloane002562,
author = {N.J.A. Sloane},
title = {Sequence {A}002562: {N}umber of Ways of Placing $n$ Nonattacking Queens
on $n\times{}n$ Board (Symmetric Solutions Count only Once)},
howpublished = {The On-Line Encyclopedia of Integer Sequences (OEIS)},
url = {https://oeis.org/search?q=A002562},
abstract = {1, 0, 0, 1, 2, 1, 6, 12, 46, 92, 341, 1787, 9233, 45752, 285053, 1846955,
11977939, 83263591, 621012754, 4878666808, 39333324973, 336376244042, 3029242658210,
28439272956934, 275986683743434, \ldots}
}
@MISC{Sloane006717,
author = {N.J.A. Sloane},
title = {Sequence {A}006717: {T}oroidal Semi-Queens on a $(2n+1) \times{} (2n+1)$
Board},
howpublished = {The On-Line Encyclopedia of Integer Sequences (OEIS)},
url = {https://oeis.org/search?q=A006717},
abstract = {1, 3, 15, 133, 2025, 37851, 1030367, 36362925, 1606008513, 87656896891,
5778121715415, 452794797220965, 41609568918940625, \ldots}
}
@MISC{Sloane007705,
author = {N.J.A. Sloane},
title = {Sequence {A}007705: {N}umber of Ways of Arranging $ 2n+1 $ Nonattacking
Queens on a $(2n+1)\times{}(2n+1)$ Toroidal Board},
howpublished = {The On-Line Encyclopedia of Integer Sequences (OEIS)},
url = {https://oeis.org/search?q=A007705},
abstract = {1, 0, 10, 28, 0, 88, 4524, 0, 140692, 820496, 0, 128850048, 1957725000,
0, 605917055356, 13404947681712, 0, \ldots}
}
@MISC{Sloane019317,
author = {N.J.A. Sloane},
title = {Sequence {A}019317: {P}lace $n$ Queens on an $n\times{}n$ Board so
as to Leave the Maximal Number of Unattacked Squares; Sequence Gives
Number of Different Solutions},
howpublished = {The On-Line Encyclopedia of Integer Sequences (OEIS)},
url = {https://oeis.org/search?q=A019317},
abstract = {1, 2, 16, 25, 1, 3, 38, 7, 1, 1, 2, 7, 1, 4, 3, 1, \ldots}
}
@MISC{Sloane051906,
author = {N.J.A. Sloane},
title = {Sequence {A}051906: {N}umber of Ways of Placing $n$ Nonattacking Toroidal
Queens on an $n \times{} b$ Chess Board},
howpublished = {The On-Line Encyclopedia of Integer Sequences (OEIS)},
url = {https://oeis.org/search?q=A051906},
abstract = {1, 0, 0, 0, 10, 0, 28, 0, 0, 0, 88, 0, 4524, 0, 0, 0, 140692, 0,
820496, 0, 0, 0, 128850048, 0, 1957725000, 0, 0, 0, 605917055356, \ldots}
}
@MISC{Sloane053994,
author = {N.J.A. Sloane},
title = {Sequence {A}053994: {N}onattacking Queens on a $(2n+1)\times{}(2n+1)$
Toroidal Board, Solutions which Differ only by Rotation, Reflection
or Torus Shift Count only Once},
howpublished = {The On-Line Encyclopedia of Integer Sequences (OEIS)},
url = {https://oeis.org/search?q=A053994},
abstract = {1, 0, 1, 1, 0, 2, 11, 0, 97, 354, 0, 31381, 395551, 0, 90120677, \ldots}
}
@MISC{Sloane054500,
author = {N.J.A. Sloane},
title = {Sequence {A}054500: {I}ndicator Sequence for Classification of Nonattacking
Queens on $n\times{}n$ Toroidal Board},
howpublished = {The On-Line Encyclopedia of Integer Sequences (OEIS)},
url = {https://oeis.org/search?q=A054500},
abstract = {1, 5, 7, 11, 13, 13, 13, 13, 17, 17, 17, 17, 17, 19, 19, 19, 23, 23, 23, 25,
25, 25, 25, 25, 25, 25, 25, 29, 29, 29, 29, 29, \ldots}
}
@MISC{Sloane1995,
author = {N.J.A. Sloane and S. Plouffe},
title = {Figure {M}0180 in {T}he Encyclopedia of Integer Sequences.},
howpublished = {San Diego: Academic Press},
year = {1995}
}
@MISC{Smet2014,
author = {G. De Smet},
title = {Cheating on the $N$ Queens benchmark},
year = {2014},
url = {http://www.optaplanner.org/blog/2014/05/12/CheatingOnTheNQueensBenchmark.html},
annote = {Website.}
}
@INPROCEEDINGS{Sosic1994,
author = {Sosic, R.},
title = {A Parallel Search Algoritm for the $n$-Queens Problem},
booktitle = {Parallel Computing and Transputer Conference, Wollongong},
year = {1994},
pages = {162-172},
publisher = {IOS Press}
}
@ARTICLE{Sosic1994a,
author = {R. Sosic and J. Gu},
title = {Efficient Local Search with Conflict Minimization: {A} Case Study of
the $n$-Queens Problem},
journal = {IEEE Transactions on Knowledge and Data Engineering},
year = {1994},
volume = {6(5)},
pages = {661-668},
abstract = {Backtracking search is frequently applied to solve a constraint-based
search problem, but it often suffers from exponential growth of computing
time. We present an alternative to backtracking search: local search
with conflict minimization. We have applied this general search framework
to study a benchmark constraint-based search problem, the $n$-Queens
problem. An efficient local search algorithm for the $n$-Queens
problem was implemented. This algorithm, running in linear time,
does not backtrack. It is capable of finding a solution for extremely
large size $n$-Queens problems. For example, on a workstation it
can find a solution for 3000000 Queens in less than 55 s.},
doi = {10.1109/69.317698},
refersto = {\cite{Abramson1989}, \cite{Ahrens1901}, \cite{Bitner1975}, \cite{Falkowski1986},
\cite{Hoffman1969}, \cite{Kale1990}, \cite{Reichling1987}, \cite{Sosic1988a},
\cite{Stone1987}, \cite{Bernhardsson1991}, \cite{Sosic1991} }
}
@ARTICLE{Sosic1991,
author = {R. Sosic and J. Gu},
title = {$3,000,000$ Queens in Less than One Minute},
journal = {ACM SIGART Bulletin},
year = {1991},
volume = {2},
pages = {22-24},
doi = {10.1145/122319.122325},
abstract = {The $n$-queens problem is a classical combinatorial search problem.
In this paper we give a linear time algorithm for this problem. The algorithm is
an extension of one of our previous local search algorithms [3, 4, 6]. On an
IBM RS 6000 computer, this algorithm is capable of solving problems with
3,000,000 queens in approximately 55 seconds.}
}
@ARTICLE{Sosic1991a,
author = {R. Sosic and J. Gu},
title = {Fast Search Algorithms for the Queens Problem},
journal = {IEEE Transactions on Systems, Man and Cybernetics},
year = {1991},
volume = {21},
pages = {1572-1576},
number = {6},
doi = {10.1109/21.135698},
abstract = {The $n$-queens problem is to place $n$ queens on an $n\times{}n$ chessboard so
that no two queens attack each other. The authors present two new algorithms, called
queen search 2 (QS2) and queen search 3 (QS3). QS2 and QS3 are probabilistic local search
algorithms, based on a gradient-based heuristic. These algorithms, running in almost
linear time, are capable of finding a solution for extremely large $n$-queens problems.
For example, QS3 can find a solution for 500000 queens in approximately 1.5 min.}
}
@ARTICLE{Sosic1990,
author = {R. Sosic and J. Gu},
title = {A Polynomial Time Algorithm for the $n$-Queens Problem},
journal = {ACM SIGART Bulletin},
year = {1990},
volume = {1},
pages = {7-11},
abstract = {The $n$-Queens problem is a classical combinatorial problem in
the artificial intelligence (AI) area. Since the problem has a simple
and regular structure, it has been widely used as a testbed to develop
and benchmark new AI search problem-solving strategies. Recently,
this problem has found practical applications in VLSI testing and
traffic control. Due to its inherent complexity, currently even very
efficient AI search algorithms developed so far can only find a solution
for the $n$-Queens problem with n up to about 100. In this paper
we present a new, probabilistic local search algorithm which is based
on a gradient-based heuristic. This efficient algorithm is capable
of finding a solution for extremely large size $n$-Queens problems.
We give the execution statistics for this algorithm with $n$ up to
500,000.},
doi = {10.1145/101340.101343},
refersto = {\cite{Polya1918}, \cite{Nadel1990}, \cite{Sosic1988b}, \cite{Sosic1988a},
\cite{Stone1987} }
}
@TECHREPORT{Sosic1988a,
author = {R. Sosic and J. Gu},
title = {How to Search For Million Queens},
institution = {Department of Computer Science, University of Utah},
year = {1988},
number = {UUCS-TR-88-008}
}
@MISC{Sosic1988b,
author = {R. Sosic and J. Gu},
title = {$n$-Queen Search on {VAX} and {B}obcat Machines},
journal = {CS 547 AI Class Student Project Report},
year = {1988},
month = {February}
}
@ARTICLE{Sprague1889,
author = {T.B. Sprague},
title = {On the Different Non-Linear Arrangements of Eight Men on a Chess-board},
journal = {Proceedings of the Edinburgh Mathematical Society},
year = {1889},
volume = {8},
pages = {30-43},
doi = {10.1017/S0013091500030522},
abstract = {The question having been proposed to me as a puzzle: To arrange
eight men on a chess-board, so that no two of them shall be in the same
line,—--that is to say, that no two are to be in the same column, nor in
the same row, nor in the same diagonal line,—--I succeeded before very long
in solving it by finding the annexed arrangement.}
}
@ARTICLE{Sprague1898,
author = {T.B. Sprague},
title = {On the Eight Queens Problem},
journal = {Proceedings of the Edinburgh Mathematical Society},
year = {1898},
volume = {17},
pages = {43-68},
doi = {10.1017/S0013091500029096},
abstract = {This is the problem discussed in my paper bearing the not very happy
title ``On the different non-linear arrangements of eight men on a chess-board”,
which was read to the Edinburgh Mathematical Society on 14th March 1890, and is
printed in its Transactions, Vol. VIII, p. 30. At that time I was not aware that
the problem had been discussed by any previous writer, and I treated it as an
entirely new one. I have since learnt that a good deal has been written about
it, and I propose on the present occasion to give briefly the history of the
problem, and the results which have been arrived at; also to communicate some
new results which I have obtained.}
}
@BOOK{Stanley1986,
title = {Enumerative Combinatorics},
publisher = {Wadsworth \& Brooks/Cole Advanced Books \& Software, Monterey, California},
year = {1986},
author = {R.P. Stanley},
volume = {I},
series = {The Wadsworth \& Brooks/Cole Mathematics Series}
}
@BOOK{Steinhaus1938,
title = {Mathematical Snapshots},
year = {1938},
author = {H. Steinhaus},
publisher = {Oxford University Press},
annote = {Translation of Kalejdoskopu matematycznego.
Later editions from Dover Publications, Inc.
Chapter 1: Triangles, Squares and Games; pages 29--30.}
}
@ARTICLE{Stern1939,
author = {E. Stern},
title = {General Formulas for the Number of Magic Squares Belonging to Certain
Classes},
journal = {The American Mathematical Monthly},
year = {1939},
volume = {46(9)},
pages = {555-581},
doi = {10.2307/2302760},
annote = {Translation by W.R. Transue of \cite{Stern1938}.}
}
@ARTICLE{Stern1938,
author = {E. Stern},
title = {{\"U}ber irregulare Pan Diagonale Lateinische {Q}uadrate mit {P}rimzahlseitenlange
und ihre {B}edeutung f\"ur das $n$-{K}\"oniginnenproblem sowie f\"ur
die {B}ildung magischer {Q}uadrate},
journal = {Nieuw Archief voor Wiskunde},
year = {1938},
volume = {19},
pages = {257-270}
}
@ARTICLE{Stoffel1976,
author = {A. Stoffel},
title = {Totally Diagonal Latin Squares},
journal = {Stud. Cerc. Mat.},
year = {1976},
volume = {28(1)},
pages = {113-119}
}
@ARTICLE{Stone1987,
author = {H.S. Stone and J.M. Stone},
title = {Efficient Search Techniques --- {A}n empirical Study of the $n$-Queens
Problem},
journal = {IBM Journal of Research and Development},
year = {1987},
volume = {31},
pages = {464-474},
doi = {10.1147/rd.314.0464},
abstract = {
This paper investigates the cost of finding the first solution to the $N$-Queens Problem using various backtrack search strategies. Among the empirical results obtained are the following: 1) To find the first solution to the $N$-Queens Problem using lexicographic backtracking requires a time that grows exponentially with increasing values of $N$. 2) For most even values of $N < 30$, search time can be reduced by a factor from 2 to 70 by searching lexicographically for a solution to the $N+1$-Queens Problem. 3) By reordering the search so that the queen placed next is the queen with the fewest possible moves to make, it is possible to find solutions very quickly for all $N < 97$, improving running time by dozens of orders of magnitude over lexicographic backtrack search. To estimate the improvement, we present an algorithm that is a variant of algorithms of Knuth and Purdom for estimating the size of the unvisited portion of a tree from the statistics of the visited portion.
}
}
@TECHREPORT{Sumitaka2001,
author = {A. Sumitaka},
title = {Explicit Solutions of the $n$-Queens Problem},
institution = {Information Processing Society of Japan (IPSJ) SIGNotes SYMbol Manipulation},
year = {2001},
number = {060-002}
}
@ARTICLE{Tambouratzis1997,
author = {T. Tambouratzis},
title = {A Simulated Annealing Artificial Neural Network Implementation of
the $n$-Queens Problem},
journal = {International Journal of Intelligent Systems},
year = {1997},
volume = {12},
pages = {739-752},
doi = {10.1002/(SICI)1098-111X(199710)12:10<739::AID-INT3>3.0.CO;2-Z},
abstract = {A Harmony Theory artificial neural network implementation of the
$n$-Queens problem is presented in this piece of research. The
problem is encoded in the two layers of the artificial neural network
in such a manner that the inherent constraints of the problem are
made directly available. Subsequently, during the simulated annealing
procedure of Harmony Theory, maximal constraint satisfaction is accomplished
in parallel and an optimal solution of the $n$-Queens problem is
produced. This solution indicates the appropriate locations of the
greatest possible number of Queens that can be placed on the $n\times{}n$
chessboard in a valid configuration, i.e., so that no Queen
threatens or is threatened by another Queen. The proposed parallel
implementation of the $n$-Queens problem, combined with the application
of the simulated annealing procedure, offers an interesting alternative
to existing techniques (e.g., search, constraint propagation) in
terms of optimality as well as computational and time efficiency.}
}
@TECHREPORT{Tanaka2002,
author = {I. Tanaka and Y. Nishio and M. Hasegawa},
title = {An Approach to Finding All Solutions of $n$-Queens Problem Using
Chaos Neural Network},
institution = {IEIC, Institute of Electronics, Information and Communication Engineers},
year = {2002}
}
@PHDTHESIS{Tanik1978,
author = {M.M. Tanik},
title = {A Graph Model for Deadlock Prevention},
school = {Texas A\&M University},
year = {1978}
}
@INPROCEEDINGS{Tarry1897a,
author = {H. Tarry},
title = {Probl\`eme des $n$ Reines sur L\'echiquier de $n^2$ Cases},
booktitle = {Compte rendu de l{'}{A}ssociation Fran\c{c}aise pour l{'}{A}vancement
des Sciences 26, Congr\`es de Saint Etienne},
year = {1897},
pages = {176}
}
@ARTICLE{Tarry1895,
author = {H. Tarry},
title = {Probl\`eme des Reines (Probl\`eme 605)},
journal = {L{'}Interm\'ediaire des Math\'ematiciens Ser},
year = {1895},
volume = {12},
pages = {205}
}
@INBOOK{Taylor2003,
chapter = {Singly Periodic {C}ostas Arrays are Equivalent to Polygonal
Path {V}atican Squares},
title = {Mathematical Properties of Sequences and Other Combinatorial Structures},
publisher = {Kluwer Acad. Publ., Boston, MA},
year = {2003},
author = {H. Taylor}
}
@ARTICLE{Taylor1991,
author = {H. Taylor},
title = {Florentine Rows or Left-Right Shifted Permutation Matrices with Cross-correlation
Values $\leq 1$},
journal = {Discrete Mathematics},
year = {1991},
volume = {93},
pages = {247-260},
doi = {10.1016/0012-365X(91)90259-5},
abstract = {(1) Find $n\times{}n$ permutation matrices---as many as possible---whose aperiodic
horizontal shifting cross-correlation function takes only the values 0 or 1. (2) Find values of
$F(n)$ = the maximum number of Florentine rows on $n$ symbols. (3) It turns out that problem
(1) is isomorphic to problem (2), so that optimum constructions are available for (1)
whenever $n + 1$ is prime. Also on exhibit is S. Alquaddoomi's recent discovery that $F(8) = 7$.}
}
@ARTICLE{Thangavel2007,
author = {P. Thangavel and D. Gladisa},
title = {Hysteretic {H}opfield Network with Dynamic Tunneling for Crossbar Switch
and $n$-Queens Problem},
journal = {Neurocomputing},
year = {2007},
volume = {70},
pages = {2544-2551},
abstract = {An efficient hysteretic Hopfield network with dynamic tunneling is
proposed. The hysteretic activation function is used for training.
The dynamic tunneling approach is employed to detrap the network
from local minima. The network gives better convergence results for
the selected problems namely crossbar switch problem with exclusive
switching and concurrent switching, and $n$-Queens problem.},
doi = {10.1016/j.neucom.2006.06.006}
}
@ARTICLE{Theron2000,
author = {W.F.D. Theron and A.P. Burger},
title = {Queen Domination of Hexagonal Hives},
journal = {Journal of Combinatorial Mathematics and Combinatorial Computing},
year = {2000},
volume = {32},
pages = {161-172}
}
@ARTICLE{Theron1998,
author = {W.F.D. Theron and G. Geldenhuys},
title = {Domination by Queens on a Square Beehive},
journal = {Discrete Mathematics},
year = {1998},
volume = {178},
pages = {213-220},
doi = {10.1016/S0012-365X(97)81828-6},
abstract = {A chessboard-like game board consisting of hexagonal cells and a board piece
called a queen are defined. We determine bounds on the upper and lower domination and
independence numbers and on the diagonal domination number for queens on square hives
of any order.}
}
@ARTICLE{Tolpygo1996,
author = {A. Tolpygo},
title = {Follow-up: {Q}ueens on a Cylinder},
journal = {Quantum: {T}he Student Magazine of Math and Science},
year = {1996},
volume = {6},
pages = {38-42},
annote = {A treatment of nonstandard chessboards and chess pieces that builds
on earlier Quantum articles (V. Dubrovsky, ``Torangles and Torboards''
[March/April 1994] and A. Futer,
``Signals, Graphs, and Kings on a Torus'' [November/December 1995]).}
}
@ARTICLE{Topor1982,
author = {R.W. Topor},
title = {Fundamental Solutions of the Eight Queens Problem},
journal = {BIT Numerical Mathematics},
year = {1982},
volume = {22},
pages = {42-52},
doi = {10.1007/BF01934394},
abstract = {Previous algorithms presented to solve the eight queens problem have generated
the set of all solutions. Many of these solutions are identical after applying sequences
of rotations and reflections. In this paper we present a simple, clear, efficient algorithm
to generate a set of fundamental (or distinct) solutions to the problem.}
}
@ARTICLE{Undercoffer1987,
author = {K. Undercoffer},
title = {The Queens Problem Revisited},
journal = {Journal of Pascal, Ada \& Modula-2},
year = {1987},
volume = {6},
pages = {45-49},
refersto = {\cite{Wirth1976}},
url = {http://www.kirtundercoffer.com/publications/QueensProblemRevisited.html}
}
@BOOK{Vaderlind2002,
title = {The Inquisitive Problem Solver},
publisher = {Mathematical Association of America, Washington, DC},
year = {2002},
author = {P. Vaderlind and R.K. Guy and L.C. Larson},
series = {MAA Problem Books Series}
}
@ARTICLE{Valtorta1991,
author = {M. Valtorta},
title = {Correspondence: {R}esponse to ``Explicit Solutions to the ${N}$-Queens Problem for all ${N}$''},
journal = {ACM SIGART Bulletin},
year = {1991},
volume = {2},
pages = {4-5},
doi = {10.1145/122344.1063799},
refersto = {\cite{Abramson1989}, \cite{Bernhardsson1991}, \cite{Gu1991},
\cite{Sosic1990}, \cite{Sosic1991}}
}
@INCOLLECTION{Vardi1991,
author = {Vardi, I.},
title = {The $n$-Queens Problem},
booktitle = {Computational Recreations in Mathematica},
publisher = {Redwood City, CA: Addison-Wesley},
year = {1991},
chapter = {6},
pages = {107-125}
}
@ARTICLE{Vasquez2006,
author = {M. Vasquez},
title = {Coloration des Graphes de Reines},
journal = {Comptes Rendus de l'Acad\'emie des Sciences Paris, S\'erie I Math\'ematique},
year = {2006},
volume = {342},
pages = {157-160},
doi = {doi:10.1016/j.crma.2005.11.022},
abstract = {Until 2003 no chromatic numbers ($\chi_n$) for the queen graphs were available
for $n>9$ except where n is not a multiple of 2 or 3. In this research announcement we
present an exact algorithm which provides coloring solutions for
$n$=12,14,15,16,18,20,21,22,24,26,28 and 32 such as $\chi_n=n$. Then we prove that there
exists an infinite number of values for $n$ such that $n=2p$ or $n=3p$, and $\chi_n=n$.}
}
@ARTICLE{Vasquez2004,
author = {M. Vasquez},
title = {New Result on the Queens $n^2$ Graph Coloring Problem,},
journal = {Journal of Heuristics},
year = {2004},
volume = {10},
pages = {407-413},
doi = {10.1023/B:HEUR.0000034713.28244.e1},
abstract = {For the Queens $n^2$ graph coloring problems no chromatic numbers
are available for $n > 9$ except where $n$ is not a multiple of 2 or 3. In this
paper we propose an exact algorithm that takes advantage of the particular
structure of these graphs. The algorithm works on the independent sets of the
graph rather than on the vertices to be colored. It combines branch and bound,
for independent set assignment, with a clique based filtering procedure. A first
experimentation of this approach provided the coloring number values ranging for
$n = 10$ to $n = 14$.}
}
@INPROCEEDINGS{Vasquez2004a,
author = {M. Vasquez},
title = {On the Queen Graph Coloring Problem},
booktitle = {Proceedings of the 3rd International Conference on Information (INFO’04)},
year = {2004},
pages = {109–112}
}
@INPROCEEDINGS{Vasquez2004b,
author = {M. Vasquez and D. Habet},
title = {Complete and Incomplete Algorithms for the Queen Graph Coloring
Problem},
booktitle = {Proceedings of the 16th European Conference on Artiﬁcial Intelligence
(ECAI’04)},
year = {2004},
pages = {226–230},
url = {http://www.frontiersinai.com/ecai/ecai2004/ecai04/pdf/p0226.pdf},
abstract = {The queen graph coloring problem consists in covering
a $n\times{}n$ chessboard with $n^2$ queens, so that two queens of
the same color cannot attack each other. When the size, $n$, of the
chessboard is a multiple of 2 or 3, it is hard to color the queen
graph with only $n$ colors. We have developed an exact algorithm
which is able to solve exhaustively this problem for dimensions up
to $n = 12$ and find one solution for $n = 14$ in one week of
computing time. The 454 solutions of Queens 122 show horizontal
and vertical symmetries in the color repartition on the chessboard.
From this observation, we design a new exact, but incomplete, algorithm
which leads us to color Queens $n^2$ problems with $n$ colors
for $n$ = 15, 16, 18, 20, 21, 22, 24, 28 and 32 in less than 24 hours of
computing time by the exploitation of symmetries and other geometric
properties.}
}
@INPROCEEDINGS{Vasquez2004c,
author = {M. Vasquez and D. Habet},
title = {Algorithmes Complet et Incomplet pour la Coloration des Graphes de Reines},
booktitle = {Programmation en Logique avec Contraintes (JFPLC2004)},
year = {2004}
}
@MISC{Velucchi1998,
author = {M. Velucchi},
title = {For Me, This Is the Best Chess-Puzzle! {N}on-Dominating Queens Problem},
year = {1998},
url = {http://anduin.eldar.org/~problemi/papers.html}
}
@MISC{Velucchi1998a,
author = {M. Velucchi},
title = {Different Dispositions on the Chessboard},
year = {1998},
url = {http://anduin.eldar.org/~problemi/papers.html}
}
@ARTICLE{Wagner1984,
author = {R.A. Wagner and R.H. Geist},
title = {The Crippled Queen Placement Problem},
journal = {Science of Computer Programming},
year = {1984},
volume = {4},
pages = {221-248},
doi = {10.1016/0167-6423(84)90001-7},
abstract = {We describe the outcome of various combinations of choices made by individuals
in the solution of a non-trivial combinatorial problem on a computer. The programs which
result are analyzed with respect to execution speed, design time, and difficulty in debugging.
The solutions obtained vary dramatically as a result of choices made in the overall design
of the solution. Choices made at lower levels in the top-down tree of design choices seem to
have less effect on the parameters analyzed. A tradeoff between mathematical effort in algorithm
design, and program speed is evident, since some solutions required solution-time which
grows exponentially with the case size, while another solution presented here gives a
closed-form expression for the required answers for all large cases.}
}
@ARTICLE{Wang2004,
author = {C.-N. Wang and S.-W. Yang and C.-M. Liu and T. Chiang},
title = {A Hierarchical ${N}$-Queen Decimation Lattice and Hardware Architecture
for Motion Estimation},
journal = {IEEE Transactions on Circuits and Systems for Video Technology},
year = {2004},
volume = {14},
pages = {429-440},
doi = {10.1109/TCSVT.2004.825550},
abstract = {A subsampling structure, an $N$-Queen lattice, for spatially decimating
a block of pixels is presented. Despite its use for many applications, we demonstrate that the
$N$-Queen lattice can be used to speed up motion estimation with nominal loss of coding
efficiency. With a simple construction, the $N$-Queen lattice characterizes the spatial
features in the vertical, horizontal, and diagonal directions for both texture and edge areas.
Especially in the 4-Queen case, every skipped pixel has the minimal and equal distance of
unity to the selected pixel. It can be hierarchically organized for variable nonsquare
block-size motion estimation. Despite the randomized lattice, we design compact data storage
architecture for efficient memory access and simple hardware implementation. Our simulations
show that the $N$-Queen lattice is superior to several existing sampling techniques with
improvement in speed by about $N$ times and small loss in peak SNR (PSNR).
The loss in PSNR is negligible for slow-motion video sequences and is less than
0.45 dB at worst for high-motion estimation sequences.}
}
@ARTICLE{Wang2003,
author = {C.-N. Wang and S.-W. Yang and C.-M. Liu and T. Chiang},
title = {A Hierarchical Decimation Lattice Based on ${N}$-Queen with an Application
for Motion Estimation},
journal = {IEEE Signal Processing Letters},
year = {2003},
volume = {10},
pages = {228-231},
doi = {10.1109/LSP.2003.814403},
abstract = {We present a novel technique, $N$-queen lattice, to spatially subsample a
block of pixels. Although this lattice is pertinent to many applications, we present
an application to speed up motion estimation with minimal loss of coding efficiency.
The $N$-queen lattice is constructed to characterize spatial features in all directions.
It can be hierarchically organized for motion estimation with variable nonsquare block size.
Despite the randomized lattice structure, we demonstrate that it is possible to achieve
compact data storage architecture for efficient memory access and simple hardware implementation.
Our simulations show that the $N$-queen lattice is superior to several existing sampling
techniques with improvement in speed by about $N$ times and small loss in peak SNR.}
}
@BOOK{Watkins2004,
title = {Across the Board: The Mathematics of Chessboard Problems},
publisher = {Princeton, NJ: Princeton University Press},
year = {2004},
author = {J. Watkins}
}
@MISC{Wikipedia,
author = {Wikipedia},
title = {Eight Queens Puzzle},
year = {2009},
url = {http://en.wikipedia.org/wiki/Eight_queens_puzzle},
annote = {Website.}
}
@ARTICLE{Wirth1971,
author = {N. Wirth},
title = {Program Development by Stepwise Refinement},
journal = {Communications of the ACM},
year = {1971},
volume = {14},
pages = {221-227},
url = {http://doi.acm.org/10.1145/362575.362577},
abstract = {The creative art of programming---to be distinguished from coding---is usually
taught by examples serving to exhibit certain techniques. It is here considered as a sequence
of design decisions concerning the decomposition of tasks into subtasks
and of data into data structures. The process of successive refinement of specifications
is illustrated by a short but nontrivial example, from which a number of conclusions are
drawn regarding the art and the instruction of programming.}
}
@BOOK{Wirth1976,
title = {Algorithms + Data Structures = Programs},
publisher = {Prentice-Hall},
year = {1976},
author = {N. Wirth},
annote = {Several editions. Chapter 3.5: The Eight Queens Problem}
}
@ARTICLE{Wu1994,
author = {J.B. Wu},
title = {A Solution to the $n$-Queens Problem},
journal = {J. Huazhong Univ. Sci. Tech.},
year = {1994},
volume = {22},
pages = {195-198}
}
@BOOK{Yaglom1964,
title = {Challenging Mathematical Problems with Elementary Solutions; {V}olume 1: {C}ombinatorial Analysis and Probability Theory},
publisher = {Holden-Day, Inc.},
year = {1964},
author = {A.M. Yaglom and I.M. Yaglom},
annote = {Problem 41.
Originally published as Neelelementarnye Zadachi v Elementarnom Izlozhenii,
by the Government Printing House for Technical-Theoretical Literature, Moscow, 1954.
Later edition (1987) by Dover Publications, Inc.},
url = {http://www.liacs.nl/home/kosters/nqueens/papers/yaglom1964.pdf}
}
@ARTICLE{Yamamoto1984,
author = {K. Yamamoto and Y. Kitamura and H. Yoshikura},
title = {Computation of Statistical Secondary Structure of Nucleic Acids},
journal = {Nucleic Acids Research},
year = {1984},
volume = {12},
pages = {335-346},
doi = {10.1093/nar/12.1Part1.335},
abstract = {This paper presents a computer analysis of statistical secondary
structure of nucleic acids. For a given single stranded nucleic acid, we generated
``structure map" which included all the annealig structures in the sequence.
The map was transformed into ``energy map" by rough approximation; here, the energy
level of every pairing structure consisting of more than 2 successive nucleic
acid pairs was calculated. By using the ``energy map", the probability of
occurrence of each annealed structure was computed, i.e., the structure was
computed statistically. The basis of computation was the 8-queen problem in
the chess game. The validity of our computer programme was checked by computing
tRNA structure which has been well established. Successful application of
this programme to small nuclear RNAs of various origins is demonstrated.}
}
@INPROCEEDINGS{Yang2001,
title = {Fast Motion Estimation Using ${N}$-Queen Pixel Decimation},
booktitle = {Advances in Multimedia Information Processing (PCM 2001)},
series = {Lecture Notes in Computer Science},
publisher = {Springer-Verlag, Berlin},
year = {2001},
author = {S.-W. Yang and C.-N. Wang and C.-M. Liu and T. Chiang},
volume = {2195},
pages = {126-133},
abstract = {We present a technique to improve the speed of block motion estimation
using only a subset of pixels from a block to evaluate the distortion
with minimal loss of coding efficiency. To select such a subset we
use a special sub-sampling structure, $N$-queen pattern. The $N$-queen
pattern can characterize the spatial information in the vertical,
horizontal and diagonal directions for both texture and edge features.
In the 4-queen case, it has a special property that every skipped
pixel has the minimal and equal distance of one to the selected pixel.
Despite of the randomized pattern, our technique has compact data
storage architecture. Our results show that the pixel decimation
of $N$-queen patterns improves the speed by about $N$ times with
small loss in {PSNR}. The loss in {PSNR} is negligible for slow motion
video sequence and has 0.45 dB loss in PSNR at worst for high motion
video sequence.},
doi = {10.1007/3-540-45453-5}
}
@ARTICLE{Yoshio1997,
author = {H. Yoshio and T. Baba and N. Funabiki and S. Nishikawa},
title = {Proposal of an ${N}$-Parallel Computation Method for a Neural Network
for the $n$-Queens Problem},
journal = {Electronics and Communications in Japan},
year = {1997},
volume = {80},
pages = {12-20}
}
@ARTICLE{Yuen1994,
author = {C.K. Yuen and M.D. Feng},
title = {Breadth-First Search in the Eight Queens Problem},
journal = {ACM SIGPLAN Notices},
year = {1994},
volume = {29},
pages = {51-55},
doi = {10.1145/185009.185019},
abstract = {The Eight Queens Problem is used to illustrate some different
approaches to recursive programming and parallel processing.}
}
@ARTICLE{Zeng2007,
author = {C. Zeng and T. Gu},
title = {A Novel Assembly Evolutionary Algorithm for $n$-Queens Problem},
journal = {Computational Intelligence and Security Workshops},
year = {2007},
abstract = {Individuals in nowadays evolutionary algorithms for $n$-Queens
problem do not satisfy some basic constraint conditions. Motivated
by self-assembly computing, a novel assembly evolutionary algorithm
for $n$-Queens problem is presented. Each individual is made up
of assembly-parts, assembly-seeds and status information. Some important
notions and rules regarding the novel assembly evolutionary algorithm
are discussed. Experimental results show that the algorithm finds
a solution faster than other latest evolutionary algorithms.},
doi = {10.1109/CISW.2007.4425472}
}
@ARTICLE{Zhang2008,
author = {C. Zhang and J. Ma},
title = {Counting Solutions for the $n$-Queens and Latin Square Problems
by Efficient {M}onte {C}arlo Simulations},
journal = {Pysical Review E},
year = {2009},
volume = {79},
number = {016703},
abstract = {We apply Monte Carlo simulations to count the numbers of solutions
of two well-known combinatorial problems: the $n$-Queens problem
and Latin square problem. The original system is first converted
to a general thermodynamic system, from which the number of solutions
of the original system is obtained by using the method of computing
the partition function. Collective moves are used to further accelerate
sampling: swap moves are used in the $n$-Queens problem and a cluster
algorithm is developed for the Latin squares. The method can handle
systems of $10^4$ degrees of freedom with more than $10^{10000}$ solutions.
We also observe a distinct finite size effect of the Latin square
system: its heat capacity gradually develops a second maximum as
the size increases.},
doi = {10.1103/PhysRevE.79.016703}
}
@PHDTHESIS{Zhao1998,
author = {K. Zhao},
title = {The Combinatorics of Chessboards},
school = {City University of New York},
year = {1998}
}