Problem with Queens and Pawns
Antreas P. Hatzipolakis
xpolakis at otenet.gr
Thu Jun 1 18:32:41 CEST 2000
Joe Crump wrote:
>But I suppose you could devote an entire database by itself
>to 'Chess' sequences!
There is an ald Russian book devoted to combinatorial chess problems,
but I don't know if has been translated into English/French etc:
L. Y. Okunev: Combinatorial Problems on the Chessboard.
Moscow and Leningrand: ONTI, 1935
(cited by A. M. Yaglom and I. M. Yaglom: Challenging Mathematical Problems
with Elementary Solutions. Vol I, p. 12)
And a recent one (from Zbl):
Hedetniemi, Sandra M.; Hedetniemi, Stephen T.; Reynolds, Robert
Combinatorial problems on chessboards. II. (English)
[CA] Haynes, Teresa W. (ed.) et al., Domination in graphs. Advanced topics.
New York, NY: Marcel Dekker. Pure Appl. Math., Marcel Dekker. 209, 133-162
(1998). [ISBN 0-8247-0034-1/hbk]
This chapter presents an excellent survey (Survey II) of
domination-related problems on chessboards, updating the Survey I of {\it
G. H. Fricke} et al. [Combinatorial problems on chessboards: A brief survey,
Graph theory, combinatorics, and applications. Vol. 1, 507-528 (1995; Zbl
843.05061)], and introduces some new topics. Survey I discussed the 36
basic problems of determining (i) the irredundance number, $\text{ir}(G)$,
(ii) the domination number, $\gamma(G)$, (iii) the independent domination
number, $i(G)$, (iv) the independence number, $\beta(G)$, (v) the upper
domination number, $\Gamma(G)$, and (vi) the upper irredundance number,
$\text{IR}(G)$, for each of the six types of chessboard graphs $G$: (a) the
Queens graph, $Q\sb n$, (b) the Kings graph, $K\sb n$, (c) the Rooks graph,
$R\sb n$, (d) the Bishops graph, $B\sb n$, (e) the Knights graph, $N\sb n$,
and (f) the Grid graph, $G\sb n$. Survey II lists several notable
improvements to the results mentioned in Survey I and presents the first
10 or so values of many of the domination-related parameters, some of
which have recently been determined by exhaustive search. The listing of a
selection of optimal configurations for some small parameter values is
helpful in giving the reader some insights into these problems. Survey II
includes a comprehensive summary of the $N$-queens problems, one of the
most studied of all chessboard problems with approximately 100
literature citations. Other problems discussed include: (1) determining the
minimum number of queens which when placed on a single diagonal, or on a
single column, will suffice to dominate every square on an order-$n$
chessboard; (2) determining placements of queens so as to dominate the
fewest possible squares; (3) domination on variant chessboards, such as
triangulated boards; (4) total domination problems, where every piece as
well as every square must be attacked by another piece; (5) the design of
algorithms for weighted Rooks graphs; and (6) determining the greatest
number of queens that can be placed on an order-$n$ board under the
condition that each queen attacks precisely $k$ others. Survey I listed
approximately 50 open problems, many of which remain open. Survey II
concludes with some which the authors consider to be the most interesting
and challenging.
[ P.Gibbons (Auckland) ]
Antreas
More information about the SeqFan
mailing list