노노그램의 논리 퍼즐의 세계적 인기와 수학적 매력을 알아보자

네모네모 로직, 혹은 피크로스라는 이름으로 더 익숙한 '노노그램'. 가로세로 숫자를 힌트 삼아 빈칸을 채워 나가다 보면 어느새 머릿속에 숨겨진 그림이 툭 튀어나오는 매력적인 퍼즐이죠.

 이 단순해 보이는 격자판 속에 사실은 전 세계를 매료시킨 역사와, 컴퓨터 과학자들을 골치 아프게 만드는 놀라운 수학적 비밀이 숨어 있다는 사실, 알고 계셨나요? 노노그램의 숨겨진 이야기들을 가볍게 파헤쳐 봅니다.

1. 게임보이와 만난 노노그램, 세계적인 열풍이 되다

사실 노노그램이 처음 세상에 나왔을 때는 지루한 출퇴근길 신문 구석이나 잡지 페이지를 채우는 소소한 흑백 퍼즐에 불과했습니다. 누구나 쉽게 접할 수 있었지만, 전 세계적인 '현상'으로 폭발적인 인기를 끌게 된 건 단연 1990년대 중반 닌텐도의 손을 거치면서부터였습니다.

1995년, 닌텐도는 게임보이용 소프트웨어로 《마리오의 피크로스(Mario's Picross)》를 세상에 내놓았습니다.

당시의 투박하고 단색이던 게임보이 화면과 노노그램의 규칙은 그야말로 찰떡궁합이었습니다. 친숙한 마리오 캐릭터를 내세워 진입 장벽을 낮췄고, 칸을 하나씩 채워갈 때마다 조금씩 형태를 드러내는 도트 그래픽은 게이머들의 승부욕을 무섭게 자극했죠.

특히 퍼즐을 풀 때 흘러나오던 중독성 강한 BGM은 아직도 많은 이들의 추억 속에 남아 있습니다. 이때부터 '피크로스'라는 이름은 노노그램의 고유명사처럼 번져 나갔고, 오늘날 수많은 모바일 퍼즐 게임들이 탄생할 수 있는 튼튼한 뿌리가 되었습니다.

2. 단순한 취미가 아니라오: 컴퓨터가 풀기 버거운 난제

우리의 눈에는 그냥 아기자기한 숫자 놀이처럼 보이지만, 수학과 컴퓨터 과학의 세계로 들어가는 순간 노노그램은 전혀 다른 얼굴을 드러냅니다. 사실 컴퓨터 입장에서 노노그램은 그리 만만한 상대가 아닙니다.

 수학적 계산이 필요한 대형 노노그램 퍼즐

컴퓨터 과학 분야에서 노노그램은 NP-완전(NP-complete) 문제로 분류됩니다. 말이 거창하지만 쉽게 말해 "어떤 노노그램이든 항상 빠르게 풀어내는 만능 방법이 아직 알려져 있지 않다"는 뜻입니다.

그렇다고 큰 퍼즐을 컴퓨터가 못 푸는 건 아닙니다. 요즘 풀이 프로그램은 50x50짜리도 눈 깜짝할 사이에 풀어냅니다. 비결은 모든 경우의 수를 대입하지 않는 것이에요.

무식하게 전부 시도(브루트 포스)하면 30x30만 되어도 감당이 안 됩니다. 그래서 컴퓨터도 사람처럼 한 줄씩 봅니다. 이 줄의 단서와 이미 확정된 칸만 가지고 새로 확정할 수 있는 칸을 찾고, 그걸 행과 열을 오가며 반복하는 거죠. 우리가 쓰는 겹치기 기법과 똑같은 원리입니다.

여기서 재밌는 사실 하나. 잘 만들어진 노노그램은 이 방식만으로 끝까지 풀립니다.  왜냐하면 그렇지 않으면 사람이 못 푸니까요. 종이와 연필로 "여기가 검은색이라 가정하고 틀리면 되돌아오기"를 하는 건 너무 고통스럽잖아요. 제작자들이 사람이 즐길 수 있게 만들다 보니, 자연히 컴퓨터에게도 다루기 좋은 문제가 된 셈입니다.

결국 우리가 꽉 막힌 대형 퍼즐 앞에서 "여기다!" 하고 짚어낸 한 칸은, 컴퓨터가 쓰는 것과 같은 논리를 머릿속에서 직접 굴려 얻어낸 결과인 셈이죠.

마무리하며

잡지 구석의 낙서에서 시작해 세상을 뒤흔든 닌텐도의 명작이 되기까지, 그리고 그 속 숨겨진 묵직한 수학적 알고리즘까지. 노노그램은 알면 알수록 참 매력적인 퍼즐입니다. 스마트폰 화면을 내려놓고, 혹은 복잡한 생각에서 잠시 벗어나 오늘 저녁엔 종이와 연필을 들거나 뚝딱뚝딱 칸을 채워나가는 노노그램 한 판 어떠신가요? 꽉 막힌 머리를 시원하게 비워주는 좋은 쉼터가 되어줄 겁니다.