체스 최대배치문제 - 나이트편

비숍편에 이어 최대배치문제 나이트 편을 소개한다.

 다시 최대배치문제에 대해 설명한다. 8×8 체스판과 함께 수없이 많은 장기말들이 있다고 가정하자. 최대배치문제란 동일한 기물 여러개를 체스판 위에 서로 공격하지않게 하면서 최대한 많이 올리려면 어떻게 해야하는지, 그리고 그 최댓값은 얼마인지 묻는 문제이다.

각 메이저 기물들에 대해 최대배치문제의 최댓값이 다음과 같이 알려져있다.

킹 : 16

퀸 : 8

룩 : 8

비숍 : ??

나이트 : ??

여기서 나이트의 경우에 대해 최대배치문제를 풀고 증명하라. 나이트는 날일(日)자 방향으로 공격한다는 사실을 유념.

(비숍의 경우 이전 체스퍼즐 글을 참고하라.)

풀이

 나이트는 무려 32개나 올릴 수 있다.

증명을 위해서는 다음과 같은 사실을 이용하면 된다.

(나이트 일주) 나이트가 체스판의 모든 칸을 정확히 한 번씩만 밟으며 움직인 뒤 다시 제자리로 올 수 있다.

여러 일주법이 있지만 오일러의 1757년 풀이를 이용한다.(사실 어떤 경로를 이용하든 풀이의 논리에는 문제가 없다.) 

 이 일주를 실에 꿰인 단추들처럼 생각하고 펼치면 64개의 칸이 배치된 원형 고리를 얻는다. 나이트의 이동 특성상 검은칸 흰칸이 번갈아가며 있음을 알 수 있다. 

 체스판에 33개 이상의 나이트를 배치한다고 하자. 이를 원형고리에 배치하는 것으로 옮기면, 비들기집의 원리에 의해 적어도 2개의 나이트가 서로 원형고리안에 맞붙게된다. 이렇게 맞붙은 두 나이트는 체스판 위에서 서로 공격하게 되므로 33개 이상의 나이트를 배치할 수 없다.

 즉 배치의 최댓값은 32개 이하이다.

이제 32개일때의 해를 직접적으로 보이면 된다.

나이트의 공격 특성상 흰 칸의에 있는 나이트는 반드시 검은 칸만을 공격한다. 고로 모든 흰 칸 위에 올리면 그만이다.(혹은 모든 검은 칸에 올려도 된다.)