상금 10억 원 걸린 체스 문제 탄생!

8×8 체스판에 퀸 8개를 올려놓는 8퀸 문제의 정답 중 하나. 모든 퀸이 서로 다른 세로줄과 가로줄, 대각선에 있다. - FlankerFF(w) 제공

9월 1일 이안 겐트 영국 세인트앤드루스대학교 교수팀이 ‘8퀸 문제’를 일반화한 ‘N-퀸 완전 문제’가 NP-완전에 속한다고 발표하면서 무려 10억 원의 상금이 걸린 체스 문제가 탄생했습니다.

N-퀸 문제는 n×n 체스판에 퀸 N개를 놓는 방법을 찾는 겁니다. 체스 규칙에 따라 퀸을 놓아야 하므로 풀기가 만만치 않습니다. 퀸은 상하좌우뿐만 아니라 대각선까지 모든 방향으로 움직이기 때문에 어떤 퀸이 다른 퀸을 공격하지 못하게 막으려면 모든 퀸이 서로 다른 가로줄, 세로줄, 대각선에 있어야 하지요.

교수팀이 선보인 문제는 N개 중 일부가 이미 자리를 잡고 있을 때, 나머지를 올려놓는 겁니다. 문제는 반복되는 규칙이 없어 슈퍼컴퓨터로 일일이 퀸의 위치를 대입해도 답을 찾는 데 수천 년이 걸린다는 거지요. 교수팀은 다항 시간에 답을 찾을 수 없다는 걸 증명해 이 문제가 NP-완전이라는 걸 밝혔습니다. 따라서 이 문제를 푸는 알고리듬을 만든다면 ‘P=NP’라는 수학계 7대 난제를 해결하는 셈이 돼, 미국 클레이 수학연구소가 주는 상금을 받을 수 있습니다. 여러분도 도전하세요!

동아사이언스