BISHOP DOMINATION ON AN M x N
CHESSBOARD
by
Paul G. Thalos
B.S., University of Colorado at Denver, 1994
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Computer Science
1999
ACKNOWLEDGEMENT
Professor Fisher has willingly lent his expertise and guidance in a caring and
supportive manner to which I am most grateful and give most acknowlegement
for without reservation. I would also like to recognize Professor Fisher, Pro
fessor Wolfe and Professor McConnell for their patience with me, and support
in allowance of any extra time that I needed due to family ilness and other
commitments to complete this thesis. For all thier support I give my complete
thanks.
This thesis for the Master of Science
degree by
Paul G. Thalos
has been approved
by
David C. Fisher
William Wolfe
Ross McConnell
Date
Thalos, Paul (M.S., Computer Science)
Bishops Dominating Number on a M x N Chessboard
Thesis directed by Associate Professor David C. Fisher
ABSTRACT
In the game of Chess, a Bishop attacks diagonally any number of squares. A
set of Bishops dominate an m by n chessboard if for every square there is
either a Bishop on it or a Bishop attacking it. What is the minimum number
of Bishops that are necessary to dominate a m by n chessboard? This thesis
will make a conjecture (which will be partially proven) for the answer to this
question.
When m = ik I have a new proof for a result that m Bishops are
required to dominate the Chessboard fully given first by Yaglom and Yaglom.
When m < n < 2m, I find a similar result that the total number of Bishops
required is 2 ^j. When n > 2m, I give a domination with 2 Bishops,
and conjecture that this is the minimum number. This conjecture is verified
when m = 2 and m = 3. It is also verified when n = 2m + 1, 2m + 2, 2m + 3,
2m + 4 and 2m + 5. Further, an Integer Programming formulation failed to
find a counterexample for values of m < 9 and values of n < 110.
Signed _________________
David C. Fisher
IV
CONTENTS
Chapter
Figures........................................................ vi
1. Bishop Domination............................................... 1
2. Square Chessboards, where 1
3. mxn Chessboards, where 1 < m < n < 2m .......................... 7
4. A Conjecture for m x n Chessboards, when n > 2m >2.............. 9
5. The Conjecture is True when n = 2m + i for i < 5 15
6. The Conjecture is True for all 2 x n and 3 x n Chessboards .... 19
7. Integer Programing Results .................................... 27
References..................................................... 33
v
1
2
5
6
7
10
11
12
13
14
19
21
22
23
24
25
26
32
FIGURES
Diagonal labeling for an 8x8 Chessboard.....................
Antidiagonal labeling for an 8x8 Chessboard.................
Here 8 Bishops dominate an 8x8 Chessboard...................
Here 8 Bishops dominate an 8x8 Chessboard...................
Here we have ^(B^j) = 6 and ^(B^g) = 8......................
Positions of White Bishops in my Domination Pattern. . .
Positions of Black Bishops in my Domination Pattern.........
An optimal configuration for the white colored squares and
large n.....................................................
Remainder Configuration for White Bishops...................
Remainder Configuration for Black Bishops...................
Dominations for all 2 x n Chessboards.......................
For all B3jTl where (l,n) is black..........................
For all B3jTl where (1, n) is black, j(B3tn) > 7(I?3,n2) + 1.
For all B3jTl where (l,n) is black, t(B3jn) > t(B3,ne) + 2. .
For all B3jTl where (l,n) is white..........................
For all B3jTI and (l,n) is white, 7(B3>n) > 7(B3>n3) + 1. . .
Another form where (1, n) is white, j(B3j11^5) > j(B3j11) + 2. .
LINDO results for white Bishops j(B5jiq)....................
vi
1.
Bishop Domination
Dg D10 Dll D\2 D13 D14 D15
Figure 1.1. Diagonal labeling for an 8x8 Chessboard.
The 8x8 Chessboard has been often been the stage to much mathe
matical thought. A conventional game involves two players, where each player
has a Queen and a King and two Kooks, two Knights and two Bishops. I am
primarily concerned with the Bishops alone, and this paper concerns having
any number of Bishops. Given that a Chessboard is a two dimensional array
of squares in rows and columns, a single Bishop moves diagonally across them.
Given also if a Chessboard is colored with two distinct colors as a Checker
board, a Bishop moves on a single color alone. The domination, or attacking
every square of this Chessboard by various chess pieces has been a topic of
1
some interest, and doing so with the use of minimal number of pieces of con
siderable interest.
I now formally define our problem. A set of Bishops dominate
an m by n chessboard if for every square there is either a Bishop on it or
a Bishop attacking it. What is the minimum number of Bishops that are
necessary to dominate a m by n chessboard? Figure 1.1 and Figure 1.2 show
a domination of the 8x8 Chessboard using 8 Bishops in a centermost row.
Yaglom and Yaglom [3] first showed that Bishop domination for a general
Ai
d2
A3
A4
M
Ai
= =
A j 1 j 1 ik 1
== ==
Figure 1.2. Antidiagonal la,hading for an 8x8 Chessboard.
square rrixm Chessboard cannot be accomplished with fewer than m Bishops.
Cockayne, Gamble and Shepard [1] also independently show these results as
well as independent dominations for square Chessboards. We will also extend
2
these results to rectangular Chessboards. We simplify our problem by assuming
that m < n, because the Bishops domination problem for a m by n chessboard
is equivalent to the problems of n by m chessboard. Through further analysis,
we have decomposed the rest of the problem into three different cases. The first
case discusses the issues when the rows m are equal to the number of columns
n. The second cases main topic is about when m < n < 2m, and the third
case discusses the issues for when n > 2m.
3
The following are a few definitions that were used throughout to help
clarify and simplify our problem.
Let Bmn be the graph with nodes VmjJl, such that
Kn, = {(l,l), (1,2), (1, n),..., (m, 1), (m, 2), (m,n)} .
The edge set is a function of nm nodes, where if given two nodes (i,j)
and (k, l) have an edge between them, then \k i\ = \j l\ ^ 0.
We also note that since Bnhn is isomorphic to Bnjm, then without loss of gen
erality we will assume throughout that m
The following are several subsets of Vnhn :
(1) The i row is: U, = {(/. I). (i, 2), ..., (i,n)}.
(2) The j column is: Cj = {(1, j), (2 ,j), ..., (m,j)}.
(3) The p diagonal is: Dp = (i,i) Â£ Vm^n \ p = m + j
(4) The p^ antidiagonal is denoted as Ap = (i,i) Â£ Vm^n \ p = j+ i l}.
(5) The set of white and black squares (denoted respectively as W and Â£)
are a subset of squares that have size and size such that
each set is denoted as
W={ (i,j)  % + j is even
Â£ = { {hi) % + j is oddj
4
2. Square Chessboards, where 1 < m = n
Yaglom and Yaglom [3] show that m Bishops are required to dominate
all Chessboards with m rows and m columns. Cockayne, Gamble and Shepard
[1] show that the independent domination number for the Bishops in square
Chessboards is no more than the domination number. Here we will give a little
different proof.
Dg D10 Dn D12 D13 Du Du
Figure 2.1. Here 8 Bishops dominate an 8x8 Chessboard.
Theorem 1 For all m > 1, we have 7= m.
5
Figure 2.2. Here 8 Bishops dominate an 8x8 Chessboard.
Proof: We can dominate Bm_m with m Bishops in row [y] (see Fig.2.2 and
Fig. 2.1 ). So 7< m.
Suppose we can dominate Bm;Tn with less than m Bishops. Let a
diagonal be large if it contains at least [y] squares. Since there are at least
m large diagonals, at least one of these diagonals must be bishopless. So to
attack the squares of this large diagonal, we need at least [y] Bishops attack
these squares via antidiagonals of the same color as the large diagonal. Thus
there are fewer than m\ y] = [y J Bishops of the other color, leaving a large
diagonal of this other color to be bishopless. Since the squares corresponding
to this diagonal cannot be covered with less than [y] Bishops in corresponding
antidiagonals, we have a contradiction. Therefore 7(5m,m) = m.
6
3. mxn Chessboards, where 1 < m < n < 2m
In this section, we will be the first to prove in a domination of Bnhn,
where 1 < m < n < 2m that at least [f J Bishops of each color are needed.
D3
d2
Dr
Figure 3.1. Here we have '(Bu) = 6 and (B\.x) = 8.
Theorem 2 For all 1 < m < n < 2m, we have j(Bmjn) = 2[J
Proof: For any 1 < m < n < 2m, we can dominate Bm^n with 2 jj Bishops,
in squares ([^J 1,2), ([fj,2), ([^J 1,4), (LfJ,4), ..., ([f J 1, 2[f J),
(LfJ,2LfJ) ( Fig 3.1 shows these dominations for B^7 and B4j8). Therefore
< 2[J
To show j(Bm,n) = 2[J, we suppose a domination exists with fewer
than LfJ Bishops for some color, say white. Since ^j < m, every white di
agonal whose size is at least m must have a Bishop in it, otherwise we cannot
attack every one of their squares via antidiagonals. Let us choose p < m to
7
be the largest integer, such that Dp is bishopless. Then p exists otherwise all
white diagonals of Dk with 1 < k < n would have a Bishop, and since there are
less than ^f j white Bishops then this is impossible. Let us also choose q > n
to be smallest integer, such that Dq is also bishopless and is of the same color
as Dp. One can show that q exists for a similiar reason as p. Since there are
2=2 1 white diagonals between Dp and Dq, then we must assume 2=Â£ 1 <
LfJ 1, and assume q ^ p < 2 [f j
How many Bishops are needed to dominate the squares of antidiago
nals p and q? Diagonalp includes all squares between (mp + 1,1) and (m,p).
Diagonal q includes all squares between (1, q m + 1) and (n + m q, n). We
know that one end of Dp is in Am_p+i and the other end is in Am+P_ i, and
one end of Dq is in Aq^m+1 and the other end is in Ajn+mqi Since [f J <
m, then q p < 2[J < 2m, so (q m + 1) (p + m 1) < 2. Thus, the
antidiagonals that cover Dp are contiguous with the antidiagonals that cover
Dq (there may be overlap between these two sets of antidiagonals, but there is
no gap).
So the total number of antidiagonals can be found as the difference
between these antidiagonals on each side as needed to cover both Dp and Dq is
(2n+mgi)(mp+i) 2 nq+p n qjq_ > n [f J > LfJ Since there are less
than LfJ white Bishops, then we have a contradiction. The proof is similar for
the black squares. Therefore, = 2[fJ.n
8
4. A Conjecture for m x n Chessboards, when
n > 2m > 2
We will introduce this section by proving a theorem that is an upper
bound for all 2m < n and conjecture that this is also the lower bound. We
first will give a domination that for each of the separate colors combined for
all values of m and values of n. We will later go and begin a proof by complete
induction on m for all n.
Theorem 3 For n > 2m > 2, we have 7{Bm^n) < 2[m^!1\
Proof: The following sets describe a domination by placement of Bishops.
We first note that any square (i,j) can be attacked one of three ways. These
are to directly have a Bishop on the square, or to have a Bishop attack it via
antidiagonal Ai+j_i attack it or to have a Bishop in diagonal Dm+j_i. The
following two sets describe domination locations for Bishops, where we these
sets are not necessarily unique. The first set describes the behavior observed
for the white colored squares, and the second set describes the pattern for the
black squares in a possible domination.
9
(2,2),
(1,5), (1,7), (1,2m+ 1),
(m, 3m + 2), (m, 3m + 4), . (in, 5m 2),
(1,6m 1), (1,6m+ 1), (1,8m5),
(to, 9m 4), (in, 9m 2), . (in, 11 m 8),
(1,12m 7), (1,12m5), (1,14m 11),
(m, 15m 10), (m, 15m 8), . (m, 17m 14)
(1, 18m 13), (1,18m11), (1,20m17),
(to, 21m 16), (m, 21m 14), . (in, 23m 20),
(1, 6(m l)k + 5), (1,6(m l)k + 3), ..., (1,6(m l)k + 2 m + 1),
k (m, 6(m 1 )k + 3m + 2), (m, 6(m 1 )k + 3m + 4), .. (m, 6(m 1 )k + 5m 2), ^
Figure 4.1. Positions of White Bishops in my Domination Pattern.
For this first subset, have shown groupings of subsets of the bish
ops in row 1 and row m. We can note that the white Bishops start off in a
nonconforming manner attacking diagonal Dm and antidiagonal A2, and have
a maintained pattern for the Bishops at every 2m 4 columns. The ending
columns must then be handled with placement of Bishops off the pattern for
sizes of chessboards that are not in full subsets.
10
This second set describes the configuration Bishops for the black
squares, it can be easily noted that we do not start the set with a square
that is not on the border.
/ (1,2), (1,4), (1,2m 2),
(ra, 3to 1), (l,3m + l), ..., (m, 5ra 5),
(1,6m 4) (1,6m2) ..., (1,8m 8),
(ra, 9ra 7). (1,9m 5) ..., (m, lira 11),
(1,12m 10), (1,12m8), ..., (1,14m 14),
(m, 15m 13), (m, 15m 11), ..., (m, 17m 17),
(1,18m 16), (1,18m14), ..., (1,20m 20),
(ra, 21ra 19), (ra, 21ra IT), .. , (to, 23to 23),
(1,6(m l)fc + 2), (1,6(m l)fc + 4), (1,6(ra 1 )k + 2ra 2),
(ra,6(ra l)k + 3ra 1), (to, 6(to L)k + 3ra + 1), .. , (to, 6(to 1 )k + 5ra 5), .
Figure 4.2. Positions of Black Bishops in my Domination Pattern.
11
This next picture actually displays and example of the combined white
and black bishop in the the domination pattern for the white square B5jH. This
domination is typical for all chessboards, and one can note that for every square
it either has a Bishop on it or is attacked by a Bishop. We basically have groups
of m 1 bishops on squares of the top and bottom rows.
A A A A A A A A = = = = = = A A A A A A A A = = = = = = A A A A
A A A A A A A A = = = = = = A A A A A A A A = = =
Figure 4.3. An optimal configuration for the white colored
squares and large n.
12
We now show that for Chessboards with sizes of n not equal to the
sizes given in our pattern, I now present a configuration of Bishops that concurs
with our domination number and we call it a remainder theorem to represent
the remainder of the Chessboard. This pattern is represented by the following
figures.
x
9 n n n n n X
b2 b2 X =
Ih Ih Ih x =
B4 B4 b4 X =
Ih ih Ih Ih Ih
Figure 4.4. Remainder Configuration for White Bishops.
13
The remainder for the set of Bishops that lie on the black squares
start at a smaller column index than the Bishops that lie on the white squares.
Figure 4.5. Remainder Configuration for Black Bishops.
For any chessboard, a correlation must be made when m and n do
not lie on the bounds of the formula noting that there are 2w+2m~4 white
squares and 2w+2m~4 black squares on the boundary. The number of Bishops
can be found by noting that each Bishop independently attacks 3 squares on
^nmj Bjghopg.
the boundary, thus equating to  w+ 21
14
5. The Conjecture is True when n = 2m +1 for
Â£<5
For the cases of n = 2m+ 1, 2m+ 2, 2m+ 3, 2m+ 4 and 2m+ 5, I have
shown the conjecture true. The proof is similar to the one found in Chapter 3.
Theorem 4 For all m, f{Bm;im+i) = l{Bm;im+2) = 2m.
Proof: Suppose that we can use m 1 Bishops to dominate the squares for
a color, say white. Let n be the total number of columns in our chessboard,
and so n = 2m + 1 or n = 2m + 2. Let us first define i = n 2m, so i = 1 or
i = 2. As in Theorem 2, let us choose diagonals p and q to represent bishopless
diagonals with the properties that p is the largest integer less than m and q
is the smallest integer greater than 2m + i. So p exists otherwise all white
diagonals of Dk with 1 < k < 2m + i would have a Bishop, and since there are
less than m white Bishops then this is impossible. One can show that q exists
for a similiar reason as does p.
Since there are m white diagonals between Dp and Dq, then we will
assume ^ 1 < m 1 thus q p < 2m. We know that one end of Dp is in
Am_p+1 and the other end is in Ap+m_i, and one end of Dq is in Aq_m+i and the
15
other end is in A3m+2iq 1. Since qp< 2m, we have (q m +1) (p + m 1)
< 2. Thus, the antidiagonals that cover Dp are contiguous with the antidiago
nals that covers the squares cover Dq (there may be overlap between these two
sets of antidiagonals, but there is no gap). Therefore the total number of
antidiagonals that pass through the squares of Dp and Dq is found as the dif
ference between these antidiagonals on each side, as given (2w+m=
= n T/ > 2m + Â£^m = m + Â£ > m. Since we assumed there are only m 1
white Bishops, then we have a contradiction. The proof is similar for the black
squares. Therefore for Â£ = 1,2, we have 7(5mj2m+.g) = 2m.
Theorem 5 For all m, we have 7(Bmj2m+3) = l{Bm;im+i) = 7(Bmj2m+5) =
2(m + 1)
Proof: We always have at least m + 2 total diagonals with m squares, where
there are "yj + 2 white diagonals with m squares and ^J + 2 black diago
nals with m squares, and thus there cannot be two of these diagonals of each
color bishopless. Now we consider three cases for Bishops of a color, and let
Â£ = 3,4,5.
Case 1: No diagonal containing m squares is bishopless:
For any n, we can dominate with 2 Bishops, (Figure 4.1 and Figure
4.2 show these dominations for general chessboards Bn^m). Therefore 7(5m,n)
< 2 [2m+3f+mj = 2 [Mj = 2 [m + [j] < 2 [m + [Â§J] = 2(m + 1) .
To show j(Bm,n) = 2(m + 1), suppose a domination exists with at
16
most m Bishops for some color, say white. Let us choose p < m to be the
largest integer, such that Dp is bishopless. Then p exists otherwise all white
diagonals of Dk with 1 < k < 2m + i would have a Bishop, and since there
are at most m white Bishops then this is impossible. Let us also choose q > n
to be smallest integer, such that Dq is also bishopless and is of the same color
as Dp. One can show that q exists for a similiar reason as p. Since there are
2=2 1 white diagonals between. Dp and Dq, then we must assume 2=Â£ 1 <
m, hence q p < 2(m + 1).
How many Bishops are needed to dominate the squares of antidiago
nals p and q? Diagonalp includes all squares between (mp + 1,1) and (m,p).
Diagonal q includes all squares between (1, q m + 1) and (n + m q, n). We
know that one end of Dp is in Am_p+i and the other end is in Am+P_ i, and one
end of Dq is in Aq^m+1 and the other end is in A2(2m+i)+mqi Either q p
< 2(m + 1) implies that (q m + 1) (p + m 1) < 2, or q p < 2(m + 1)
implies that (q m + 1) (p + m 1) <4.
If qp < 2(m+ 1) implies that (q ^m +1) (p + m^ 1) < 2, and the
antidiagonals that cover Di are contiguous with the antidiagonals that cover
Dj (there may be overlap between these two sets of antidiagonals, but there is
no gap), where (q p) 2m + 2 < 2m 2m + 2 = 2. So the total number
of antidiagonals can be found as the difference between these antidiagonals
on each side as needed to cover both Dp and Dq is (2(2m+^)+m~9~1)(p+1) _
2(2m+i)2(qp) =2m + Â£^i^2xÂ£< 2m + i 1 ^ii = 2m + Â£^l^(m + l)
= m + Â£ ^ 2 > m + 1 Since t > 3 and there are at most m white Bishops, then
17
we have a contracdiction. The proof is similar for the black squares. Therefore,
7 (Bm,n) =
Otherwise q^p < 2(m + 1) implies that (q m +1) (p + m 1) <4
and the antidiagonals have a gap, where (q p)^2m + 2 < (2m+ 2) ^2m + 2
= 4. So the total number of antidiagonals can be found as the difference be
tween these antidiagonals on each side as needed to cover both Dp and Dq is
(2(2to+1)+toq1) (top+1) 2{2m+t)2{qp)+2 2m + Â£ fcP < 2m + Â£ 2(m+1)
= 2m + Â£ ^ (m + 1) = m + Â£ ^ 1 >m + l Since ( > 3> and there are at most
m white Bishops, then we have a contracdiction. The proof is similar for the
black squares. Therefore, 7(I?mj) = 2(m + l).D
Case 2: One diagonal with m squares is bishopless: Let us label the
bishopless diagonal Dk, where m < k < n. Let Dk be some color, say white.
We know that k m, or we have no way to attack square (1,1). Similarly,
we cannot have k = n, but for square (n,m). Dk has squares that range
between (l,k m + 1) to (m,k + 1) for some k. A Bishop can only attack
one square of each Ak^m+1 to Ak+m+\. So the number of Bishops needed are
/c^m + l+ n + m^(/c + m+l)^n^m^2 = 2m + Â£ + m ^ 2 = m + Â£ ^ 2
> m + 1. Thus, for all m > 2 we are requiring more than m Bishops.
Case 3: More than one bishopless diagonal between Dp and Dq:
Since there are at least m + 1 squares that require Bishops from at least two
bishopless diagonals of size m, then my domination matches this number and
uses only m + 1 Bishops.
18
6. The Conjecture is True for all 2 x n and
3 x n Chessboards
We can note that the Bishops in this case are also independently dominating
upto three squares, and quite easily verify the conjecture.
m A m j m A m m A m m A m A m A
A = = A = A = A = A = A A
Figure 6.1. Dominations for all 2 x n Chessboards.
Theorem 6 When m = 2 and for all n, we have 7(_B2,n) = 2
Proof: Let Pn be defined as the set of disjoint paths of length n. Then B2,n
= Pn U Pn is disjoint union of all the paths of length n. It is well known that
7(P) = tf tl 7(B2,J = 7(P.UP.) = l(Pn) + l(Pn) = ifl + T = 2 hi'
Theorem 7 For all n, we have 7= 2 = 2 ^j + 2
Proof: This will be done via induction on n, and conjecture that this holds
true for all possible m. There are a total of four possible configurations of the
last six columns that the dominations fall into. These six columns repeat in
19
pattern and I begin with a basis of n = 4, 5, 6, 7, 8 and 9.
Applying Theorem 2 for n = 4, 5, we can state that the number of
Bishops required are 2 for a color. Also n = 6, we can apply Theorem 2, and
state that the number of Bishops required are 3 for a color. When we apply our
formula, we have ^
matches these results. Applying Theorem 4 for n = 7, 8, we can state that
the number of Bishop required are 3 for a color. When we apply our formula,
we have j
results. Applying Theorem 5 for n = 9, we can state that the number of Bish
ops required are 4 and applying our formula we have the number of Bishops
required is [j + lj =4 and is also the same result. So these values form a
basis for induction.
Now we can assume that for columns n > 9 that < 2 j + lj
holds true for 4 < k < n as the upper bound for the number of Bishops required
to dominate B3_k. I must show through two cases of the last six columns where
(1 ,n) is either a white or a black square that 'j(B^k) > 2 j + lj.
+ lj = 3 and 11 + lj = 3, and these formula also matches these
+ lj =2, 11 + lj =2 and 11 + lj = 3. So the formula
20
(l,n5) (l,n3) (l,n1)
(2,n4) (2,n2) (2 ,n)
(3,n5 (3,n3 (3,n1
(bl) (1,3)
(2,2)
(3,1) (3,3)
Figure 6.2. For all B3_n where (l,n) is black.
Case where square (l,n) is black: Let D be the set of Bishop squares
that dominates B^n. Square (2,n) must be dominated, and so a Bishop can
either be at square (2, n) or we need to have a Bishop at either of the squares
(1,n 1) or (3,n 1).
21
Figure 6.3. For all B3_n where (1, n) is black, 7(B3jn) > ry(B3jn_2) + 1.
Since we need to dominate square (2,n) then either a Bishop lies on
square (2, n) or there is a Bishop on either square (3, n 1) or square (1, n 1)
So assume square (2,n) is contained in D (see Figure 6.3), and we have used
one Bishop. Thus we have fully dominated two columns from B3,n and are left
with I?3jn2 to dominate. So our result is:
7(B,.n) > 7(B3.W + 1 > pij + 1 > [f J + 1.
If a Bishop is not at square (2,n), then we must have a Bishop at
sqaure (1 ,n 1) and square (3,n 1). So without loss of generality let us
assume square (1, n 1) is in D. So now we have dominated two columns from
B3jT1. So there must be a Bishop at either sqaure (3, n 1) or sqaure (2, n 3) or
square (1, n 4). Having a Bishop lie on square (1, n 4) dominates the same
squares as having the Bishop lie on the other squares and more. So assume
there is a second Bishop on square (1 ,n 4) (see Figure 6.4).
22
SL &
=
Figure 6.4. For all B3_n where (1, n) is black, 7(B3jn) > 7(_B3)n_6) + 2.
We can observe from Figure 6.4 that square (l,n 5) is not domi
nated by a Bishop. It is also possible to have square (3,n 5) not dominated
by a Bishop. So either an additional Bishop lies on square (1 ,n 5), square
(2,n 6) or on square (3,n 7). Since this Bishop is from I?3jn_6 and would
dominate more squares, let us assume that a Bishop lies on square (2,n 6),
which gives rise to the same domination result as given from the previous case.
So now we have used two Bishops to dominate a total of six columns with the
assumption of the domination of a square by a Bishop from I?3jn_6. So our
result is:
7(jB3,6) + 2 > 7{Bs,n) > 1 + [Vj +2 > [J + 1
23
(l,n4) (l,n2) (gn)
(2,n5) (2,n3) (2,n1)
(3,n4 (3,n2 (3,n)
(bl) (1,3)
(2,2)
(3,1) (3,3)
Figure 6.5. For all B3_n where (l,n) is white.
Case where square (l,n) is white. Let D be the set of Bishop squares that
dominates B3j, as we did when square (1, n) was black. Since a Bishop from D
must dominate square (l,n), then this Bishop must lie on either square (l,n),
square (2, n 1) or square (3, n 2). We can note that having square (2, n 1)
contained in D is also a domination of the same minimal size as having square
(1, n) contained in D. So either square (2, n 1) or square (3, 2) is contained
in D.
24
+ 1.
If square (1, n) is contained in D, then we know we get the same dom
ination of equal size as if square (2, n 1) or if square (3, 2) were contained
in D. So let us assume that square (1, n) is not in D. If square (2,n 1) is
contained in D, then we can note that this dominates all the white squares
of i?3j3 from B3jJ1. This reduces our problem by three columns, and if we let
k = n 3 we can refer to inductive hypothesis for B3jk. So our our result is:
7(B3J > 7+ 1 > 1 + 5*J +1. = tj +1.
25
Figure 6.7. Another form, where (1, n) is white,> 7(S3jn) +2.
In the last configuration, square (2, n 1) is now not in D and square
(3,n 2) is contained in D. We now note that we need to dominate square
(3, n). If we had a Bishop there, we would dominate the same squares as placing
a Bishop at square (2, n 1). We also can find that placing a Bishop at square
(1 ,n 2) also dominates the same squares as placing the Bishop at square
(2, n 1) and more squares. Since there are no other ways to dominate these
other squares, let us assume that the second Bishop lies on square (1 ,n 2)
(see Figure 6.7). Now we can note that our result is 7(B3jn) > 7(7?3,n5) + 2.
Having a Bishop lie on square (2, n 5) would only dominate that square, and
we would want to have the Bishop lie on either square (l,n 6) or square
(3,n 6). This Bishop is not part of the domination of B?tJ, So our result
is:
> 7(S3,5) + 2 > =f2j + 2 > pij + 1 > =J + 1.
26
7. Integer Programing Results
An alternate method to model this problem is using systems of linear inequali
ties for specific Chessboards. I wrote a c program to generate such inequalities
into specific text hies that contained the system of linear inequalities describ
ing diagonals and the squares that belong to each diagonal and antidiagonal
for each specific Chessboard, which were run through LINDO. I ran these pro
cesses in hopes of finding a counterexample to the conjecture at hand. I was
not able to find such a counter example, my results ran for values m < 9 with
respective values of n < 110.
Squares of the diagonals range from from the Northeast to the South
west, and squares of antidiagonals range from the Southeast to the Northwest.
I for the sake of the program, my variable names were Diag# and Antid# and
were numbered sequentially, and squares were rowcolumn coordinates, start
ing with r#c#. The summation of a diagonal and antidiagonal subtracting
a double counted square was an inequality valued as greater than or equal to
one. Diagonals minus the squares of the antidiagonal were valued as equal to
zero. Antidiagonals minus the squares of the diagonal were valued as equal to
zero.
We now give an sample of systems of linear inequalities that describe
27
the solution to the white squares for a B5yW. I also have displayed a sample
Chessboard with the solution obtained. The solution obtained is interesting
that it is similar to the upper bound domination I have given.
The Integer program that modeled the white squares is given as follows:
min
Diagl+Diag2+Diag3+Diag4+Diag5+Diag6+Diag7+Diag8+Diag9+Diagl0
st
Antid8rlclr2c2r3c3r4c4r5c5=0
Diaglrlcl=0
Diagl+Antid8rlcl>=l
Antidlrlc3r2c4r3c5r4c6r5c7=0
Diag2+Antidlrlc3>=l
Antid2rlc5r2c6r3c7r4c8r5c9=0
Diag3+Antid2rlc5>=l
Antid3rlc7r2c8r3c9r4cl0r5c11=0
Diag4+Antid3rlc7>=l
Antid4rlc9r2cl0r3cllr4cl2r5c13=0
Diag5+Antid4rlc9>=l
Antid5rlcllr2cl2r3cl3r4cl4r5c15=0
Diag6+Antid5rlcll>=l
Antid6rlcl3r2cl4r3cl5r4c16=0
Diag7+Antid6rlcl3>=l
Antid7rlcl5r2cl6=0
Diag8+Antid7rlcl5>=l
Diag2+Antid8r2c2>=l
Diag3+Antidlr2c4>=l
Diag4+Antid2r2c6>=l
Diag5+Antid3r2c8>=l
Diag6+Antid4r2cl0>=l
Diag7+Antid5r2cl2>=l
Diag8+Antid6r2cl4>=l
Diag9+Antid7r2cl6>=l
28
Antid9r3clr4c2r5c3=0
o o ii
II LO
o CO tH
ii tH U
o o O tH o tH
ii II II tH tH Sh
LO t' CD U Sh 1
O o O tH 1
tH tH tH P CN tH
P P P 1 tH o
1 1 1 o o CN
co 00 tH CN Sh
o o o o Sh 1
CN CN CN CN 1 CO
o tH P P P P tH tH
II tH tH tH tH tH tH ii 1 tH 1 1 1 tH o
CO tH tH tH tH tH ii ii ii tH tH tH tH ii ii ii A CO ii LO tH t' tH CD tH o tH CO
o ii ii ii ii ii A A A ii ii ii ii A A A co o A O ii o ii O ii CO ii Sh
tH A A A A A tH CO LO A A A A O CN tH CO tH CO A CO A CO A Sh A 1
Sh tH CO LO t' CD tH tH tH CN co 00 tH tH tH o P o P CO P LO P t' 1 CD CN
1 o o O O O o u o O O o o o o o 1 LO 1 o 1 O 1 O o O tH
CN CO CO CO CO CO CO CO CO P CN P LO co LO 00 LO tH LO o
O Sh P P P P P u P P P P P P P P 1 o O 1 o P o P o P o Sh
CN 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 co ii o 1 1 1 1 Sh
Sh CD 00 tH CN CO LO co CD 00 tH CN CO LO TJ tH P tH P CD P 00 P tH Sh CN 1
1 TJ TJ TJ TJ TJ T* TJ TJ TJ T* TJ TJ TJ TJ H o 1 1 TJ 1 TJ 1 T* 1 TJ tH
tH H H H H H H H H H H H H H H H P LO tH H CO H LO H t' H CD H tH
o P p P P p p P P P p P P p P P Pi P o P o P O P o P O P> o
CO Pi Pi Pi Pi Pi Pi Pi Pi Pi Pi Pi Pi 1 LO LO Pi LO Pi LO LO Pi LO
Sh <*s
1 + + + + + + + + + + + + + + + O tH 1 + 1 + 1 + 1 + 1 + 1
CN CN CO LO CO t' 00 CD CO LO CO t' 00 CD tH CO co LO LO co CD 00
bO bO bO bO bO bO bO bO bO bO bO bO bO bO bO bO bO H bO bO bO bO bO bO b0 bO bO bO bO
nJ nJ nJ cd nJ nJ nJ cd nJ nJ nJ cd nJ nJ nJ nJ cd P nJ cd nJ nJ nJ nJ nJ cd nJ nJ nJ
H H H H H H H H H H H H H H H H H H H H H H H H H H H H
Q Q Q Q Q Q Q Q n n n Q n n Q Q n <*s Q Q Q Q Q n n Q n n Q
Diag8+Antid3r5cll>=l
Diag9r5cl3r4cl4r3cl5r2cl6=0
Diag9+Antid4r5cl3>=l
Diagl0r5cl5r4cl6=0
Diagl0+Antid5r5cl5>=l
end
terse
gin
200
go
99999999
no
quit
30
The Bishop square locations produced by LINDO are given in the following set
as {R2C2, R5C3, R5C1, R1C9, RICH, RICH, R1C15}.
LINDO 5.3 (October 1994)
LINDO Systems, Chicago, IL
LDW83531000
University of Colorado
: : ? : LP OPTIMUM FOUND AT STEP 102
OBJECTIVE VALUE = 5.58333349
NEW INTEGER SOLUTION OF 7.00000000
AT BRANCH 5 PIVOT 352
BOUND ON OPTIMUM: 6.111111
ENUMERATION COMPLETE. BRANCHES= 5 PIV0TS=
LAST INTEGER SOLUTION IS THE BEST FOUND
REINSTALLING BEST SOLUTION...
99999999
OBJECTIVE FUNCTION VALUE
1) 7.000000
VARIABLE VALUE REDUCED COST
DIAG2 1.000000 1.000000
DIAG3 1.000000 1.000000
DIAG4 1.000000 1.000000
DIAG5 1.000000 1.000000
DIAG6 1.000000 1.000000
DIAG7 1.000000 1.000000
DIAG8 1.000000 1.000000
ANTID8 1.000000 0.000000
352
31
R2C2 1.000000 0.000000
ANTID4 1.000000 0.000000
R1C9 1.000000 0.000000
ANTID5 1.000000 0.000000
RICH 1.000000 0.000000
ANTID6 1.000000 0.000000
R1C13 1.000000 0.000000
ANTID7 1.000000 0.000000
R1C15 1.000000 0.000000
ANTID9 1.000000 0.000000
R5C3 1.000000 0.000000
ANTID10 1.000000 0.000000
R5C1 1.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
NO. ITERATIONS= 371
BRANCHES= 5 DETERM.= l.OOOE 0
Again, we see from this example alone that there is a tend for the
placement of the Bishops toward the top and bottom rows.
A A A A
A
A A
Figure 7.1. UNDO results for white Bishops 7(S5ji6).
32
REFERENCES
[1] E. J. Cockayne, B. Gamble and B. Shepherd, Chessboard Domination Prob
lems, Discrete Mathematics 86(1990)13 20
[2] G. H. Fricke, et. al. Combinatorial Problems on Chessboards:A Brief Sur
vey in Graph Theory, Combinatorics and Applications, Y. Alavi and A.
Schwenk, John Wiley and Sons, Inc., NY, 1995.
[3] A. M. Yaglom and I. M. Yaglom, Challenging Mathematical Problems with
Elementary Solutions,Dover Publications, Inc., NY, vl, 1964.
33

PAGE 1
BISHOP DOMINA TION ON AN M N CHESSBO ARD b y P aul G. Thalos B.S., Univ ersit y of Colorado at Den v er, 1994 A thesis submitted to the Univ ersit y of Colorado at Den v er in partial fulllmen t of the requiremen ts for the degree of Master of Science Computer Science 1999
PAGE 2
A CKNO WLEDGEMENT Professor Fisher has willingly len t his expertise and guidance in a caring and supportiv e manner to whic h I am most grateful and giv e most ac kno wlegemen t for without reserv ation. I w ould also lik e to recognize Professor Fisher, Professor W olfe and Professor McConnell for their patience with me, and support in allo w ance of an y extra time that I needed due to family ilness and other commitmen ts to complete this thesis. F or all thier support I giv e m y complete thanks.
PAGE 3
This thesis for the Master of Science degree b y P aul G. Thalos has been appro v ed b y Da vid C. Fisher William W olfe Ross McConnell Date
PAGE 4
Thalos, P aul (M.S., Computer Science) Bishop's Dominating Num ber on a M N Chessboard Thesis directed b y Associate Professor Da vid C. Fisher ABSTRA CT In the game of Chess, a Bishop attac ks diagonally an y n um ber of squares. A set of Bishops \dominate" an m b y n c hessboard if for ev ery square there is either a Bishop on it or a Bishop attac king it. What is the minim um n um ber of Bishops that are necessary to dominate a m b y n c hessboard? This thesis will mak e a conjecture (whic h will be partially pro v en) for the answ er to this question. When m = n I ha v e a new proof for a result that m Bishops are required to dominate the Chessboard fully giv en rst b y Y aglom and Y aglom. When m < n 2 m I nd a similar result that the total n um ber of Bishops required is 2 j n 2 k When n > 2 m I giv e a domination with 2 j n + m 3 k Bishops, and conjecture that this is the minim um n um ber. This conjecture is v eried when m = 2 and m = 3. It is also v eried when n = 2 m + 1, 2 m + 2, 2 m + 3, 2 m + 4 and 2 m + 5. F urther, an In teger Programming form ulation failed to nd a coun terexample for v alues of m 9 and v alues of n 110. Signed Da vid C. Fisher iv
PAGE 5
CONTENTS Chapter Figures . . . . . . . . . . . . . . . . . vi 1. Bishop Domination . . . . . . . . . . . . . 1 2. Square Chessboards, where 1 m = n . . . . . . . . 5 3. m n Chessboards, where 1 m < n 2 m . . . . . . 7 4. A Conjecture for m n Chessboards, when n > 2 m > 2 . . . 9 5. The Conjecture is T rue when n = 2 m + ` for ` 5 . . . . 15 6. The Conjecture is T rue for all 2 n and 3 n Chessboards . . 19 7. In teger Programing Results . . . . . . . . . . . 27 References . . . . . . . . . . . . . . . . . 33 v
PAGE 6
FIGURES Figures 1.1 Diagonal lab eling for an 8 8 Chessb o ar d. . . . . . 1 1.2 A ntidiagonal lab eling for an 8 8 Chessb o ar d. . . . . 2 2.1 Her e 8 Bishops dominate an 8 8 Chessb o ar d. . . . . 5 2.2 Her e 8 Bishops dominate an 8 8 Chessb o ar d. . . . . 6 3.1 Her e we have r ( B 4 ; 7 ) = 6 and r ( B 4 ; 8 ) = 8 . . . . . 7 4.1 Positions of White Bishops in my Domination Pattern. . 10 4.2 Positions of Black Bishops in my Domination Pattern. . . 11 4.3 A n optimal c ongur ation for the white c olor e d squar es and lar ge n . . . . . . . . . . . . . . . 12 4.4 R emainder Congur ation for White Bishops. . . . . 13 4.5 R emainder Congur ation for Black Bishops. . . . . 14 6.1 Dominations for all 2 n Chessb o ar ds. . . . . . . 19 6.2 F or all B 3 ;n wher e (1 ; n ) is black. . . . . . . . . 21 6.3 F or all B 3 ;n wher e (1 ; n ) is black, r ( B 3 ;n ) r ( B 3 ;n 2 ) + 1 . 22 6.4 F or all B 3 ;n wher e (1 ; n ) is black, r ( B 3 ;n ) r ( B 3 ;n 6 ) + 2 . 23 6.5 F or all B 3 ;n wher e (1 ; n ) is white. . . . . . . . . 24 6.6 F or all B 3 ;n and (1 ; n ) is white, r ( B 3 ;n ) r ( B 3 ;n 3 ) + 1 . . 25 6.7 A nother form wher e (1 ; n ) is white, r ( B 3 ;n 5 ) r ( B 3 ;n ) + 2 . 26 7.1 LINDO r esults for white Bishops r ( B 5 ; 16 ) . . . . . . 32 vi
PAGE 7
1. Bishop Domination D 8 D 7 D 6 D 5 D 4 D 3 D 2 D 1 @ @ @ R @ @ @ R @ @ @ R @ @ @ R @ @ @ R @ @ @ R @ @ @ R @ @ @ R D 9 D 10 D 11 D 12 D 13 D 14 D 15 @ @ @ R @ @ @ R @ @ @ R @ @ @ R @ @ @ R @ @ @ R @ @ @ R Figure 1.1. Diagonal lab eling for an 8 8 Chessb o ar d. The 8 8 Chessboard has been often been the stage to m uc h mathematical though t. A con v en tional game in v olv es t w o pla y ers, where eac h pla y er has a Queen and a King and t w o Rooks, t w o Knigh ts and t w o Bishops. I am primarily concerned with the Bishops alone, and this paper concerns ha ving an y n um ber of Bishops. Giv en that a Chessboard is a t w o dimensional arra y of squares in ro ws and columns, a single Bishop mo v es diagonally across them. Giv en also if a Chessboard is colored with t w o distinct colors as a Chec k erboard, a Bishop mo v es on a single color alone. The domination, or attac king ev ery square of this Chessboard b y v arious c hess pieces has been a topic of 1
PAGE 8
some in terest, and doing so with the use of minimal n um ber of pieces of considerable in terest. I no w formally dene our problem. A set of Bishops \dominate" an m b y n c hessboard if for ev ery square there is either a Bishop on it or a Bishop attac king it. What is the minim um n um ber of Bishops that are necessary to dominate a m b y n c hessboard? Figure 1.1 and Figure 1.2 sho w a domination of the 8 8 Chessboard using 8 Bishops in a cen termost ro w. Y aglom and Y aglom [3] rst sho w ed that Bishop domination for a general A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 A 9 A 10 A 11 A 12 A 13 A 14 A 15 Figure 1.2. A ntidiagonal lab eling for an 8 8 Chessb o ar d. square m m Chessboard cannot be accomplished with few er than m Bishops. Coc k a yne, Gam ble and Shepard [1] also independen tly sho w these results as w ell as independen t dominations for square Chessboards. W e will also extend 2
PAGE 9
these results to rectangular Chessboards. W e simplify our problem b y assuming that m n because the Bishops domination problem for a m b y n c hessboard is equiv alen t to the problems of n b y m c hessboard. Through further analysis, w e ha v e decomposed the rest of the problem in to three dieren t cases. The rst case discusses the issues when the ro ws m are equal to the n um ber of columns n The second case's main topic is about when m < n 2 m and the third case discusses the issues for when n > 2 m 3
PAGE 10
The follo wing are a few denitions that w ere used throughout to help clarify and simplify our problem. Let B m;n be the graph with nodes V m;n suc h that V m;n = f (1 ; 1) ; (1 ; 2) ; : : :; (1 ; n ) ; : : :; ( m; 1) ; ( m; 2) ; : : :; ( m; n ) g : The edge set E m;n is a function of mn nodes, where if giv en t w o nodes ( i; j ) and ( k; l ) ha v e an edge bet w een them, then j k i j = j j l j 6 = 0. W e also note that since B m;n is isomorphic to B n;m then without loss of generalit y w e will assume throughout that m n The follo wing are sev eral subsets of V m;n : (1) The i th ro w is: R i = f ( i; 1) ; ( i; 2) ; : : :; ( i; n ) g (2) The j th column is: C j = f (1 ; j ) ; (2 ; j ) ; : : :; ( m; j ) g (3) The p th diagonal is: D p = n ( i; j ) 2 V m;n j p = m + j i o (4) The p th an tidiagonal is denoted as A p = n ( i; j ) 2 V m;n j p = j + i 1 o (5) The set of white and blac k squares (denoted respectiv ely as W and L ) are a subset of squares that ha v e size d mn 2 e and size b mn 2 c suc h that eac h set is denoted as W = n ( i; j ) j i + j is ev en o L = n ( i; j ) j i + j is odd o 4
PAGE 11
2. Square Chessboards, where 1 m = n Y aglom and Y aglom [3] sho w that m Bishops are required to dominate all Chessboards with m ro ws and m columns. Coc k a yne, Gam ble and Shepard [1] sho w that the independen t domination n um ber for the Bishops in square Chessboards is no more than the domination n um ber. Here w e will giv e a little dieren t proof. D 8 D 7 D 6 D 5 D 4 D 3 D 2 D 1 @ @ @ R @ @ @ R @ @ @ R @ @ @ R @ @ @ R @ @ @ R @ @ @ R @ @ @ R D 9 D 10 D 11 D 12 D 13 D 14 D 15 @ @ @ R @ @ @ R @ @ @ R @ @ @ R @ @ @ R @ @ @ R @ @ @ R Figure 2.1. Her e 8 Bishops dominate an 8 8 Chessb o ar d. Theorem 1 F or all m 1 we have r ( B m;m ) = m 5
PAGE 12
A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 A 9 A 10 A 11 A 12 A 13 A 14 A 15 Figure 2.2. Her e 8 Bishops dominate an 8 8 Chessb o ar d. Proof: W e can dominate B m;m with m Bishops in ro w d m 2 e (see Fig.2.2 and Fig. 2.1 ). So r ( B m;m ) m Suppose w e can dominate B m;m with less than m Bishops. Let a diagonal be \large" if it con tains at least d m 2 e squares. Since there are at least m large diagonals, at least one of these diagonals m ust be bishopless. So to attac k the squares of this large diagonal, w e need at least d m 2 e Bishops attac k these squares via an tidiagonals of the same color as the large diagonal. Th us there are few er than m d m 2 e = b m 2 c Bishops of the other color, lea ving a large diagonal of this other color to be bishopless. Since the squares corresponding to this diagonal cannot be co v ered with less than d m 2 e Bishops in corresponding an tidiagonals, w e ha v e a con tradiction. Therefore r ( B m;m ) = m 2 6
PAGE 13
3. m n Chessboards, where 1 m < n 2 m In this section, w e will be the rst to pro v e in a domination of B m;n where 1 m < n 2 m that at least b n 2 c Bishops of eac h color are needed. D 4 D 3 D 2 D 1 @ @ @ R @ @ @ R @ @ @ R @ @ @ R D 5 D 6 D 7 D 8 D 9 D 10 @ @ @ R @ @ @ R @ @ @ R @ @ @ R @ @ @ R @ @ @ R D 4 D 3 D 2 D 1 @ @ @ R @ @ @ R @ @ @ R @ @ @ R D 5 D 6 D 7 D 8 D 9 D 10 D 11 @ @ @ R @ @ @ R @ @ @ R @ @ @ R @ @ @ R @ @ @ R @ @ @ R Figure 3.1. Her e we have r ( B 4 ; 7 ) = 6 and r ( B 4 ; 8 ) = 8 Theorem 2 F or all 1 m < n 2 m we have r ( B m;n ) = 2 b n 2 c Proof: F or an y 1 m < n 2 m w e can dominate B m;n with 2 j n 2 k Bishops, in squares ( b m 2 c 1 ; 2) ; ( b m 2 c ; 2) ; ( b m 2 c 1 ; 4) ; ( b m 2 c ; 4) ; : : :; ( b m 2 c 1 ; 2 b n 2 c ) ; ( b m 2 c ; 2 b n 2 c ) ( Fig. 3.1 sho ws these dominations for B 4 ; 7 and B 4 ; 8 ). Therefore r ( B m;n ) 2 b n 2 c T o sho w r ( B m;n ) = 2 b n 2 c w e suppose a domination exists with few er than b n 2 c Bishops for some color, sa y white. Since j n 2 k m ev ery white diagonal whose size is at least m m ust ha v e a Bishop in it, otherwise w e cannot attac k ev ery one of their squares via an tidiagonals. Let us c hoose p < m to 7
PAGE 14
be the largest in teger, suc h that D p is bishopless. Then p exists otherwise all white diagonals of D k with 1 k n w ould ha v e a Bishop, and since there are less than j n 2 k white Bishops then this is impossible. Let us also c hoose q > n to be smallest in teger, suc h that D q is also bishopless and is of the same color as D p One can sho w that q exists for a similiar reason as p Since there are q p 2 1 white diagonals bet w een D p and D q then w e m ust assume q p 2 1 b n 2 c 1, and assume q p 2 j n 2 k How many Bishops ar e ne e de d to dominate the squar es of antidiagonals p and q ? Diagonal p includes all squares bet w een ( m p +1 ; 1) and ( m; p ). Diagonal q includes all squares bet w een (1 ; q m + 1) and ( n + m q; n ). W e kno w that one end of D p is in A m p +1 and the other end is in A m + p 1 and one end of D q is in A q m +1 and the other end is in A 2 n + m q 1 Since b n 2 c m then q p 2 b n 2 c 2 m so ( q m + 1) ( p + m 1) 2. Th us, the an tidiagonals that co v er D p are con tiguous with the an tidiagonals that co v er D q (there ma y be o v erlap bet w een these t w o sets of an tidiagonals, but there is no \gap"). So the total n um ber of an tidiagonals can be found as the dierence bet w een these an tidiagonals on eac h side as needed to co v er both D p and D q is (2 n + m q 1) ( m p +1) 2 = 2 n q + p 2 = n q p 2 n b n 2 c b n 2 c Since there are less than b n 2 c white Bishops, then w e ha v e a con tradiction. The proof is similar for the blac k squares. Therefore, r ( B m;n ) = 2 b n 2 c 2 8
PAGE 15
4. A Conjecture for m n Chessboards, when n > 2 m > 2 W e will in troduce this section b y pro ving a theorem that is an upper bound for all 2 m < n and conjecture that this is also the lo w er bound. W e rst will giv e a domination that for eac h of the separate colors com bined for all v alues of m and v alues of n W e will later go and begin a proof b y complete induction on m for all n Theorem 3 F or n > 2 m > 2 we have r ( B m;n ) 2 b m + n 3 c Proof: The follo wing sets describe a domination b y placemen t of Bishops. W e rst note that an y square ( i; j ) can be attac k ed one of three w a ys. These are to directly ha v e a Bishop on the square, or to ha v e a Bishop attac k it via an tidiagonal A i + j 1 attac k it or to ha v e a Bishop in diagonal D m + j i The follo wing t w o sets describe domination locations for Bishops, where w e these sets are not necessarily unique. The rst set describes the beha vior observ ed for the white colored squares, and the second set describes the pattern for the blac k squares in a possible domination. 9
PAGE 16
8 > > > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > > > : (2 ; 2) ; (1 ; 5) ; (1 ; 7) ; :::; (1 ; 2 m +1) ; ( m; 3 m +2) ; ( m; 3 m +4) ; :::; ( m; 5 m 2) ; (1 ; 6 m 1) ; (1 ; 6 m +1) ; :::; (1 ; 8 m 5) ; ( m; 9 m 4) ; ( m; 9 m 2) ; :::; ( m; 11 m 8) ; (1 ; 12 m 7) ; (1 ; 12 m 5) ; :::; (1 ; 14 m 11) ; ( m; 15 m 10) ; ( m; 15 m 8) ; :::; ( m; 17 m 14) ; (1 ; 18 m 13) ; (1 ; 18 m 11) ; :::; (1 ; 20 m 17) ; ( m; 21 m 16) ; ( m; 21 m 14) ; :::; ( m; 23 m 20) ; . . . . . . (1 ; 6( m 1) k +5) ; (1 ; 6( m 1) k +3) ; :::; (1 ; 6( m 1) k +2 m +1) ; ( m; 6( m 1) k +3 m +2) ; ( m; 6( m 1) k +3 m +4) ; :::; ( m; 6( m 1) k +5 m 2) ; 9 > > > > > > > > > > > > > > > > > > > > = > > > > > > > > > > > > > > > > > > > > ; : Figure 4.1. Positions of White Bishops in my Domination Pattern. F or this rst subset, ha v e sho wn groupings of subsets of the bishops in ro w 1 and ro w m W e can note that the white Bishops start o in a nonconforming manner attac king diagonal D m and an tidiagonal A 2 and ha v e a main tained pattern for the Bishops at ev ery 2 m 4 columns. The ending columns m ust then be handled with placemen t of Bishops o the pattern for sizes of c hessboards that are not in full subsets. 10
PAGE 17
This second set describes the conguration Bishops for the blac k squares, it can be easily noted that w e do not start the set with a square that is not on the border. 8 > > > > > > > > > > > > > > > > > > < > > > > > > > > > > > > > > > > > > : (1 ; 2) ; (1 ; 4) ; :::; (1 ; 2 m 2) ; ( m; 3 m 1) ; (1 ; 3 m +1) ; :::; ( m; 5 m 5) ; (1 ; 6 m 4) (1 ; 6 m 2) :::; (1 ; 8 m 8) ; ( m; 9 m 7) ; (1 ; 9 m 5) :::; ( m; 11 m 11) ; (1 ; 12 m 10) ; (1 ; 12 m 8) ; :::; (1 ; 14 m 14) ; ( m; 15 m 13) ; ( m; 15 m 11) ; :::; ( m; 17 m 17) ; (1 ; 18 m 16) ; (1 ; 18 m 14) ; :::; (1 ; 20 m 20) ; ( m; 21 m 19) ; ( m; 21 m 17) ; :::; ( m; 23 m 23) ; . . . ; . . . (1 ; 6( m 1) k +2) ; (1 ; 6( m 1) k +4) ; :::; (1 ; 6( m 1) k +2 m 2) ; ( m; 6( m 1) k +3 m 1) ; ( m; 6( m 1) k +3 m +1) ; :::; ( m; 6( m 1) k +5 m 5) ; 9 > > > > > > > > > > > > > > > > > > = > > > > > > > > > > > > > > > > > > ; Figure 4.2. Positions of Black Bishops in my Domination Pattern. 11
PAGE 18
This next picture actually displa ys and example of the com bined white and blac k bishop in the the domination pattern for the white squars B 5 ;n This domination is t ypical for all c hessboards, and one can note that for ev ery square it either has a Bishop on it or is attac k ed b y a Bishop. W e basically ha v e groups of m 1 bishops on squares of the top and bottom ro ws. ppp ppp ppp ppp ppp ppp Figure 4.3. A n optimal c ongur ation for the white c olor e d squar es and lar ge n 12
PAGE 19
W e no w sho w that for Chessboards with sizes of n not equal to the sizes giv en in our pattern, I no w presen t a conguration of Bishops that concurs with our domination n um ber and w e call it a remainder theorem to represen t the remainder of the Chessboard. This pattern is represen ted b y the follo wing gures. B 1 B 2 B 2 B 3 B 3 B 3 B 4 B 4 B 4 B 4 B 5 B 5 B 5 B 5 B 5 @ @ I @ @ I @ @ I @ @ I @ @ I Figure 4.4. R emainder Congur ation for White Bishops. 13
PAGE 20
The remainder for the set of Bishops that lie on the blac k squares start at a smaller column index than the Bishops that lie on the white squares. B 1 B 2 B 2 B 3 B 3 B 3 B 4 B 4 B 4 B 4 B 5 B 5 B 5 B 5 B 5 @ @ I @ @ I @ @ I @ @ I @ @ I Figure 4.5. R emainder Congur ation for Black Bishops. F or an y c hessboard, a correlation m ust be made when m and n do not lie on the bounds of the form ula noting that there are 2 n +2 m 4 2 white squares and 2 n +2 m 4 2 blac k squares on the boundary The n um ber of Bishops can be found b y noting that eac h Bishop independen tly attac ks 3 squares on the boundary th us equating to l n + m 2 3 m = j n + m 3 k Bishops. 14
PAGE 21
5. The Conjecture is T rue when n = 2 m + ` for ` 5 F or the cases of n = 2 m +1, 2 m +2, 2 m +3, 2 m +4 and 2 m +5, I ha v e sho wn the conjecture true. The proof is similar to the one found in Chapter 3. Theorem 4 F or all m r ( B m; 2 m +1 ) = r ( B m; 2 m +2 ) = 2 m Proof: Suppose that w e can use m 1 Bishops to dominate the squares for a color, sa y white. Let n be the total n um ber of columns in our c hessboard, and so n = 2 m + 1 or n = 2 m + 2. Let us rst dene ` = n 2 m so ` = 1 or ` = 2. As in Theorem 2, let us c hoose diagonals p and q to represen t bishopless diagonals with the properties that p is the largest in teger less than m and q is the smallest in teger greater than 2 m + ` So p exists otherwise all white diagonals of D k with 1 k 2 m + ` w ould ha v e a Bishop, and since there are less than m white Bishops then this is impossible. One can sho w that q exists for a similiar reason as does p Since there are m white diagonals bet w een D p and D q then w e will assume q p 2 1 m 1 th us q p 2 m W e kno w that one end of D p is in A m p +1 and the other end is in A p + m 1 and one end of D q is in A q m +1 and the 15
PAGE 22
other end is in A 3 m +2 l q 1 Since q p 2 m w e ha v e ( q m +1) ( p + m 1) 2. Th us, the an tidiagonals that co v er D p are con tiguous with the an tidiagonals that co v ers the squares co v er D q (there ma y be o v erlap bet w een these t w o sets of an tidiagonals, but there is no \gap"). Therefore the total n um ber of an tidiagonals that pass through the squares of D p and D q is found as the difference bet w een these an tidiagonals on eac h side, as giv en (2 n + m q 1) ( m p +1) 2 = n q p 2 2 m + ` m = m + ` m Since w e assumed there are only m 1 white Bishops, then w e ha v e a con tradiction. The proof is similar for the blac k squares. Therefore for ` = 1 ; 2, w e ha v e r ( B m; 2 m + ` ) = 2 m 2 Theorem 5 F or all m we have r ( B m; 2 m +3 ) = r ( B m; 2 m +4 ) = r ( B m; 2 m +5 ) = 2( m + 1) Proof: W e alw a ys ha v e at least m + 2 total diagonals with m squares, where there are l m 2 m + 2 white diagonals with m squares and j m 2 k + 2 blac k diagonals with m squares, and th us there cannot be t w o of these diagonals of eac h color bishopless. No w w e consider three cases for Bishops of a color, and let ` = 3 ; 4 ; 5. Case 1: No diagonal con taining m squares is bishopless: F or an y n w e can dominate B m;n with 2 j n + m 3 k Bishops, (Figure 4.1 and Figure 4.2 sho w these dominations for general c hessboards B n;m ). Therefore r ( B m;n ) 2 j 2 m + ` + m 3 k = 2 j 3 m + ` 3 k = 2 h m + b ` 3 c i 2 h m + j 5 3 ki = 2( m + 1) T o sho w r ( B m;n ) = 2( m + 1), suppose a domination exists with at 16
PAGE 23
most m Bishops for some color, sa y white. Let us c hoose p < m to be the largest in teger, suc h that D p is bishopless. Then p exists otherwise all white diagonals of D k with 1 k 2 m + ` w ould ha v e a Bishop, and since there are at most m white Bishops then this is impossible. Let us also c hoose q > n to be smallest in teger, suc h that D q is also bishopless and is of the same color as D p One can sho w that q exists for a similiar reason as p Since there are q p 2 1 white diagonals bet w een. D p and D q then w e m ust assume q p 2 1 m hence q p 2( m + 1). How many Bishops ar e ne e de d to dominate the squar es of antidiagonals p and q ? Diagonal p includes all squares bet w een ( m p +1 ; 1) and ( m; p ). Diagonal q includes all squares bet w een (1 ; q m + 1) and ( n + m q; n ). W e kno w that one end of D p is in A m p +1 and the other end is in A m + p 1 and one end of D q is in A q m +1 and the other end is in A 2(2 m + ` )+ m q 1 Either q p 2( m + 1) implies that ( q m + 1) ( p + m 1) 2, or q p 2( m + 1) implies that ( q m + 1) ( p + m 1) 4. If q p 2( m +1) implies that ( q m +1) ( p + m 1) 2, and the an tidiagonals that co v er D i are con tiguous with the an tidiagonals that co v er D j (there ma y be o v erlap bet w een these t w o sets of an tidiagonals, but there is no \gap"), where ( q p ) 2 m + 2 2 m 2 m + 2 = 2. So the total n um ber of an tidiagonals can be found as the dierence bet w een these an tidiagonals on eac h side as needed to co v er both D p and D q is (2(2 m + ` )+ m q 1) ( m p +1) 2 = 2(2 m + ` ) 2 ( q p ) 2 = 2 m + ` 1 q p 2 2 m + ` 1 2( m +1) 2 = 2 m + ` 1 ( m +1) = m + ` 2 m +1 Since ` 3 and there are at most m white Bishops, then 17
PAGE 24
w e ha v e a con tracdiction. The proof is similar for the blac k squares. Therefore, r ( B m;n ) = 2 b m + n 3 c 2 Otherwise q p 2( m +1) implies that ( q m +1) ( p + m 1) 4 and the an tidiagonals ha v e a \gap", where ( q p ) 2 m +2 (2 m +2) 2 m +2 = 4. So the total n um ber of an tidiagonals can be found as the dierence bet w een these an tidiagonals on eac h side as needed to co v er both D p and D q is (2(2 m + ` )+ m q 1) ( m p +1) 2 = 2(2 m + ` ) 2 ( q p )+2 2 = 2 m + ` q p 2 2 m + ` 2( m +1) 2 = 2 m + ` ( m + 1) = m + ` 1 m + 1 Since ` 3 and there are at most m white Bishops, then w e ha v e a con tracdiction. The proof is similar for the blac k squares. Therefore, r ( B m;n ) = 2( m + 1). 2 Case 2: One diagonal with m squares is bishopless: Let us label the bishopless diagonal D k where m k n Let D k be some color, sa y white. W e kno w that k 6 = m or w e ha v e no w a y to attac k square (1 ; 1). Similarly w e cannot ha v e k = n but for square ( n; m ). D k has squares that range bet w een (1 ; k m + 1) to ( m; k + 1) for some k A Bishop can only attac k one square of eac h A k m +1 to A k + m +1 So the n um ber of Bishops needed are k m + 1 + n + m ( k + m + 1) n m 2 = 2 m + ` + m 2 = m + ` 2 m + 1. Th us, for all m > 2 w e are requiring more than m Bishops. 2 Case 3: More than one bishopless diagonal bet w een D p and D q : Since there are at least m + 1 squares that require Bishops from at least t w o bishopless diagonals of size m then m y domination matc hes this n um ber and uses only m + 1 Bishops. 2 18
PAGE 25
6. The Conjecture is T rue for all 2 n and 3 n Chessboards W e can note that the Bishops in this case are also independen tly dominating upto three squares, and quite easily v erify the conjecture. ppp ppp ppp Figure 6.1. Dominations for all 2 n Chessb o ar ds. Theorem 6 When m = 2 and for all n we have r ( B 2 ;n ) = 2 j n +2 3 k Proof: Let P n be dened as the set of disjoin t paths of length n Then B 2 ;n = P n S P n is disjoin t union of all the paths of length n It is w ell kno wn that r ( P n ) = l n 3 m th us r ( B 2 ;n ) = r ( P n S P n ) = r ( P n )+ r ( P n ) = l n 3 m + l n 3 m = 2 l n 3 m 2 Theorem 7 F or all n w e ha v e r ( B 3 ;n ) = 2 j n +3 3 k = 2 j n 3 k + 2 Proof: This will be done via induction on n and conjecture that this holds true for all possible m There are a total of four possible congurations of the last six columns that the dominations fall in to. These six columns repeat in 19
PAGE 26
pattern and I begin with a basis of n = 4 ; 5 ; 6 ; 7 ; 8 and 9. Applying Theorem 2 for n = 4 ; 5, w e can state that the n um ber of Bishops required are 2 for a color. Also n = 6, w e can apply Theorem 2, and state that the n um ber of Bishops required are 3 for a color. When w e apply our form ula, w e ha v e j 4 3 + 1 k = 2, j 5 3 + 1 k = 2 and j 6 3 + 1 k = 3. So the form ula matc hes these results. Applying Theorem 4 for n = 7 ; 8, w e can state that the n um ber of Bishop required are 3 for a color. When w e apply our form ula, w e ha v e j 7 3 + 1 k = 3 and j 8 3 + 1 k = 3, and these form ula also matc hes these results. Applying Theorem 5 for n = 9, w e can state that the n um ber of Bishops required are 4 and applying our form ula w e ha v e the n um ber of Bishops required is j 9 3 + 1 k = 4 and is also the same result. So these v alues form a basis for induction. No w w e can assume that for columns n > 9 that r ( B 3 ;k ) 2 j k 3 + 1 k holds true for 4 k n as the upper bound for the n um ber of Bishops required to dominate B 3 ;k I m ust sho w through t w o cases of the last six columns where (1 ; n ) is either a white or a blac k square that r ( B 3 ;k ) 2 j k 3 + 1 k 20
PAGE 27
r r r r r r r r r r r r (1 ; 1) (1 ; 2) (1 ; 3) (1 ;n 5) (1 ;n 4) (1 ;n 3) (1 ;n 2) (1 ;n 1) (1 ;n ) (2 ; 1) (2 ; 2) (2 ; 3) (2 ;n 5) (2 ;n 4) (2 ;n 3) (2 ;n 2) (2 ;n 1) (2 ;n ) (3 ; 1) (3 ; 2) (3 ; 3) (3 ;n 5) (3 ;n 4) (3 ;n 3) (3 ;n 2) (3 ;n 1) (3 ;n ) Figure 6.2. F or all B 3 ;n wher e (1 ; n ) is black. Case where square (1 ; n ) is blac k: Let D be the set of Bishop squares that dominates B 3 ;n Square (2 ; n ) m ust be dominated, and so a Bishop can either be at square (2 ; n ) or w e need to ha v e a Bishop at either of the squares (1 ; n 1) or (3 ; n 1). 21
PAGE 28
q q q q q q q q q q q q Figure 6.3. F or all B 3 ;n wher e (1 ; n ) is black, r ( B 3 ;n ) r ( B 3 ;n 2 ) + 1 Since w e need to dominate square (2 ; n ) then either a Bishop lies on square (2 ; n ) or there is a Bishop on either square (3 ; n 1) or square (1 ; n 1) So assume square (2 ; n ) is con tained in D (see Figure 6.3), and w e ha v e used one Bishop. Th us w e ha v e fully dominated t w o columns from B 3 ;n and are left with B 3 ;n 2 to dominate. So our result is: r ( B 3 ;n ) r ( B 3 ;n 2 ) + 1 j n +1 3 k + 1 j n 3 k + 1. 2 If a Bishop is not at square (2 ; n ), then w e m ust ha v e a Bishop at sqaure (1 ; n 1) and square (3 ; n 1). So without loss of generalit y let us assume square (1 ; n 1) is in D So no w w e ha v e dominated t w o columns from B 3 ;n So there m ust be a Bishop at either sqaure (3 ; n 1) or sqaure (2 ; n 3) or square (1 ; n 4). Ha ving a Bishop lie on square (1 ; n 4) dominates the same squares as ha ving the Bishop lie on the other squares and more. So assume there is a second Bishop on square (1 ; n 4) (see Figure 6.4). 22
PAGE 29
q q q q q q q q q q q q Figure 6.4. F or all B 3 ;n wher e (1 ; n ) is black, r ( B 3 ;n ) r ( B 3 ;n 6 ) + 2 W e can observ e from Figure 6.4 that square (1 ; n 5) is not dominated b y a Bishop. It is also possible to ha v e square (3 ; n 5) not dominated b y a Bishop. So either an additional Bishop lies on square (1 ; n 5), square (2 ; n 6) or on square (3 ; n 7). Since this Bishop is from B 3 ;n 6 and w ould dominate more squares, let us assume that a Bishop lies on square (2 ; n 6), whic h giv es rise to the same domination result as giv en from the previous case. So no w w e ha v e used t w o Bishops to dominate a total of six columns with the assumption of the domination of a square b y a Bishop from B 3 ;n 6 So our result is: r ( B 3 ;n 6 ) + 2 r ( B 3 ;n ) 1 + j n 6 3 k +2 j n 3 k + 1. 2 23
PAGE 30
r r r r r r r r r r r r (1 ; 1) (1 ; 2) (1 ; 3) (1 ;n 5) (1 ;n 4) (1 ;n 3) (1 ;n 2) (1 ;n 1) (1 ;n ) (2 ; 1) (2 ; 2) (2 ; 3) (2 ;n 5) (2 ;n 4) (2 ;n 3) (2 ;n 2) (2 ;n 1) (2 ;n ) (3 ; 1) (3 ; 2) (3 ; 3) (3 ;n 5) (3 ;n 4) (3 ;n 3) (3 ;n 2) (3 ;n 1) (3 ;n ) Figure 6.5. F or all B 3 ;n wher e (1 ; n ) is white. Case where square (1 ; n ) is white. Let D be the set of Bishop squares that dominates B 3 ;n as w e did when square (1 ; n ) w as blac k. Since a Bishop from D m ust dominate square (1 ; n ), then this Bishop m ust lie on either square (1 ; n ), square (2 ; n 1) or square (3 ; n 2). W e can note that ha ving square (2 ; n 1) con tained in D is also a domination of the same minimal size as ha ving square (1 ; n ) con tained in D So either square (2 ; n 1) or square (3 ; n 2) is con tained in D 24
PAGE 31
q q q q q q q q q q q q Figure 6.6. F or all B 3 ;n and (1 ; n ) is white, r ( B 3 ;n ) r ( B 3 ;n 3 ) + 1 If square (1 ; n ) is con tained in D then w e kno w w e get the same domination of equal size as if square (2 ; n 1) or if square (3 ; n 2) w ere con tained in D So let us assume that square (1 ; n ) is not in D If square (2 ; n 1) is con tained in D then w e can note that this dominates all the white squares of B 3 ; 3 from B 3 ;n This reduces our problem b y three columns, and if w e let k = n 3 w e can refer to inductiv e h ypothesis for B 3 ;k So our our result is: r ( B 3 ;n ) r ( B 3 ;n 3 ) + 1 1 + j n 3 3 k + 1. = j n 3 k + 1. 2 25
PAGE 32
q q q q q q q q q q q q Figure 6.7. A nother form wher e (1 ; n ) is white, r ( B 3 ;n 5 ) r ( B 3 ;n ) + 2 In the last conguration, square (2 ; n 1) is no w not in D and square (3 ; n 2) is con tained in D W e no w note that w e need to dominate square (3 ; n ). If w e had a Bishop there, w e w ould dominate the same squares as placing a Bishop at square (2 ; n 1). W e also can nd that placing a Bishop at square (1 ; n 2) also dominates the same squares as placing the Bishop at square (2 ; n 1) and more squares. Since there are no other w a ys to dominate these other squares, let us assume that the second Bishop lies on square (1 ; n 2) (see Figure 6.7). No w w e can note that our result is r ( B 3 ;n ) r ( B 3 ;n 5 ) + 2. Ha ving a Bishop lie on square (2 ; n 5) w ould only dominate that square, and w e w ould w an t to ha v e the Bishop lie on either square (1 ; n 6) or square (3 ; n 6). This Bishop is not part of the domination of B 3 ;n 5 So our result is: r ( B 3 ;n ) r ( B 3 ;n 5 ) + 2 j n 2 3 k + 2 j n +1 3 k + 1 j n 3 k + 1. 2 26
PAGE 33
7. In teger Programing Results An alternate method to model this problem is using systems of linear inequalities for specic Chessboards. I wrote a c program to generate suc h inequalities in to specic text les that con tained the system of linear inequalities describing diagonals and the squares that belong to eac h diagonal and an tidiagonal for eac h specic Chessboard, whic h w ere run through LINDO. I ran these processes in hopes of nding a coun terexample to the conjecture at hand. I w as not able to nd suc h a coun ter example, m y results ran for v alues m 9 with respectiv e v alues of n 110. Squares of the diagonals range from from the Northeast to the Southw est, and squares of an tidiagonals range from the Southeast to the NorthW est. I for the sak e of the program, m y v ariable names w ere Diag# and An tid# and w ere n um bered sequen tially and squares w ere ro wcolumn coordinates, starting with r#c#. The summation of a diagonal and an tidiagonal subtracting a double coun ted square w as an inequalit y v alued as greater than or equal to one. Diagonals min us the squares of the an tidiagonal w ere v alued as equal to zero. An tidiagonals min us the squares of the diagonal w ere v alued as equal to zero. W e no w giv e an sample of systems of linear inequalities that describe 27
PAGE 34
the solution to the white squares for a B 5 ; 16 I also ha v e displa y ed a sample Chessboard with the solution obtained. The solution obtained is in teresting that it is similar to the upper bound domination I ha v e giv en. The In teger program that modeled the white squares is giv en as follo ws: min Diag1+Diag2+Diag3+Diag4+Diag5+Diag6+Diag7+Diag8+Diag9+Diag10 st Antid8r1c1r2c2r3c3r4c4r5c5=0 Diag1r1c1=0 Diag1+Antid8r1c1>=1 Antid1r1c3r2c4r3c5r4c6r5c7=0 Diag2+Antid1r1c3>=1 Antid2r1c5r2c6r3c7r4c8r5c9=0 Diag3+Antid2r1c5>=1 Antid3r1c7r2c8r3c9r4c10r5c11=0 Diag4+Antid3r1c7>=1 Antid4r1c9r2c10r3c11r4c12r5c13=0 Diag5+Antid4r1c9>=1 Antid5r1c11r2c12r3c13r4c14r5c15=0 Diag6+Antid5r1c11>=1 Antid6r1c13r2c14r3c15r4c16=0 Diag7+Antid6r1c13>=1 Antid7r1c15r2c16=0 Diag8+Antid7r1c15>=1 Diag2+Antid8r2c2>=1 Diag3+Antid1r2c4>=1 Diag4+Antid2r2c6>=1 Diag5+Antid3r2c8>=1 Diag6+Antid4r2c10>=1 Diag7+Antid5r2c12>=1 Diag8+Antid6r2c14>=1 Diag9+Antid7r2c16>=1 28
PAGE 35
Antid9r3c1r4c2r5c3=0 Diag2r3c1r2c2r1c3=0 Diag2+Antid9r3c1>=1 Diag3+Antid8r3c3>=1 Diag4+Antid1r3c5>=1 Diag5+Antid2r3c7>=1 Diag6+Antid3r3c9>=1 Diag7+Antid4r3c11>=1 Diag8+Antid5r3c13>=1 Diag9+Antid6r3c15>=1 Diag3+Antid9r4c2>=1 Diag4+Antid8r4c4>=1 Diag5+Antid1r4c6>=1 Diag6+Antid2r4c8>=1 Diag7+Antid3r4c10>=1 Diag8+Antid4r4c12>=1 Diag9+Antid5r4c14>=1 Diag10+Antid6r4c16>=1 Antid10r5c1=0 Diag3r5c1r4c2r3c3r2c4r1c5=0 Diag3+Antid10r5c1>=1 Diag4r5c3r4c4r3c5r2c6r1c7=0 Diag4+Antid9r5c3>=1 Diag5r5c5r4c6r3c7r2c8r1c9=0 Diag5+Antid8r5c5>=1 Diag6r5c7r4c8r3c9r2c10r1c11=0 Diag6+Antid1r5c7>=1 Diag7r5c9r4c10r3c11r2c12r1c13=0 Diag7+Antid2r5c9>=1 Diag8r5c11r4c12r3c13r2c14r1c15=0 Diag8+Antid3r5c11>=1 Diag9r5c13r4c14r3c15r2c16=0 Diag9+Antid4r5c13>=1 Diag10r5c15r4c16=0 Diag10+Antid5r5c15>=1 29
PAGE 36
end terse gin 200 go 99999999 no quit 30
PAGE 37
The Bishop square locations produced b y LINDO are giv en in the follo wing set as f R 2 C 2 ; R 5 C 3 ; R 5 C 1 ; R 1 C 9 ; R 1 C 11 ; R 1 C 13 ; R 1 C 15 g LINDO 5.3 (October 1994) LINDO Systems, Chicago, IL LDW83531000 University of Colorado : : ? : LP OPTIMUM FOUND AT STEP 102 OBJECTIVE VALUE = 5.58333349 NEW INTEGER SOLUTION OF 7.00000000 AT BRANCH 5 PIVOT 352 BOUND ON OPTIMUM: 6.111111 ENUMERATION COMPLETE. BRANCHES= 5 PIVOTS= 352 LAST INTEGER SOLUTION IS THE BEST FOUND REINSTALLING BEST SOLUTION... 99999999 : OBJECTIVE FUNCTION VALUE 1) 7.000000 VARIABLE VALUE REDUCED COST DIAG2 1.000000 1.000000 DIAG3 1.000000 1.000000 DIAG4 1.000000 1.000000 DIAG5 1.000000 1.000000 DIAG6 1.000000 1.000000 DIAG7 1.000000 1.000000 DIAG8 1.000000 1.000000 ANTID8 1.000000 0.000000 31
PAGE 38
R2C2 1.000000 0.000000 ANTID4 1.000000 0.000000 R1C9 1.000000 0.000000 ANTID5 1.000000 0.000000 R1C11 1.000000 0.000000 ANTID6 1.000000 0.000000 R1C13 1.000000 0.000000 ANTID7 1.000000 0.000000 R1C15 1.000000 0.000000 ANTID9 1.000000 0.000000 R5C3 1.000000 0.000000 ANTID10 1.000000 0.000000 R5C1 1.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES NO. ITERATIONS= 371 BRANCHES= 5 DETERM.= 1.000E 0 : Again, w e see from this example alone that there is a tend for the placemen t of the Bishops to w ard the top and bottom ro ws. Figure 7.1. LINDO r esults for white Bishops r ( B 5 ; 16 ) 32
PAGE 39
REFERENCES [1] E. J. Coc k a yne, B. Gam ble and B. Shepherd, Chessb o ar d Domination Pr oblems Discrete Mathematics 86(1990)13 20 [2] G. H. F ric k e, et. al. Combinatorial Pr oblems on Chessb o ar ds:A Brief Survey in Gr aph The ory, Combinatorics and Applic ations Y. Ala vi and A. Sc h w enk, John Wiley and Sons, Inc., NY, 1995. [3] A. M. Y aglom and I. M. Y aglom, Challenging Mathematic al Pr oblems with Elementary Solutions ,Do v er Publications, Inc., NY, v1, 1964. 33
