Part 1 of 3
4xN Optimal Domination Numbers


D(4,N) = the domination number for a board with 4 rows and N columns.

D(4,1) = 4
------------
D(4,2) = 4
D(4,3) = 4
D(4,4) = 4
D(4,5) = 4
D(4,6) = 4
D(4,7) = 6
------------
D(4,N+6) = D(4,N) + 4  for N >= 2



Part 2 of 3
4xN Sufficiency Proofs


Sufficiency is proved by showing a feasible solution
using the domination number of knights.

________________________________________________________
D(4,1) <= 4

x
x
x
x

________________________________________________________
Extendable solution by repeating the first six columns
D(4,2) <= 4    D(4,6k+2) <= 4k+4

- -            - - - - - - - -
x x            - - x x - - x x
x x            - - x x - - x x
- -            - - - - - - - -
               \---------/
                 repeats

________________________________________________________
Extendable solution by repeating the first six columns
D(4,3) <= 4    D(4,6k+3) <= 4k+4

- - -          - - - - - - - - -
- x x          - - x x - - - x x
- x x          - - x x - - - x x
- - -          - - - - - - - - -
               \---------/
                 repeats

________________________________________________________
Extendable solution by repeating the first six columns
D(4,4) <= 4    D(4,6k+4) <= 4k+4

- - - -        - - - - - - - - - -
- - x x        - - x x - - - - x x
- - x x        - - x x - - - - x x
- - - -        - - - - - - - - - -
               \---------/
                 repeats

________________________________________________________
Extendable solution by repeating the first six columns
D(4,5) <= 4     D(4,6k+5) <= 4k+4

- - - - -       - - - - - - - - - - -
- - x x -       - - x x - - - - x x -
- - x x -       - - x x - - - - x x -
- - - - -       - - - - - - - - - - -
                \---------/
                  repeats

________________________________________________________
Extendable solution by repeating the first six columns
D(4,6) <= 4    D(4,6k) <= 4k

- - - - - -    - - - - - - - - - - - -
- - x x - -    - - x x - - - - x x - -
- - x x - -    - - x x - - - - x x - -
- - - - - -    - - - - - - - - - - - -
               \---------/
                 repeats

________________________________________________________
Extendable solution by repeating the first six columns
D(4,7) <= 6       D(4,6k+1) <= 4k+2

- - - - - - -     - - - - - - - - - - - - -
- - x x x - -     - - x x - - - - x x x - -
- - x x x - -     - - x x - - - - x x x - -
- - - - - - -     - - - - - - - - - - - - -
                  \---------/
                    repeats



Part 3 of 3
4xN 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(4,1) >= 4

o
o   Since no square can be attacked,
o   all squares must be covered by occupying them.
o

________________________________________________________
D(4,2) >= 4

o o
o o   2x4 block requires 4 knights.
o o
o o

________________________________________________________
D(4,3) >= 4

o o -
o o -   2x4 block requires 4 knights.
o o -
o o -

________________________________________________________
D(4,4) >= 4

o o - -
o o - -   2x4 block requires 4 knights.
o o - -
o o - -

________________________________________________________
D(4,5) >= 4

o o - - -
o o - - -   2x4 block requires 4 knights.
o o - - -
o o - - -

________________________________________________________
Extendable optimality proof by repeating the first six columns.
D(4,6k) >= 4k

o o - - - -
o o - - - -   Each repeatable 2x4 block requires a separate 4 knights.
o o - - - -
o o - - - -
\---------/
  repeats

________________________________________________________
Extendable optimality proof by repeating the first six columns.
D(4,6k+1) >= 4k+2

o o - - - - a   Each repeatable 2x4 block requires a separate 4 knights.
o o - - - - -   a-square and b-square each require a separate knight.
o o - - - - -   Total is 4 times number of 2x4 blocks plus 2.
o o - - - - b
\---------/
  repeats

________________________________________________________
Extendable optimality proof by repeating the first six columns.
D(4,6k+2) >= 4k+4

o o - - - - a a   Each repeatable 2x4 block requires a separate 4 knights.
o o - - - - a a   The right-hand 2x4 block requires an extra 4 knights.
o o - - - - a a   Total is 4 times number of 2x4 blocks plus 4.
o o - - - - a a
\---------/
  repeats

________________________________________________________
Extendable optimality proof by repeating the first six columns.
D(4,6k+3) >= 4k+4

o o - - - - a a -   Same proof as D(4,6k+2).
o o - - - - a a -
o o - - - - a a -
o o - - - - a a -
\---------/
  repeats

________________________________________________________
Extendable optimality proof by repeating the first six columns.
D(4,6k+4) >= 4k+4

o o - - - - a a - -    Same proof as D(4,6k+2).
o o - - - - a a - -
o o - - - - a a - -
o o - - - - a a - -
\---------/
  repeats

________________________________________________________
Extendable optimality proof by repeating the first six columns.
D(4,6k+5) >= 4k+4

o o - - - - a a - - -    Same proof as D(4,6k+2).
o o - - - - a a - - -
o o - - - - a a - - -
o o - - - - a a - - -
\---------/
  repeats

________________________________________________________