12x12
KNIGHT COVERING
OPTIMALITY PROOF
24 knights are required to cover a 12x12 board.
The proof is divided into two cases.
Case 1: There does not exist an unoccupied (3,3) square.
Case 2: There exists an unoccupied (3,3) square.
=========================
See the Divide and Round Proof Technique
for an explanation of the following notation and reasoning.
=========================
Proof of Case 1
If there does not exist an unoccupied (3,3) square,
then all (3,3) squares are occupied.
This takes 4 knights.
We must now show that 20 more knights are required
to cover the remaining squares.
First, we need to prove a new constraint.
Here's a 3-in-a-row constraint that requires 2 knights.
1 - 1 - 1 - - - - - - - o - o - o - - - - - - -
1 - 1 - 1 - 1 - - - - - - - - - - - - - - - - -
- 1 - 1 - 1 - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
>= 2
Three single-square constraints.
1 - - 1 - - 1 1 - - - - a - - - - - c - - - - -
- - 1 - 1 1 - - 1 - - - - - - - - b - - - - - -
- 1 - 1 - 1 - 2 - - - - - - - - - - - - - - - -
- - - - 1 - 1 - - - - - - - - - - - - - - - - -
>= 3
Add the above two constraint sets.
2 - 1 1 1 - 1 1 - - - -
1 - 2 - 2 1 1 - 1 - - -
- 2 - 2 - 2 - 2 - - - -
- - - - 1 - 1 - - - - -
>= 5
Divide by 2 and round.
1 - 1 1 1 - 1 1 - - - - o - o - o - o - - - - -
1 - 1 - 1 1 1 - 1 - - - - - - - - o - - - - - -
- 1 - 1 - 1 - 1 - - - - - - - - - - - - - - - -
- - - - 1 - 1 - - - - - - - - - - - - - - - - -
>= 3
Now we place the above constraint into four locations
on the 12x12 board.
1 - 1 1 1 - 1 1 - - 1 1 a - a - a - a - - - - b
1 - 1 - 1 1 1 - 1 1 - - - - - - - a - - - - - -
- 1 - 1 - 1 - 1 - - 1 1 - - - - - - - - - - - b
- 1 - - 1 - 1 - - 1 - 1 - - - - - - - - - - - -
1 - 1 - - - - - 1 - 1 1 - - - - - - - - - - - b
1 1 - 1 - - - - - 1 1 - c - - - - - - - - - b -
- 1 1 - - - - - 1 - 1 1 - c - - - - - - - - - b
1 1 - 1 - - - - - 1 - 1 c - - - - - - - - - - -
1 - 1 - - 1 - 1 - - 1 - - - - - - - - - - - - -
1 1 - - 1 - 1 - 1 - 1 - c - - - - - - - - - - -
- - 1 1 - 1 1 1 - 1 - 1 - - - - - - d - - - - -
1 1 - - 1 1 - 1 1 1 - 1 c - - - - d - d - d - d
>= 12
Here's another four-location constraint set.
1 1 - - 1 1 - 1 1 1 - 1 a - - - - b - b - b - b
- - 1 1 - 1 1 1 - 1 - 1 - - - - - - b - - - - -
1 1 - - 1 - 1 - 1 - 1 - a - - - - - - - - - - -
1 - 1 - - 1 - 1 - - 1 - - - - - - - - - - - - -
1 1 - 1 - - - - - 1 - 1 a - - - - - - - - - - -
- 1 1 - - - - - 1 - 1 1 - a - - - - - - - - - c
1 1 - 1 - - - - - 1 1 - a - - - - - - - - - c -
1 - 1 - - - - - 1 - 1 1 - - - - - - - - - - - c
- 1 - - 1 - 1 - - 1 - 1 - - - - - - - - - - - -
- 1 - 1 - 1 - 1 - - 1 1 - - - - - - - - - - - c
1 - 1 - 1 1 1 - 1 1 - - - - - - - d - - - - - -
1 - 1 1 1 - 1 1 - - 1 1 d - d - d - d - - - - c
>= 12
Sixteen single-square constraints.
- - - 1 - 1 1 - 1 - - - - - - - - a b - - - - -
- 1 - 1 1 - - 1 1 - 1 - - c - - - - - - - - d -
- - - 1 1 1 1 1 1 - - - - - - - - - - - - - - -
1 1 1 - 1 1 1 1 - 1 1 1 - - - - - - - - - - - -
- 1 1 1 2 1 1 2 1 1 1 - - - - - - - - - - - - -
1 - 1 1 1 1 1 1 1 1 - 1 e - - - - f g - - - - h
1 - 1 1 1 1 1 1 1 1 - 1 i - - - - j k - - - - l
- 1 1 1 2 1 1 2 1 1 1 - - - - - - - - - - - - -
1 1 1 - 1 1 1 1 - 1 1 1 - - - - - - - - - - - -
- - - 1 1 1 1 1 1 - - - - - - - - - - - - - - -
- 1 - 1 1 - - 1 1 - 1 - - m - - - - - - - - n -
- - - 1 - 1 1 - 1 - - - - - - - - o p - - - - -
>= 16
Add the above three constraint sets.
2 1 1 2 2 2 2 2 2 1 1 2
1 1 2 2 2 2 2 2 2 2 1 1
1 2 - 2 2 2 2 2 2 - 2 1
2 2 2 - 2 2 2 2 - 2 2 2
2 2 2 2 2 1 1 2 2 2 2 2
2 2 2 2 1 1 1 1 2 2 2 2
2 2 2 2 1 1 1 1 2 2 2 2
2 2 2 2 2 1 1 2 2 2 2 2
2 2 2 - 2 2 2 2 - 2 2 2
1 2 - 2 2 2 2 2 2 - 2 1
1 1 2 2 2 2 2 2 2 2 1 1
2 1 1 2 2 2 2 2 2 1 1 2
>= 40
Divide by 2 and round.
1 1 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 o - - - o -
1 1 - 1 1 1 1 1 1 - 1 1 o - - - - - - - - - - o
1 1 1 - 1 1 1 1 - 1 1 1 - - - - - - - - - - - -
1 1 1 1 1 1 1 1 1 1 1 1 o - - - - - - - - - - o
1 1 1 1 1 1 1 1 1 1 1 1 o o - - - o o - - - o o
1 1 1 1 1 1 1 1 1 1 1 1 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 - - - - - - - - - - - -
1 1 - 1 1 1 1 1 1 - 1 1 o - - - - - - - - - - o
1 1 1 1 1 1 1 1 1 1 1 1 - o - - - o o - - - o -
1 1 1 1 1 1 1 1 1 1 1 1 o - o - o o o o - o - o
>= 20
===========================
Proof of Case 2
If there exists an unoccupied (3,3) square, then without
loss of generality it can be in the upper left corner.
We need another new constraint.
Here are two 3-in-a-row constraints added.
1 - 1 - 1 - 1 - 1 - 1 - a - a - a - b - b - b -
1 - 1 - 2 - 2 - 1 - 1 - - - - - - - - - - - - -
- 1 - 1 - 2 - 1 - 1 - 1 - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
>= 4
Three single-square constraints added.
1 - - 1 - - - 1 - - 1 - c - - - - - - - - - e -
- - 1 - - 1 - - 1 - - - - - - - - d - - - - - -
- 1 - 1 - - - 1 - 1 - 1 - - - - - - - - - - - -
- - - - 1 - 1 - - - - - - - - - - - - - - - - -
>= 3
Add the above two constraint sets.
2 - 1 1 1 - 1 1 1 - 2 -
1 - 2 - 2 1 2 - 2 - 1 -
- 2 - 2 - 2 - 2 - 2 - 2
- - - - 1 - 1 - - - - -
>= 7
Divide by 2 and round.
1 - 1 1 1 - 1 1 1 - 1 - o - o - o - o - o - o -
1 - 1 - 1 1 1 - 1 - 1 - - - - - - o - - - - - -
- 1 - 1 - 1 - 1 - 1 - 1 - - - - - - - - - - - -
- - - - 1 - 1 - - - - - - - - - - - - - - - - -
>= 4
Note that the above configuration must be on an edge
of the board. Otherwise it can be covered by 3 knights.
Combine two of the above constraints.
(x 1)
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - 1 1 1 1 - - - - - - - - - - - - - - - -
1 1 1 1 1 1 1 1 1 1 1 1 - - - - - - - - - - - -
1 1 1 1 1 2 2 1 1 1 1 1 - - - - - a b - - - - -
1 1 1 2 2 1 1 2 2 1 1 1 a b a b a b a b a b a b
>= 8
Combine another two.
(x 1)
- - - - - - - - - 1 1 1 - - - - - - - - - - - a
- - - - - - - - - 1 1 1 - - - - - - - - - - - b
- - - - - - - - - 1 1 1 - - - - - - - - - - - a
- - - - - - - - - 1 1 2 - - - - - - - - - - - b
- - - - - - - - 1 1 1 2 - - - - - - - - - - - a
- - - - - - - - 1 1 2 1 - - - - - - - - - - a b
- - - - - - - - 1 1 2 1 - - - - - - - - - - b a
- - - - - - - - 1 1 1 2 - - - - - - - - - - - b
- - - - - - - - - 1 1 2 - - - - - - - - - - - a
- - - - - - - - - 1 1 1 - - - - - - - - - - - b
- - - - - - - - - 1 1 1 - - - - - - - - - - - a
- - - - - - - - - 1 1 1 - - - - - - - - - - - b
>= 8
Four 3-in-a-row constraints.
(x 1)
- - - - - - 1 1 1 1 1 1 - - - - - - a b a b a b
- - - - 1 1 1 1 1 1 1 1 - - - - - - - - - - - -
- - - - - 1 1 1 1 1 1 1 - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
1 1 1 1 1 1 1 - - - - - - - - - - - - - - - - -
1 1 1 1 1 1 1 1 - - - - - - - - - - - - - - - -
1 1 1 1 1 1 - - - - - - c d c d c d - - - - - -
1 1 1 1 1 1 1 1 - - - - - - - - - - - - - - - -
1 1 1 1 1 1 1 - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
>= 8
Another four.
(x 1)
- - - - 1 1 1 1 1 - - - - - - - - - a - - - - -
- - - - 1 1 1 1 1 - - - - - - - - - b - - - - -
- - - - 1 1 1 1 1 - - - - - - - - - a - - - - -
- - - - 1 1 1 1 1 - - - - - - - - - b - - - - -
- 1 - - 1 1 1 1 1 - - - - - - - - - a - - - - -
- 1 1 - 1 1 1 1 1 - - - - - - - - - b - - - - -
1 1 1 - 1 1 - 1 1 - - - c - - - - - - - - - - -
1 1 1 - - 1 - 1 - - - - d - - - - - - - - - - -
1 1 1 - - - - - - - - - c - - - - - - - - - - -
1 1 1 - - - - - - - - - d - - - - - - - - - - -
1 1 1 - - - - - - - - - c - - - - - - - - - - -
1 1 1 - - - - - - - - - d - - - - - - - - - - -
>= 8
(x 1)
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - 1 - - - - - - - - - - - - -
- - - - - - - - - 1 - - - - - - - - - - - - - -
- - - - - - - - - - 1 1 - - - - - - - - - - - b
- - - - - - - - - 1 - - - - - - - - - - - - - -
- 1 - 1 - 1 - - - - 1 1 - - - - - - - - - - - b
1 - 1 - 1 - 1 - - 1 - - - - - - - - - - - - - -
1 - 1 - 1 - - - - - 1 1 a - a - a - - - - - - b
>= 4
(x 1)
- - - - - - - - - - 1 1 - - - - - - - - - - - a
- - - - - - - - - 1 - - - - - - - - - - - - - -
- - - - - - - - - - 1 1 - - - - - - - - - - - a
- - - - - - - - - 1 - - - - - - - - - - - - - -
- - - - - - - - - - 1 1 - - - - - - - - - - - a
- - - - - - - - - 1 - - - - - - - - - - - - - -
- - - - - - - - - - 1 - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - 1 - 1 - 1 - - - - - - - - - - - - -
- - - - - 1 - 1 - 1 - 1 - - - - - - - - - - - -
- - - - - - - 1 - 1 - 1 - - - - - - - b - b - b
>= 4
Thirty single-square constraints.
Note that the (3,3) location is forbidden to cover these squares.
(x 1)
- - - 2 2 - 1 1 2 1 1 1 - - - a b - c - - - d e
- 2 1 - 1 2 2 - 2 1 1 1 - - - - - f g - - - h i
- 1 - 2 3 2 1 2 2 2 1 1 - - - - - - - - - - - -
2 - 2 2 1 3 1 3 - 2 1 2 j - - - - - - - - - - -
2 1 3 1 2 2 2 1 2 1 - 1 k - - - - l - - - - - -
- 2 2 3 2 - 1 2 2 - 1 - - m - - n - o - - - p -
1 2 1 1 2 1 3 - 2 - 1 - q r - - - s t - - - u -
1 - 2 3 1 2 - 2 2 1 - 1 - - - - - - - - - - - -
2 2 2 - 2 2 2 2 - 2 1 2 - - - - - - - - - - - -
1 1 2 2 1 - - 1 2 2 - 1 - - - - - - - - - - - -
1 1 1 1 - 1 1 - 1 - 1 1 v w - - - x y - - - z A
1 1 1 2 1 - - 1 2 1 1 - B C - - - - - - - - D -
>= 30
Six disjoint single-square constraints multiplied by 2.
(x 2)
- - - 2 - - - - - - - - - - - - - - - - - - - -
- 2 - - - - - - - - - - - a - - - - - - - - - -
- - - 2 - - - - - - - - - - - - - - - - - - - -
2 - 2 - 2 - 2 - - - 2 - - - - - - - - - - - - -
- - - 2 - - - 2 - 2 2 - - - - - - - - - - - - -
- - - - - 2 - - - 2 - 2 - - - - - b - - - - - c
- - - 2 - - - 2 - 2 - 2 - - - - - - - - - - - d
- - - - 2 - 2 - - 2 2 - - - - - - - - - - - - -
- - - - - - - - - - 2 - - - - - - - - - - - - -
- - - - 2 2 2 2 - - - - - - - - - - - - - - - -
- - - 2 2 - - 2 2 - - - - - - - - - - - - - - -
- - - - - 2 2 - - - - - - - - - - e f - - - - -
>= 12
Multiply the corner square constraint by 3.
(x 3)
3 - - - - - - - - - - - o - - - - - - - - - - -
- - 3 - - - - - - - - - - - - - - - - - - - - -
- 3 - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
>= 3
Multiply these two single-square constraints by 4.
Note that the (3,3) location is forbidden to cover these squares.
(x 4)
- 4 4 - - - - - - - - - - o - - - - - - - - - -
4 - - 4 - - - - - - - - o - - - - - - - - - - -
4 - - - - - - - - - - - - - - - - - - - - - - -
- 4 - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - -
>= 8
Add the above ten constraint sets.
3 4 4 4 3 1 3 3 4 3 4 4
4 4 4 4 3 4 4 2 4 4 3 3
4 4 - 4 4 4 3 4 4 4 4 4
4 4 4 2 4 4 4 4 1 4 4 4
3 3 4 4 4 4 4 4 4 4 4 4
1 4 4 4 4 4 3 4 4 4 4 3
3 4 3 4 4 3 3 3 4 4 4 2
3 2 4 4 4 4 3 4 3 4 4 4
4 4 4 1 4 4 4 3 - 4 4 4
3 4 4 4 4 4 4 4 4 4 4 4
4 3 4 4 4 4 4 4 4 4 3 4
4 3 4 4 4 3 3 4 4 4 4 4
>= 93
Divide by 4 and round.
1 1 1 1 1 1 1 1 1 1 1 1 o o - o o - o o o o o o
1 1 1 1 1 1 1 1 1 1 1 1 o o - - - o o - - - o o
1 1 - 1 1 1 1 1 1 1 1 1 - - - - - - o - - - - o
1 1 1 1 1 1 1 1 1 1 1 1 o - - - - - o - - - - o
1 1 1 1 1 1 1 1 1 1 1 1 o - - - - o o - - - - o
1 1 1 1 1 1 1 1 1 1 1 1 - o - - o o o - - - o o
1 1 1 1 1 1 1 1 1 1 1 1 o 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 1 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 1 1 o o - - - o o - - - o o
1 1 1 1 1 1 1 1 1 1 1 1 o o o o o o o o o o o o
>= 24