7xN
Optimal Domination Numbers
Solutions and Proofs
Part 1 of 3
7xN Optimal Domination Numbers
D(7,N) = the domination number for a board with 7 rows and N columns.
D(7, 1) = 7
D(7, 2) = 6
D(7, 3) = 6
D(7, 4) = 6
D(7, 5) = 7
D(7, 6) = 8
D(7, 7) = 10
D(7, 8) = 11
D(7, 9) = 12
D(7,10) = 14
D(7,11) = 15
D(7,12) = 16
D(7,13) = 17
-------------
D(7,14) = 19
D(7,15) = 20
D(7,16) = 21
D(7,17) = 22
D(7,18) = 24
-------------
D(7,N+5) = D(7,N) + 6 for N >= 14
Part 2 of 3
7xN Sufficiency Proofs
Sufficiency is proved by showing a feasible solution
using the domination number of knights.
________________________________________________________
D(7,1) <= 7 D(7,2) <= 6 D(7,3) <= 6 D(7,4) <= 6
x - - - - - - - - -
x - - - - - - - - -
x x x - x x - x x -
x x x - x x - x x -
x x x - x x - x x -
x - - - - - - - - -
x - - - - - - - - -
________________________________________________________
D(7,5) <= 7 D(7,6) <= 8 D(7,7) <= 10 D(7,8) <= 11
- - x - - - - - - - - - - - - - - - - - - - - - - -
- - x - - - - - - - - - - x - x - - - - x - x - - -
- - x - - - x x x x - - - x - x - - - - x - - - x -
- - x - - - - - - - - - - x - x - - - - x - - - x x
- - x - - - x x x x - - - x - x - - - - x - - - x -
- - x - - - - - - - - - - x - x - - - - x - x - - -
- - x - - - - - - - - - - - - - - - - - - - - - - -
________________________________________________________
D(7,9) <= 12 D(7,10) <= 14 D(7,11) <= 15
- - - - - - - - - - - x - - - - x - - - - x - - - - - - - -
- - x - x - x - - - - x - - - - x - - - - x - - - - - - - -
- - x - - - x - - - - x - - - - x - - - - x - - - x x x x -
- - x - - - x - - - - x - - - - x - - - - x - - - - - - - -
- - x - - - x - - - - x - - - - x - - - - x - - - x x x x -
- - x - x - x - - - - x - - - - x - - - - x - - - - - - - -
- - - - - - - - - - - x - - - - x - - - - x - - - - - - - -
________________________________________________________
D(7,12) <= 16 D(7,13) <= 17
- - - - - - - - - - - - - - - - - - - - x - - - -
- - x - x - - x - x - - - - x - x - - - - - - - -
- - x - - - - - - x - - - - x - - - x - - - x x -
- - x - x - - x - x - - - - x - - - x - - - x - -
- - x - - - - - - x - - - x x - - - x - - - x - -
- - x - x - - x - x - - - - - - - - - - x - x - -
- - - - - - - - - - - - - - - - x - - - - - - - -
________________________________________________________
Extendable solution by repeating five columns
D(7,5k+4) <= 6k+7
- - x - - x - - - - - - - -
- - x - - - - - - - - x - -
- - x - - - - x x - x x - -
- - x - - - - - - - - - - -
- x x - x x - - - - x x - -
- - - - - - - - - - x x - -
- - - - - - - x - - - - - -
\-------/
repeats
________________________________________________________
Extendable solution by repeating five columns
D(7,5k) <= 6k+2
- - - - - - x - - - - - - - -
- - x x - - - - - - - - x - -
- - x x - - - - x x - x x - -
- - - - - - - - - - - - - - -
- - x x - x x - - - - x x - -
- - x - - - - - - - - x x - -
- - - - - - - - x - - - - - -
\-------/
repeats
________________________________________________________
Extendable solution by repeating five columns
D(7,5k+1) <= 6k+3
- - - - - - x - - - - x - - - -
- - x x - - - - - - - - - - - -
- - x x - - - - x x - - - x x -
- - - - - - - - - - - - - x - -
- - x x - x x - - - - x - x - -
- - x - - - - - - - - x - x - -
- - - - - - - - x - - - - - - -
\-------/
repeats
________________________________________________________
Extendable solution by repeating five columns
D(7,5k+2) <= 6k+4
- - - - - - - x - - - - x - - - -
- - x - x - - - - - - - - - - - -
- - x - x - - - - x x - - - x x -
- - x - - - - - - - - - - - x - -
- x x - - - x x - - - - x - x - -
- - - - - - - - - - - - x - x - -
- - - - x - - - - x - - - - - - -
\-------/
repeats
________________________________________________________
Extendable solution by repeating five columns
D(7,5k+3) <= 6k+6
- - x - - x - - - - x - - - - - - -
- - x - - - - - - - - - - - - - - -
- - x - - - - x x - - - x x - x x -
- - x - - - - - - - - - - - - x - -
- x x - x x - - - x x - - - - x - -
- - - - - - - - - - - - - - - x - -
- - - - - - - x - - - - x - - x - -
\-------/
repeats
Part 3 of 3
7xN Necessity Proofs
Necessity is proved by showing that
at least the domination number of knights is required
to cover a subset of the board.
________________________________________________________
D(7,1) >= 7
o Since no square can be attacked,
o all squares must be covered by occupying them.
o
o
o
o
o
________________________________________________________
D(7,2) >= 6
o o Each of the 6 o-squares
o o must be covered by
- - a different knight.
- -
- -
- -
o o
________________________________________________________
D(7,3) >= 6
a b a The a-squares need 2 knights.
- a - The b-squares needs 1 knight, which can't also cover an a-square.
- - - The c-squares need 2 knights.
- - - Any way of covering the c-squares with 2 knights
- - - leaves at least one d-square uncovered.
c - c Thus a total of 6 knights is needed.
d c d
________________________________________________________
D(7,4) >= 6
o o - - Each of the 6 o-squares
- o - - must be covered by
- - - - a different knight.
- - - -
- - - -
- - o -
- - o o
________________________________________________________
D(7,5) >= 7
a a a - - a's = 4
a a a a - b's = 2
- - - - - c = 1
- - - - - -------
- - - - - sum = 7
- - - - -
b c b - b
________________________________________________________
D(7,6) >= 8
o - - - - o Each of the 8 o-squares
o o - - - - must be covered by
- - - - - - a different knight.
- - - - - -
- - - - - -
- - - - o o
o - - - - o
________________________________________________________
D(7,7) >= 10
o - - - - o o Each of the 10 o-squares
o o - - - - - must be covered by
- - - - - - - a different knight.
- - - - - - -
- - - - - - -
- - - - - o o
o o - - - - o
________________________________________________________
D(7,8) >= 11
o o - - - - o o The 8 o-squares must each be covered by a different knight.
- o - - - - o - The 3 a-squares require at least 2 knights.
- - - - - - - - Any 2-knight solution that covers the 3 a-squares
- - - - - - - - leaves at least 1 b-square uncovered, so it takes
- - - - - - - - 3 knights to cover all a-squares and b-squares.
a - a - - - - o This makes 11 knights to cover the lettered squares.
b a b - - - - o
________________________________________________________
D(7,9) >= 12
a a a - - - - b b Each of the 4 corner groups
a - a - - - - b - needs a separate set of 3 knights.
- - - - - - - - -
- - - - - - - - -
- - - - - - - - -
- c - - - - d - d
c c - - - - d d d
________________________________________________________
TO BE CONTINUED
________________________________________________________