노노그램 푸는 법

결론부터 — 찍지 말고 「겹치는 칸」부터 칠한다

노노그램(네모로직)은 줄 옆의 숫자만 보고 칸을 칠해 그림을 완성하는 퍼즐입니다. 숫자 「3 2」는 그 줄에 칠한 덩어리가 왼쪽부터 3칸, 2칸 순서로 있고 그 사이에 빈칸이 적어도 하나 있다는 뜻입니다.

푸는 법의 뼈대는 하나입니다. 한 줄에서 덩어리를 놓을 수 있는 모든 자리를 떠올렸을 때, 어느 자리에서든 칠해지는 칸만 칠한다. 한판고 노노그램이 판을 고를 때 쓰는 추론기도 정확히 이 방식이고, 이 방식만으로 끝까지 풀리는 판만 냅니다. 그래서 찍을 필요가 한 번도 없습니다.

겹치기 공식 — 「여유」보다 긴 덩어리는 가운데가 정해진다

먼저 그 줄의 여유를 계산합니다. 여유 = 줄 길이 − (숫자의 합 + 덩어리 수 − 1). 덩어리를 전부 왼쪽으로 붙였을 때 오른쪽에 남는 칸 수입니다. 그러면 덩어리마다 길이 − 여유만큼의 칸이 어느 자리에 놓든 겹치므로 바로 칠할 수 있습니다. 추론 코드로 10칸 줄을 계산하면 이렇습니다.

표에서 두 가지가 보입니다. 첫째, 10칸 줄에서 숫자 하나가 5 이하이면 처음에는 한 칸도 확정되지 않습니다. 6부터 2칸씩 늘어납니다. 둘째, 여유가 0인 줄은 숫자만 보고 줄 전체가 정해집니다. 「5 4」는 5+4+사이 1칸이 딱 10칸이라 칠할 칸 9개와 빈칸 1개가 한 번에 나옵니다. 그래서 첫 수는 늘 「숫자를 더해 줄 길이에 가까운 줄」입니다.

그다음 네 가지 — 끝 붙이기·빈칸 표시·다 찬 줄·직각 이동

• 끝 붙이기. 줄의 맨 끝 칸이 칠해졌다면 첫 덩어리는 거기서 시작합니다. 첫 숫자가 3이면 끝에서 3칸을 칠하고 넷째 칸은 빈칸으로 확정합니다. 빈칸으로 막힌 자리 바로 옆도 같은 방법으로 셉니다.
• 빈칸을 ✕로 표시. 덩어리가 닿을 수 없는 칸은 ✕로 막아 둡니다. ✕는 채점에 들어가지 않지만, 줄의 길이가 짧아진 것과 같아서 여유가 줄고 겹치는 칸이 다시 생깁니다.
• 다 찬 줄은 나머지를 모두 ✕. 칠한 칸이 숫자와 맞아떨어지면 게임이 바깥 숫자를 흐리게 바꿉니다. 그 줄의 남은 칸은 전부 빈칸이니 한꺼번에 막으세요.
• 막히면 직각으로. 가로줄에서 더 나올 것이 없으면 세로줄로 넘어갑니다. 방금 가로에서 확정한 칸이 세로줄에서는 「끝 붙이기」의 출발점이 됩니다.

난이도별로 첫 훑기에서 얼마나 정해지나

판 생성 코드로 난이도마다 300판씩 만들고, 빈 판에서 가로줄 전부와 세로줄 전부를 한 번씩 겹치기로 훑었을 때 정해지는 칸을 셌습니다. 「훑기 횟수」는 가로 전부→세로 전부를 한 번으로 치고, 더 정할 칸이 없음을 확인하는 마지막 훑기까지 센 값입니다. 게임이 어려움 판을 고를 때 쓰는 바로 그 숫자입니다.

쉬움은 첫 훑기로 판의 절반 넘게 정해지지만, 어려움은 평균 19칸, 적게는 2칸뿐이었습니다. 어려움에서 시작부터 막막한 것은 실력 탓이 아니라 그렇게 골라 낸 판이기 때문입니다. 어려움은 최소 5번을 훑어야 끝나는 판만 나오고, 실제로는 5~11번이 걸렸습니다. 이때는 겹치기보다 ✕ 표시와 끝 붙이기가 일을 합니다. 5×5 미니는 쉬움 2.2번, 어려움 3.1번이면 끝납니다.

모두가 같은 판을 받는 오늘의 도전은 10×10 보통입니다. 51일치를 그대로 만들어 보니 30일이 3번, 16일이 4번 훑기로 끝났고, 6번이 걸린 날은 하루였습니다. 첫 훑기로 정해지는 칸은 평균 47칸이었습니다.

누가 만들었나 — 그리고 왜 찍기 없는 판이 귀한가

이 퍼즐은 일본의 그래픽 편집자 이시다 논이 1987년 도쿄의 한 그림 대회에서 우승한 것을 계기로 떠올려 1988년 「창문 그림 퍼즐(Window Art Puzzles)」이라는 이름으로 처음 발표했고, 퍼즐 작가 니시오 데쓰야도 비슷한 시기에 따로 같은 퍼즐을 냈습니다. 「노노그램」이라는 이름은 영국의 퍼즐 수집가 제임스 달게티가 이시다의 이름 「논」과 다이어그램의 「그램」을 붙여 만들었고, 1990년부터 영국 선데이 텔레그래프에 실렸습니다(The Puzzle Museum, Wikipedia). 한국에서는 네모로직, 네모네모 로직으로 더 많이 불립니다.

아무 그림이나 숫자로 바꾸면 답이 여러 개이거나, 찍지 않고는 못 푸는 판이 쉽게 나옵니다. 노노그램에 답이 있는지 가리는 문제는 컴퓨터로도 어려운 부류(NP-완전)로 알려져 있습니다(Ueda·Nagao 1996). 한판고는 그래서 줄 추론만으로 끝까지 풀리는 판만 내고, 다른 방법으로 답이 정확히 하나인지 한 번 더 셉니다.

노노그램 하러 가기 →