d라이브러리

“겁도 없이 체스 세계에 들어왔군.”
할아버지의 이야기를 들으며 성 밖으로 걸어 나온 체리와 스론 앞에 위풍당당한 체스 여왕이 나타났어요. 여왕은 체리와 스론에게 이렇게 말했지요.
“내가 내는 문제를 풀면 체스 세계 밖으로 무사히 내보내 주지.” 

여러 명의 ‘퀸’을 배치하라!

여왕이 낸 첫 번째 문제는 가로 8줄, 세로 8줄인 체스판에 8명의 ‘퀸’이 서로를 공격하지 않도록 배치하라는 것이었어요. 일명 ‘여덟 퀸 퍼즐’이었지요. 
퀸은 가로, 세로, 대각선 어느 방향으로든 자유롭게 움직일 수 있는 기물이에요. 한 칸에 퀸 1개가 놓여있다면, 다음 차례에는 가로, 세로, 대각선 어느 방향에서도 먼저 둔 퀸으로부터 공격당하지 않는 위치에 퀸을 둬야 하지요. 
여왕은 먼저 a5에 퀸을 두고, 체리와 스론에게 남은 퀸 7개를 알맞은 자리에 두라고 말했어요. 체리와 스론은 먼저 여왕이 둔 퀸이 공격할 수 있는 경로를 하늘색으로 색칠했어요. 하늘색으로 칠해진 곳을 피해서 다음 퀸을 두면 되기 때문이지요. 
체리는 두 번째 퀸을 f8에 두고 다시 퀸이 움직일 수 있는 경로를 보라색으로 색칠했어요. 가로줄과 세로줄에 퀸이 하나씩만 놓여야 한다는 사실을 깨달은 스론은 d7에 세 번째 퀸을 두고 퀸의 경로를 노란색으로 색칠했지요. 
체리와 스론은 나머지 5개의 퀸을 어디에 두었을까요? 나머지 퀸의 이동 경로도 색칠하면서퀸을 어디에 두면 좋을지 생각해 보세요.

기사가 체스판을 여행하려면?

여왕은 곧바로 ‘기사의 여행(Knight’s tour)’이라는 두 번째 문제를 냈어요. 나이트(기사)가 주어진 모든 칸을 한 번씩만 지나가는 방법을 찾는 문제였지요. 
여왕이 가져온 체스판은 가로 3줄, 세로 3줄로 이뤄져 있었어요. 여왕은 나이트가 가운데를 제외한 모든 칸을 한 번씩 방문하도록 화살표를 그려보라고 했지요. 나이트는 앞뒤 좌우 중 한 방향으로 한 칸 움직이고, 그 방향의 대각선 왼쪽 또는 오른쪽으로 한 칸을 더 움직이는 기물이에요. 

체리와 스론은 먼저 나이트를 위로 한 칸, 오른쪽 위 대각선으로 한 칸을 움직여 b3의 자리에 두었어요. 그런 다음에는 아래로 한 칸, 오른쪽 아래 대각선으로 한 칸을 움직여 c1의 자리에 두었지요. 헷갈리지 않도록 한 번 방문한 칸에는 ‘OK’ 표시를 했어요. c1에 도착한 나이트는 다음에 어디로 이동할 수 있을까요? 체리와 스론이 나머지 기사의 여행을 어떻게 완성했을지, 나이트의 다음 움직임을 화살표로 표시해보세요. 가운데 칸을 제외하고 모든 칸에 한 번씩 OK 표시를 적을 수 있어야 해요. 이미 OK가 있는 칸을 지나갈 순 있지만 최종 도착지가 될 순 없어요.