주메뉴바로가기.. 본문바로가기

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

네이버밴드 구글플러스

2017년 10월 08일 17:00 프린트하기

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

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


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


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

네이버밴드 구글플러스

2017년 10월 08일 17:00 프린트하기

혼자보기 아까운 기사
친구들에게 공유해 보세요

네이버밴드 구글플러스

이 기사가 괜찮으셨나요? 메일로 더 많은 기사를 받아보세요!

20 + 7 = 새로고침
###
과학기술과 관련된 분야에서 소개할 만한 재미있는 이야기, 고발 소재 등이 있으면 주저하지 마시고, 알려주세요. 제보하기

관련 태그뉴스