Bishop and Knight

킹이 있는 칸을 $(r,c)$라고 하자. 위쪽 또는 아래쪽 변까지의 거리 중 작은 값을 $x$, 왼쪽 또는 오른쪽 변까지의 거리 중 작은 값을 $y$라고 정의한다. 두 값을 각각 $3$에서 잘라낸 뒤 $x\le y$가 되도록 정렬한다.

킹의 현재 칸과 이동 가능한 칸은 킹을 중심으로 한 $3\times3$ 영역에만 존재한다. 이 영역의 칸을 공격하거나, 영역 안에 배치된 기물을 다른 기물로 보호하려면 킹에서 체비쇼프 거리 $3$보다 멀리 떨어진 나이트는 필요하지 않다. 비숍도 같은 대각선 위에서 더 가까운 위치로 옮겨 동일한 역할을 하도록 정규화할 수 있다. 따라서 경계까지의 거리가 $3$ 이상인 경우는 모두 동일하게 취급할 수 있다.

가능한 위치 유형은 다음 열 가지뿐이다.

$$(0,0),(0,1),(0,2),(0,3),(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)$$

각 유형에서 킹 주변의 유한한 영역만 조사하면 된다. 킹의 현재 칸과 이동 가능한 각 칸을 목표 칸으로 두고, 그 칸에 기물이 있다면 해당 기물을 제거한 상태에서 다른 기물이 목표 칸을 공격하는지 검사한다. 나이트의 공격은 곧바로 계산할 수 있고, 비숍은 목표 칸과 비숍 사이에 다른 기물이 없는지 확인한다.

$S=4,5,6$에서는 실제 체스판 전체를, $S\ge7$에서는 각 유형을 대표하는 $7\times7$ 판을 완전 탐색한다. 각 비숍 수에 대해 필요한 나이트 수의 최솟값을 구하면 다음 표를 얻는다. 표의 값 이하가 아니라, 주어진 나이트 수가 표의 값 이상일 때 가능하다. $B\ge 5$인 열은 모두 이다.

$S=2$에서는 어떤 위치도 불가능하다. $S=3$은 별도로 완전 탐색하며 다음 표를 사용한다. $\infty$는 불가능함을 뜻한다.

이제 각 유형에 속하는 칸의 수를 센다. 한 좌표축에서 가장 가까운 경계까지의 거리를 $d$라고 할 때, 거리를 $3$에서 자른 값이 $d$인 좌표의 개수를 $C_d$라고 하자.

$d=0,1,2$에 대해서는 다음과 같다.