[9월의 퍼즐] 용왕을 배치하려면

체스에서 가장 강한 기물은 퀸^Queen이다. 이것은 가로, 세로, 대각선, 어느 방향으로든 얼마든지 움직일 수 있어서 그야말로 최강의 기물이라 할 수 있다. 가로 세로 8개의 칸으로 이루어진 격자 모양의 체스판 위에 여덟 개의 퀸을 올려 놓아, 어느 두 퀸도 서로를 공격하지 못하도록 배치하는 “여덟 퀸 문제”는 1848년에 독일의 막스 베첼^{Max Bezzel}이 창안한 이후, 가우스^{Carl Friedrich Gauss}를 비롯한 여러 수학자들이 연구하고 일반화하였으며, 20세기에는 위대한 전산학자 데이크스트라^{Edsger Dijkstra}가 구조화 프로그래밍의 예시로 사용하기도 하였다.

세계에는 체스와 비슷한 게임이 많이 있는데, 한중일의 장기도 그 가운데 하나이다. 특히 일본의 장기인 쇼기^将棋는 한국과 중국의 장기와 달리 체스처럼 격자 모양의 칸 안에 기물을 배치하고, 기물의 움직임도 체스와 비슷하다.

9월 퍼즐에서는 일본 장기인 쇼기를 이용한 문제를 다루어 보자.

쇼기는 가로 세로 9개의 칸으로 이루어진 격자 모양의 쇼기판에 기물을 배치한다. 쇼기에서 가장 강한 기물은 가로 세로 어느 쪽으로도 마음대로 움직일 수 있는 비차^{飛車, 일본어로는 히샤}로, 한국과 중국 장기의 차^車, 체스의 룩^Rook과 비슷하다. 그런데 쇼기에서는 체스처럼 기물이 승격을 할 수 있어서, 비차가 승격하면 용왕^{龍王, 일본어로는 류오}이라는 기물로 바뀐다. 비차 기물 밑면에 龍王이 적혀 있어서, 승격한 기물은 뒤집어서 사용한다.

용왕은 비차의 움직임에 더하여, 대각선 방향으로 한 칸을 움직일 수 있어서, 쇼기에서 비차보다 더 강한 기물이라 할 수 있다.

가로 세로 9칸인 쇼기판에 어느 두 용왕도 서로를 공격할 수 없게 용왕을 배치해 보자. 당연히 용왕을 9개보다 더 많이 배치할 수는 없다. 이러면 문제가 좀 재미가 없으니, 여기에 한국과 중국 장기의 졸^卒, 체스의 폰^Pawn에 해당하는 기물인 보병^{步兵, 일본어로는 후효}을 추가하자. 그러면 보병이 용왕의 경로를 막아서 용왕을 더 배치할 수 있다.

이해를 돕기 위하여 보병 기물 1개, 용왕 기물 9+1=10개를 배치한 예를 아래에 그렸다. 5열과 e행의 두 용왕 사이에 보병이 끼어 있어서 용왕들끼리 서로를 공격할 수 없다. 이 배치는 180도 돌려도 같아지는 대칭적인 배치이다.

보병의 개수를 늘려 용왕을 더 많이 배치해 보자. 보병 기물 4개, 용왕 기물 9+4=13개를 쇼기판에 배치하여 어느 두 용왕도 서로를 공격할 수 없게 하려면 어떻게 해야할까? 이렇게 하는 방법은 아주 많아서 한 가지 제한을 추가하자. 쇼기판을 90도 돌려도 같은 배치가 되도록 하려면 보병 4개와 용왕 13개를 어떻게 배치해야 할까?