노노그램은 정말 슈퍼컴퓨터도 못 풀까 — NP-완전의 진짜 의미
노노그램을 검색하다 보면 이런 문장을 자주 만나게 됩니다.
"노노그램은 NP-완전 문제라서, 판이 커지면 슈퍼컴퓨터도 풀 수 없다."
앞부분은 맞습니다. 뒷부분은 틀렸습니다.
실제로 요즘 노노그램 풀이 프로그램은 50x50짜리를 눈 깜짝할 사이에 풉니다. 저희 사이트에 있는 80x80 퍼즐도 마찬가지예요. 그럼 NP-완전이라는 말은 무슨 뜻일까요?
이 오해를 풀어보면, 우리가 노노그램을 푸는 방식에 대해서도 꽤 재밌는 걸 알게 됩니다.
NP-완전이 뜻하는 것
먼저 용어부터 정리하겠습니다. 어떤 문제가 NP-완전이라는 건 대략 이런 뜻입니다.
"모든 경우에 대해 빠르게 푸는 방법이 알려져 있지 않다."
여기서 중요한 건 모든 경우입니다. 특정 문제를 못 푼다는 게 아니라, 어떤 문제를 던져줘도 항상 빠르게 푸는 만능 알고리즘이 없다는 뜻이에요.
그리고 하나 더. "빠르게 푸는 방법이 알려져 있지 않다"이지 "존재하지 않는다"가 아닙니다. 이게 그 유명한 P 대 NP 문제인데, 아직 아무도 증명하지 못했습니다.
그럼 왜 실제로는 잘 풀릴까
핵심은 이겁니다. 우리가 푸는 노노그램은 '임의의 노노그램'이 아닙니다.
NP-완전성은 상상할 수 있는 모든 노노그램에 대한 이야기입니다. 그중에는 정말 고약한 것들도 있어요. 하지만 실제로 퍼즐책이나 게임에 실리는 노노그램은 그런 게 아닙니다.
제대로 만든 노노그램은 한 줄씩만 봐도 풀립니다.
이걸 '라인 솔빙(line solving)'이라고 부릅니다. 지금 이 행 하나만 놓고, 이 행의 단서와 이미 확정된 칸만 가지고 새로 확정할 수 있는 칸을 찾는 방식이죠. 겹치기 기법이 대표적입니다.
한 줄만 봐도 확정되는 칸이 나옵니다. 이 단순한 작업의 반복이 라인 솔빙입니다.
이 작업은 빠릅니다. 한 줄의 길이에 비례하는 정도라서, 격자가 커져도 감당할 수 있어요. 행과 열을 번갈아 훑는 걸 반복하면 대부분의 퍼즐이 풀립니다.
좋은 퍼즐의 숨은 조건
여기서 재밌는 사실이 나옵니다. 노노그램 제작자들은 알게 모르게 "라인 솔빙만으로 풀리는 퍼즐"을 만들어 왔습니다.
왜냐하면 그게 아니면 사람이 못 푸니까요. 라인 솔빙으로 안 풀리는 퍼즐은 "여기가 검은색이라고 가정해보고, 모순이 생기면 되돌아오기"를 해야 하는데, 이건 종이와 연필로 하기엔 너무 고통스럽습니다.
그래서 시중의 노노그램은 사실상 전부 라인 솔빙으로 풀립니다. 사람이 즐길 수 있게 만들다 보니 자연히 컴퓨터에게도 쉬운 문제가 된 거죠.
노노그램이 이론적으로 어렵다는 것과, 우리가 실제로 푸는 노노그램이 어렵다는 건 다른 이야기입니다.
진짜로 쉬운 경우도 있습니다
수학적으로 확실히 쉽다고 증명된 부류도 있습니다.
모든 행과 열에 숫자가 하나씩만 있고, 칠해진 칸이 전부 하나로 이어져 있는 경우입니다. 이런 노노그램은 2-SAT이라는 다른 문제로 변환할 수 있고, 그 문제는 빠르게 푸는 방법이 알려져 있습니다.
단서가 5 하나뿐인 줄들로만 이루어진 퍼즐을 떠올려보시면 됩니다. 확실히 쉬워 보이죠? 그 직관이 수학적으로도 맞다는 이야기입니다.
모든 줄의 단서가 하나뿐인 퍼즐. 이런 부류는 빠르게 푸는 방법이 증명되어 있습니다.
사람과 컴퓨터는 다르게 풉니다
이 대목이 개인적으로 가장 흥미롭습니다.
컴퓨터는 막히면 가정하고 되돌아옵니다. "여기를 칠했다고 치자" → 계속 진행 → 모순 발견 → 처음으로 복구. 이걸 수백만 번 반복해도 컴퓨터는 아무렇지 않습니다.
사람은 이걸 잘 못 합니다. 종이에 연필로 칠했다가 지우는 건 번거롭고, 어디까지 되돌려야 하는지 기억하기도 어려우니까요.
대신 사람은 패턴을 봅니다. 어느 줄이 정보가 많은지 한눈에 알아채고, 그림의 형태가 드러나기 시작하면 "여기가 귀겠구나" 하고 짐작합니다. 컴퓨터가 못 하는 종류의 추론이죠.
6400칸짜리 80x80 퍼즐. 사람에게는 몇 시간짜리 도전이지만, 컴퓨터에게는 순식간입니다.
그래서 잘 만든 퍼즐 앞에서는 사람이 컴퓨터보다 영리하게 풉니다. 시행착오 없이 확정된 것만 짚어나가니까요.
마무리
정리하면 이렇습니다.
- 노노그램은 NP-완전이 맞습니다
- 하지만 "슈퍼컴퓨터도 못 푼다"는 과장입니다
- 실제 퍼즐은 라인 솔빙으로 풀리게끔 설계되어 있습니다
- 그 설계는 사람이 풀 수 있게 하려다 보니 생긴 것입니다
결국 우리가 노노그램을 풀 수 있는 이유는, 누군가 사람이 풀 수 있는 문제를 만들어줬기 때문입니다. 퍼즐을 만든다는 게 생각보다 섬세한 일이라는 뜻이기도 하고요.
다음 글에서는 그 '좋은 퍼즐'의 조건을 좀 더 구체적으로 다뤄보겠습니다.
노노그램의 역사와 배경이 궁금하시다면 노노그램의 세계적 인기와 수학적 매력을, 풀이 기법을 익히고 싶으시다면 노노그램 초보자 완벽 가이드를 읽어보세요.