8xN
Optimal Domination Numbers
Solutions and Proofs
Part 1 of 3
8xN Optimal Domination Numbers
D(8,N) = the domination number for a board with 8 rows and N columns.
D(8, 1) = 8
D(8, 2) = 8
D(8, 3) = 8
D(8, 4) = 8
D(8, 5) = 8
D(8, 6) = 8
D(8, 7) = 11
--------------
D(8, 8) = 12
D(8, 9) = 13
D(8,10) = 14
D(8,11) = 16
D(8,12) = 16
D(8,13) = 18
--------------
D(8,N+6) = D(8,N) + 8 for N >= 8
Part 2 of 3
8xN Sufficiency Proofs
Sufficiency is proved by showing a feasible solution
using the domination number of knights.
________________________________________________________
D(8,1) <= 8 D(8,2) <= 8 D(8,3) <= 8 D(8,4) <= 8
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(8,5) <= 8 D(8,6) <= 8 D(8,7) <= 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 - - - - - - - - -
- - - - - - - - - - - - - - - - - -
________________________________________________________
Extendable solution by repeating the first six columns
D(8,8) <= 12 D(8,6k+2) <= 8k+4
- - - - - - - - - - - - - - - - - - - - - -
- - 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 - -
- - - - - - - - - - - - - - - - - - - - - -
\---------/
repeats
________________________________________________________
Extendable solution by repeating the first six columns
D(8,9) <= 13 D(8,6k+3) <= 8k+5
- - - - - - - - - - - - - - - - - - - - - - - -
- - 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 - - - -
\---------/
repeats
________________________________________________________
Extendable solution by repeating the first six columns
D(8,10) <= 14 D(8,6k+4) <= 8k+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 x - - - x x - - - x x - -
- - - - - - - x - - - - x x - - - - - - - - - x - -
- - - - x - - - - - - - - - - - - - - - x - - - - -
\---------/
repeats
________________________________________________________
Extendable solution by repeating the first six columns
D(8,11) <= 16 D(8,6k+5) <= 8k+8
- - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - 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 -
- - - - - - - - - - - - - - - - - - - - - - - - - - - -
\---------/
repeats
________________________________________________________
Extendable solution by repeating the first six columns
D(8,12) <= 16 D(8,6k) <= 8k
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - 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 - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
\---------/
repeats
________________________________________________________
Extendable solution by repeating the first six columns
D(8,13) <= 18 D(8,6k+1) <= 8k+2
- - - - - - - - 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 - - - - - - - - - - - - x - -
- - - - x - - - - - - - - - - - - - - - - - - x - - - - - - - -
\---------/
repeats
Part 3 of 3
8xN 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(8,1) >= 8
o Since no square can be attacked,
o all squares must be covered by occupying them.
o
o
o
o
o
o
________________________________________________________
D(8,2) >= 8
o o No two o-squares can be covered by the same knight,
o o so it takes 8 knights just to cover the o-squares.
- - Thus it takes at least 8 knights to cover the whole board.
- -
- -
- -
o o
o o
________________________________________________________
D(8,3) >= 8
a a a No single knight can cover the lettered squares from both
a b a ends of the diagram, so it takes two separate sets of knights.
- - - A knight can cover at most two squares within an end group.
- - - However, the b-square can only be covered by itself,
- - - so it takes 4 knights to cover one end group.
- - - Two end groups take 8 knights, thus it takes at least 8 knights
c d c to cover the whole board.
c c c
________________________________________________________
D(8,4) >= 8
a a a - It takes 4 knights to cover the end patterns.
a a a a No knight can cover both an a-square and a b-square,
- - - - so it takes a separate set of 4 knights to cover each end group,
- - - - thus it takes at least 8 knights to cover the whole board.
- - - -
- - - -
b b b b
b b b -
________________________________________________________
D(8,5) >= 8
a a a - - Same proof as 8x4.
a a a a -
- - - - -
- - - - -
- - - - -
- - - - -
a b b b -
a b b - -
________________________________________________________
D(8,6) >= 8
o - - - - o No two of the 8 o-squares can be covered by a single knight,
o o - - - - so it takes 8 knights to cover them all,
- - - - - - thus is takes at least 8 knights to cover the whole board.
- - - - - -
- - - - - -
- - - - - -
o o - - - -
o - - - - o
o - o o - o 2nd proof. A single knight can cover at most 2 of the
- o - - o - 16 o-squares, so it takes 8 knights to cover them all,
o - - - - o thus it takes at least 8 knights to cover the whole board.
- - - - - -
- - - - - -
o - - - - o
- o - - o -
o - o o - o
3rd proof. Same as 8x4 and 8x5.
________________________________________________________
D(8,7) >= 11
o - - - - o o The 8 o-squares must each be covered by a separate knight
o o - - - - - because no single knight can more than one of them.
- - - - - - - 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
- - - - - a b 3 knights to cover all a-squares and b-squares.
o o - - - - a This makes 11 knights to cover the lettered squares,
o - - - - a b thus it takes at least 11 knights to cover the whole board.
________________________________________________________
D(8,8) >= 12
o - - - - - - o No two of the 12 o-squares can be covered by a single knight,
o o - - - - o o so it takes 12 knights to cover them all,
- - - - - - - - thus it takes at least 12 knights to cover the whole board.
- - - - - - - -
- - - - - - - -
- - - - - - - -
o o - - - - o o
o - - - - - - o
________________________________________________________
D(8,9) >= 13
a a a - - - - - o The a-square group and the b-square group
a a a - - - - o o each require 4 knights. The o-squares
a a - - - - - - - take 1 knight each. A single knight can cover
- - - - - - - - - squares of only one letter, so it takes 13 knights
- - - - - - - - - to cover all the lettered squares. Thus it takes
- - - - - - - - - at least 13 knights to cover the whole board.
- - - - - b b b b
o o - - - - b b b
________________________________________________________
D(8,10) >= 14
o - - - - - - a a a The a-square group and b-square group each require 4 knights.
o o - - - - a a a a The o-squares take 1 knight each.
- - - - - - - - - - A single knight can cover the squares of at most one group.
- - - - - - - - - - So 14 knights are required to cover the lettered squares.
- - - - - - - - - - Thus it takes at least 14 knights to cover the whole board.
- - - - - - - - - -
o o - - - - b b b b
o - - - - - - b b b
________________________________________________________
D(8,11) >= 16
o o o - - - - - o o o Case 1: at least one of the x-squares in Figure 2
o o o o - - - - o o o is occupied. Pick one of those knights and possibly
- - - - - - - - - o o reflect the board so it becomes one of the x-squares
- - - - - - x - - - - in Figure 1. The four corner patterns in Figure 1
- - - - - - x - - - - need a total of 15 knights for a cover, but the
- - - - - - - - - - - x-square knight does not contribute to this cover.
o o - - - - - - - - - So in this case, it takes at least 16 knights
o - - - - o o o o o o to cover the board.
Figure 1
o o o - - o - - o o o Case 2: no Figure 2 x-square contains a knight. The top
o o o o - - - o o o o and bottom groups must be covered by two separate sets of
- - - - - o - - - - - knights since the x-squares are the only ones that
- - - - x - x - - - - cover squares of both groups and no knight occupies them.
- - - - x - x - - - - Each corner group needs 4 knights, but there are two
- - - - - o - - - - - locations (the central o-squares) that cover squares
o o o o - - - o o o o of both. However, occupying one leaves the other
o o o - - o - - o o o uncovered. So it can't reduce the total number from 8.
Figure 2 Thus it takes 16 knights in this case, too.
________________________________________________________
D(8,12) >= 16
o - - - - o o - - - - o No two of the 16 o-squares can be convered by
o o - - - - - - - - o o a single knight, so it takes 16 knights
- - - - - - - - - - - - to cover them all, thus it takes at least
- - - - - - - - - - - - 16 knights to cover the whole board.
- - - - - - - - - - - -
- - - - - - - - - - - -
o o - - - - - - - - o o
o - - - - o o - - - - o
________________________________________________________
D(8,13) >= 18
o - - - - a o a - - - - o The a-square group and b-square group each take
o o - - - - a - - - - o o 2 knights. A single knight can cover the squares
- - - - - - - - - - - - - of one group or one o-square, so it takes
- - - - - - - - - - - - - 18 knights to cover them all. Thus it takes
- - - - - - - - - - - - - at least 18 knights to cover the whole board.
- - - - - - - - - - - - -
o o - - - - b - - - - o o
o - - - - b o b - - - - o
________________________________________________________
D(8,14) >= 20
D(8,15) >= 21
D(8,16) >= 22
D(8,17) >= 24
________________________________________________________
D(8,18) >= 24
o - - - - b b b b b b b b - - - - o o's = 12
o o - - - - b - - - - b - - - - o o a's = 6
- - - - - b - - - - - - b - - - - - b's = 6
- - - - - - - - - - - - - - - - - - --------
- - - - - - - - - - - - - - - - - - sum = 24
- - - - - a - - - - - - a - - - - -
o o - - - - a - - - - a - - - - o o
o - - - - a a a a a a a a - - - - o
proof of 6-pattern
------------------
combine 2 dipper patterns, each requiring 3 knights
- 1 1 1 1 2 2 1 1 1 1 - - - a b a b a b a b - -
1 1 1 2 1 1 1 1 2 1 1 1 - - - a - - - - b - - -
- 1 1 1 1 1 1 1 1 1 1 - - - - - - - - - - - - -
- - 1 - 1 - - 1 - 1 - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
>= 6
combine 10 single squares, each requiring 1 knight
- 2 1 2 1 1 1 1 2 1 2 - - - a b c - - d e f - -
2 1 1 1 2 2 2 2 1 1 1 2 - - - g - - - - h - - -
- 2 2 2 1 2 2 1 2 2 2 - - - i - - - - - - j - -
1 - 1 - 2 - - 2 - 1 - 1 - - - - - - - - - - - -
- 1 - 1 - - - - 1 - 1 - - - - - - - - - - - - -
>= 10
add the 12 constraints
- 3 2 3 2 3 3 2 3 2 3 -
3 2 2 3 3 3 3 3 3 2 2 3
- 3 3 3 2 3 3 2 3 3 3 -
1 - 2 - 3 - - 3 - 2 - 1
- 1 - 1 - - - - 1 - 1 -
>= 16
divide by 3 and round
- 1 1 1 1 1 1 1 1 1 1 - - - o o o o o o o o - -
1 1 1 1 1 1 1 1 1 1 1 1 - - - o - - - - o - - -
- 1 1 1 1 1 1 1 1 1 1 - - - o - - - - - - o - -
1 - 1 - 1 - - 1 - 1 - 1 - - - - - - - - - - - -
- 1 - 1 - - - - 1 - 1 - - - - - - - - - - - - -
>= 6
________________________________________________________
TO BE CONTINUED
________________________________________________________